haskell - 描述给定 foldr 函数的前几个评估步骤

Question

给出如下函数:

mystery a b c xs = 
  foldr (\x rec a b -> rec x (b + c)) (\a b -> a + b - c) xs a b

我大致知道函数的作用，但我很难真正理解中间步骤。我选择了以下示例:

mystery 1 2 3 [1, 2, 3]

尤其是 rec 的使用让我很为难。我假设最后的步骤之一是这样的:

(\a b -> 3 + (b + 3 + 3 + 3) - 3) [] 1 2

所以输出是11。有人可以描述执行的前几个步骤吗？之后会发生什么:

foldr (\x rec a b -> rec x (b + 3)) (\a b -> a + b - 3) [1, 2, 3] 1 2

Answer 1

这里的关键是 foldr 操作是构造一个函数，然后将它应用到 a 和 b；我们可以通过添加括号来澄清它:

mystery a b c xs = 
(foldr (\x rec a b -> rec x (b + c)) (\a b -> a + b - c) xs) a b

如果 xs 列表为空，您将得到简单的初始函数 \a b -> a + b - c，然后将其应用于 a 和 b。

如果不为空，则对该函数进行连续变换(在每次迭代中，“rec”是前一个函数，用于构造新函数)。

为了说明，让我们为 mystery 1 2 3 [1, 2, 3] 手动运行 foldr；最初，我们有:

foldr (\x rec a b -> rec x (b + 3)) (\a b -> a + b - 3) [1,2,3]

应用 foldr 的等式:

foldr f z []     = z 
foldr f z (x:xs) = f x (foldr f z xs)

将表达式简化为:

(\rec a b -> rec 1 (b + 3)) (foldr (\x rec a b -> rec x (b + 3)) (\a b -> a + b - 3) [2,3])

重复我们得到的列表中的下一个值:

(\rec a b -> rec 1 (b + 3)) (\rec a b -> rec 2 (b + 3)) (foldr (\x rec a b -> rec x (b + 3)) (\a b -> a + b - 3) [3])

然后，对于最后一个:

(\rec a b -> rec 1 (b + 3)) (\rec a b -> rec 2 (b + 3)) (\rec a b -> rec 3 (b + 3)) (\a b -> a + b - 3)

我们需要组合这些函数，创建最终函数——用之前的函数替换“rec”:

(\rec a b -> rec 1 (b + 3)) (\rec a b -> rec 2 (b + 3)) (\rec a b -> rec 3 (b + 3)) (\a b -> a + b - 3)
=> (\rec a b -> rec 1 (b + 3)) (\rec a b -> rec 2 (b + 3)) (\a b -> (\a b -> a + b - 3) 3 (b + 3))
=> (\rec a b -> rec 1 (b + 3)) (\rec a b -> rec 2 (b + 3)) (\a b -> 3 + (b + 3) - 3))
=> (\rec a b -> rec 1 (b + 3)) (\a b -> (\a b -> 3 + (b + 3) - 3)) 2 (b + 3))
=> (\rec a b -> rec 1 (b + 3)) (\a b -> 3 + ((b + 3) + 3) - 3))
=> \a b -> (\a b -> 3 + ((b + 3) + 3) - 3)) 1 (b + 3)
=> \a b -> 3 + (((b + 3) + 3) + 3) - 3)
=> \a b -> b + 9

然后，我们将 \a b -> b + 9 应用于原始的“a”和“b”(即 1 和 2)，得到 2 + 9 = 11