GHCi中foldl遇类型错误，与foldr行为差异求解

问题场景 #

执行foldr (:) [1] [2,3,4]时，GHCi正常输出[2,3,4,1]；但执行foldl (:) [1] [2,3,4]时，会触发如下类型匹配错误：

<interactive>:51:7: error:
    • Couldn't match type ‘a’ with ‘[a]’
      Expected: [a] -> [[a]] -> [a]
        Actual: [a] -> [[a]] -> [[a]]
      ‘a’ is a rigid type variable bound by
        the inferred type of it :: [a]
        at <interactive>:51:1-21
    • In the first argument of ‘foldl’, namely ‘(:)’
      In the expression: foldl (:) [1] [2, 3, 4]
      In an equation for ‘it’: it = foldl (:) [1] [2, 3, 4]
    • Relevant bindings include it :: [a] (bound at <interactive>:51:1)

核心原因：foldl和foldr的函数参数顺序要求完全不同 #

别被「仅累加器位置不同」的表面印象误导，两者对传入的折叠函数的参数顺序要求是完全相反的：

• foldr的类型是(a -> b -> b) -> b -> [a] -> b，要求折叠函数先接收列表元素，再接收累加器，返回新的累加器。
• foldl的类型是(b -> a -> b) -> b -> [a] -> b，要求折叠函数先接收累加器，再接收列表元素，返回新的累加器。

而(:)（列表构造符）的类型是x -> [x] -> [x]，作用是「拿一个元素，再拿一个列表，返回把元素插在列表头部的新列表」——刚好完美匹配foldr的参数顺序，所以foldr (:) [1] [2,3,4]的执行逻辑是：

2 : (3 : (4 : [1])) → [2,3,4,1]

但对于foldl来说，它需要折叠函数先接收累加器（这里是[1]，属于[Int]类型），再接收列表元素（2/3/4，属于Int类型）。而(:)根本不接受这种参数顺序：它第一个参数必须是单个元素，第二个才是列表。这就导致GHC推断类型时出现矛盾：它需要累加器类型既是Int（满足(:)的第一个参数要求），又是[Int]（实际传入的初始累加器类型），所以抛出「无法匹配a与[a]」的错误。

实现预期输出[1,2,3,4]的正确写法 #

如果想用foldl实现把2/3/4依次追加到[1]末尾的效果，有两种常见方式：

1. 直接用匿名函数处理追加逻辑（简单但效率较低，因为++每次都要遍历整个列表）：

foldl (\acc elem -> acc ++ [elem]) [1] [2,3,4]

2. 用flip (:)反转参数顺序，最后反转列表（效率更高，因为(:)是O(1)操作）：

reverse $ foldl (flip (:)) [1] [2,3,4]

这里flip (:)把(:)的参数顺序反转成[x] -> x -> [x]，刚好符合foldl对折叠函数的参数要求，先把元素倒序加到初始列表头部，最后反转就得到正序的[1,2,3,4]。

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