Haskell中如何实现Tree类型的Applicative实例以生成全运算组合

你当前的Tree类型Applicative实例实现的是按位置对齐的zip风格应用逻辑，无法实现所有函数和所有参数的全交叉组合，不符合需求。

原有实现存在两个核心错误：

• Branch t1 t2 <*> Leaf a = t1 <*> Leaf a 逻辑直接丢弃了分支右子树的所有函数，导致测试用例中的乘法逻辑完全没有被执行
• Branch t1 t2 <*> Branch t3 t4 = Branch (t1 <*> t3) (t2 <*> t4) 是对齐匹配规则，仅会让左树左子树的函数应用到右树左子树的值、左树右子树的函数应用到右树右子树的值，不会产生交叉组合

完整实现代码如下：

data Tree a = Branch (Tree a) (Tree a) | Leaf a deriving (Eq, Show)

-- 先实现依赖的Functor实例
instance Functor Tree where
  fmap f (Leaf x) = Leaf (f x)
  fmap f (Branch l r) = Branch (fmap f l) (fmap f r)

instance Applicative Tree where
  pure = Leaf
  -- 单个函数应用到右树所有值，原有逻辑正确
  Leaf f <*> t = f <$> t
  -- 分支下的所有函数分别应用到整个右树，结果合并为新分支
  Branch l r <*> t = Branch (l <*> t) (r <*> t)

-- 参考fromList实现（按二分法构建平衡树）
fromList :: [a] -> Tree a
fromList [x] = Leaf x
fromList xs = let (lpart, rpart) = splitAt (length xs `div` 2) xs
              in Branch (fromList lpart) (fromList rpart)

-- 参考toList实现（先序遍历输出列表）
toList :: Tree a -> [a]
toList (Leaf x) = [x]
toList (Branch l r) = toList l ++ toList r

代入测试表达式：

toList $ fromList [(+),(*)] <*> fromList [1..3] <*> fromList [10,100,1000]

输出结果完全匹配预期：
[11,101,1001,12,102,1002,13,103,1003,10,100,1000,20,200,2000,30,300,3000]

内容的提问来源于stack exchange，提问作者Vic