为何使用foldr的mystery函数从左取元素却具有右结合性？

先看这段Haskell代码的推导过程：

mystery [1,2,3]
       = foldr snoc [] [1,2,3]
       = snoc 1 (foldr snoc [] [2,3])
       = snoc 1 (snoc 2 (foldr snoc [] [3]))
       = snoc 1 (snoc 2 (snoc 3 (foldr snoc [] [])))
       = snoc 1 (snoc 2 (snoc 3 ([])))
       = snoc 1 (snoc 2 ([3] ++ [2]))
       = [3,2] ++ [1]
       = [3,2,1]

你混淆了两个核心概念：元素的遍历顺序和函数应用的结合性。

foldr确实是从列表左端开始依次取元素（先取1，再取2，最后取3），但它的函数应用是右结合的——意思是，每个元素都会和「右边所有元素fold后的最终结果」结合，而非和左边已处理好的结果结合。

这里的snoc函数定义是snoc x xs = xs ++ [x]，也就是把元素追加到列表末尾。所以推导过程里，我们得先算出最右侧的折叠结果：

1. 空列表的折叠结果就是初始值[]
2. 把3和空列表结合：snoc 3 [] = [] ++ [3] = [3]
3. 把2和这个结果结合：snoc 2 [3] = [3] ++ [2] = [3,2]
4. 最后把1和这个结果结合：snoc 1 [3,2] = [3,2] ++ [1] = [3,2,1]

换句话说，foldr的右结合体现在函数嵌套结构上：foldr f z [x1,x2,x3] = f x1 (f x2 (f x3 z))，所有括号都嵌套在右侧，求值时必须从最内层的右侧元素开始计算，再逐步往左处理。这和你误以为的“从左到右求值”不是一回事——遍历顺序是左到右，但求值顺序是从右到左（因为每一步都依赖右侧的结果），再加上snoc的特性，最终得到了反转的列表。

如果换成左结合的foldl，结构会是foldl f z [x1,x2,x3] = f (f (f z x1) x2) x3，这时才是从左到右把元素和左侧已处理结果结合，用snoc的话会得到原列表[1,2,3]。

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