Haskell 应用于 foldr 的 lambda 函数中的因变量、自变量
Haskell dependent, independent variables in lambda function as applied to foldr
给定
> foldr (+) 5 [1,2,3,4]
15
第二个版本
foldr (\x n -> x + n) 5 [1,2,3,4]
也returns15。关于第二个版本，我不明白的第一件事是 foldr 如何知道哪个变量与累加器种子 5 相关联，以及哪个变量与列表变量的元素 [1,2,3,4] 相关联。在 lambda 演算方式中，x 似乎是因变量，n 是自变量。所以如果这个
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr _ z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
是foldr和这些
:type foldr
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
:t +d foldr
foldr :: (a -> b -> b) -> b -> [a] -> b
它的类型声明，我可以收集，从类型声明本身推断出 “哪个是依赖的，哪个是独立的” 的答案吗？上面 foldr 的两个例子似乎都必须这样做
(+) 1 ((+) 2 ((+) 3 ((+) 4 ((+) 5 0))))
我只是猜到了上面的第二个lambda函数版本，但我不太明白它是如何工作的，而第一个带有(+)的版本分解如上所示。
另一个例子是这个
length' = foldr (const (1+)) 0
const 似乎知道“丢弃”传入的列表元素并简单地递增，从初始累加器值开始。这与
相同
length' = foldr (\_ acc -> 1 + acc) 0
再次，Haskell 知道 foldr 的第二个和第三个参数（累加器和列表）中的哪一个被视为因变量和自变量，这似乎是魔术。但是不，我确信答案在于类型声明（我无法破译，因此，这个 post），以及 lambda 演算的知识，我是初学者。
更新
我找到了这个
reverse = foldl (flip (:)) []
然后申请一个列表
foldl (flip (:)) [] [1,2,3]
foldl (flip (:)) (1:[]) [2,3]
foldl (flip (:)) (2:1:[]) [3]
foldl (flip (:)) (3:2:1:[]) []
. . .
这里很明显顺序是“累加器”，然后是列表，而flip是翻转第一和第二个变量，然后对它们进行(:)。同样，这
reverse = foldl (\acc x -> x : acc) []
foldl (\acc x -> x : acc) [] [1,2,3]
foldl (\acc x -> x : acc) (1:[]) [1,2,3]
. . .
似乎也依赖顺序，但在上面的示例中
length' = foldr (\_ acc -> 1 + acc) 0
foldr (\_ acc -> 1 + acc) 0 [1,2,3]
它怎么知道 0 是累加器并且绑定到 acc 而不是第一个（幽灵）变量？因此，据我所知（前五页）lambda 演算，任何“lambda'd”变量，例如 \x 都是因变量，所有其他非 lambda'd 变量都是独立的。上面，\_ 与 [1,2,3] 相关联，表面上是自变量的 acc 是 0；因此，命令 不是 指示分配。就好像 acc 是某个关键字，在使用时总是绑定到累加器，而 x 总是在谈论传入的列表成员。
此外，t a 转换为 [a] 的类型定义中的“代数”是什么？这是范畴论的东西吗？我明白了
Data.Foldable.toList :: t a -> [a]
在Foldable定义中。就这些了吗？
好吧，foldr 本身就知道这一点。它的定义方式使其函数参数接受累加器作为第二个参数。
就像你写一个div x y = ...函数一样，你可以自由使用y作为分红。
也许您对 foldr 和 foldl 在累加器函数中交换了参数这一事实感到困惑？
“依赖”很可能是指 绑定 变量。
“独立”很可能是指自由（即未绑定）变量。
(\x n -> x + n)中没有自由变量。 x 和 n 都出现在箭头的左边，->，所以它们被命名为这个 lambda 函数的参数，bound inside its body , 在箭头的右边。被绑定意味着当这个 lambda 函数确实应用于它的参数时，在函数体中每个对 n 的引用都被替换为对相应 参数 的引用).
同样，_ 和 acc 都绑定在 (\_ acc -> 1 + acc) 的体内。此处使用 通配符 的事实无关紧要。我们完全可以写 _we_dont_care_。
lambda 函数定义中的参数“分配”（也称为“绑定”）应用程序中参数的值，纯粹是位置上的。第一个参数将被绑定/分配给第一个参数，第二个参数 - 到第二个参数。然后进入lambda函数体，按照规则进一步缩减。
这有点不同，说明实际上在 lambda 演算中所有函数都只有一个参数，而多参数函数实际上是嵌套的单参数 lambda 函数；并且该应用程序是左关联的，即嵌套在左侧。
这实际上意味着很简单
(\ x n -> x + n) 5 0
=
(\ x -> (\ n -> x + n)) 5 0
=
((\ x -> (\ n -> x + n)) 5) 0
=
(\ n -> 5 + n) 0
=
5 + 0
至于Haskell如何从类型签名中知道哪个是哪个，同样，函数类型中的类型变量也是位置的，第一个类型变量对应于第一个预期参数的类型，第二个类型变量到第二个预期参数的类型，依此类推。
它是所有纯位置。
因此，作为纯机械和谨慎替换的问题，因为根据 foldr 的定义，它认为 foldr g 0 [1,2,3] = g 1 (foldr g 0 [2,3]) = ... = g 1 (g 2 (g 3 0))，我们有
foldr (\x n -> x + n) 0 [1,2,3]
=
(\x n -> x + n) 1 ( (\x n -> x + n) 2 ( (\x n -> x + n) 3 0 ))
=
(\x -> (\n -> x + n)) 1 ( (\x n -> x + n) 2 ( (\x n -> x + n) 3 0 ))
=
(\n -> 1 + n) ( (\x n -> x + n) 2 ( (\x n -> x + n) 3 0 ))
=
1 + ( (\x n -> x + n) 2 ( (\x n -> x + n) 3 0 ))
=
1 + ( (\x (\n -> x + n)) 2 ( (\x n -> x + n) 3 0 ))
=
1 + (\n -> 2 + n) ( (\x n -> x + n) 3 0 )
=
1 + (2 + (\x n -> x + n) 3 0 )
=
1 + (2 + (\x -> (\n -> x + n)) 3 0 )
=
1 + (2 + (\n -> 3 + n) 0 )
=
1 + (2 + ( 3 + 0))
也就是说(\x n -> x + n)和(+)完全没有区别。
至于foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b中的那个t，意思就是给定一个类型T a，如果instance Foldable T存在，那么这个类型就变成foldr :: (a -> b -> b) -> b -> T a -> b，当它与 T a.
类型的值一起使用时
一个例子是 Maybe a，因此 foldr (g :: a -> b -> b) (z :: b) :: Maybe a -> b。
另一个示例是 [] a，因此 foldr (g :: a -> b -> b) (z :: b) :: [a] -> b。
(edit:) 所以让我们关注列表。函数 foo 具有该类型意味着什么，
foo :: (a -> b -> b) -> b -> [a] -> b
？这意味着它需要一个 a -> b -> b 类型的参数，即一个函数，我们称它为 g，这样
foo :: (a -> b -> b) -> b -> [a] -> b
g :: a -> b -> b
-------------------------------------
foo g :: b -> [a] -> b
它本身就是一个函数，需要一些 b 类型的参数 z，因此
foo :: (a -> b -> b) -> b -> [a] -> b
g :: a -> b -> b
z :: b
-------------------------------------
foo g z :: [a] -> b
它本身就是一个函数，需要一些 [a] 类型的参数 xs，因此
foo :: (a -> b -> b) -> b -> [a] -> b
g :: a -> b -> b
z :: b
xs :: [a]
-------------------------------------
foo g z xs :: b
给定一个列表，例如 [x]（即 x :: a、[x] :: [a]），这样的函数 foo g z 可以做什么？
foo g z [x] = b where
我们需要生成一个 b 值，但是怎么做呢？嗯，g :: a -> b -> b 产生一个函数 b -> b 给定类型 a 的值。等等，我们有！
f = g x -- f :: b -> b
它对我们有什么帮助？嗯，我们有z :: b，所以
b = f z
如果是 [] 怎么办？我们根本没有任何 as，但是我们有一个 b 类型值，z——所以我们只定义
而不是上面的
b = z
如果是 [x,y] 怎么办？我们将使用相同的 f 构建技巧，两次：
f1 = g x -- f1 :: b -> b
f2 = g y -- f2 :: b -> b
要生成 b，我们现在有很多选择：它是 z！或者，它是 f1 z!?或 f2 z？但是我们可以做的最一般的事情是所有我们可以访问的数据，是
b = f1 (f2 z)
获得对倍（......或者，
b = f2 (f1 z)
左 ).
如果我们代入并简化，我们得到
foldr g z [] = z
foldr g z [x] = g x z -- = g x (foldr g z [])
foldr g z [x,y] = g x (g y z) -- = g x (foldr g z [y])
foldr g z [x,y,w] = g x (g y (g w z)) -- = g x (foldr g z [y,w])
一种模式出现了。
等等等等等等
旁注：b 是一个糟糕的命名选择，这在 Haskell 中很常见。 r 会好得多——“递归结果”的助记符。
另一个助记符是 g 参数的顺序：a -> r -> r 暗示，不，指示，列表的元素 a 作为第一个参数出现； r 递归结果排在第二位（递归处理输入列表的其余部分的结果 -- 递归，因此以相同的方式);然后通过这个“步骤”函数生成总体结果，g.
这就是递归的本质：递归处理输入结构的自相似子部分，通过简单的一步完成处理：
a a
: `g`
[a] r
------------- -------------
[a] r
[a]
a [a]
--------
(x : xs) -> r
xs -> r
----------------------
( x , r ) -> r --- or, equivalently, x -> r -> r
正如 Steven Leiva 所说 here，foldr (1) 获取一个列表并用给定的函数替换缺点运算符 (:) 并且 (2) 替换最后一个空列表[] 与累加器种子，这就是 foldr 的定义所说的
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr _ z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
如此脱糖 [1,2,3] 是
(:) 1 ((:) 2 ((:) 3 []))
并且递归实际上是用 f 替换 (:)，正如我们在 foldr f z (x:xs) = f x (foldr f z xs) 中看到的那样，z 种子值正在运行直到它被替换为 [] 的基本情况，满足上面的 (1) 和 (2)。
我的第一个困惑是看到这个
foldr (\x n -> x + n) 0 [1,2,3]
并且不理解它会根据上面的定义扩展到
(\x n -> x + n) 1 ((\x n -> x + n) 2 ((\x n -> x + n) 3 0 ))
接下来，由于对实际的beta reduction如何进行了解不多，下面的第二步到第三步没看懂
(\x -> (\n -> x + n)) 1 ...
(\n -> 1 + n) ...
1 + ...
第二到第三步是 lambda 演算，虽然很奇怪，但它是 (+) 和 (\x n -> x + n) 是同一回事的根本原因。我不认为它是纯粹的 lambda 演算加法，但它（详细地）模仿递归中的加法。我可能需要跳回 lambda 演算才能真正理解为什么 (\n -> 1 + n) 变成 1 +
我最糟糕的心理障碍是认为我首先在括号内查看某种急切的评估
foldr ((\x n -> x + n) 0 [1,2,3,4])
foldr 的三个参数将首先交互，即 0 将绑定到 x，列表成员将绑定到 n
(\x n -> x + n) 0 [1,2,3,4]
0 + 1
。 . .然后我不知道该怎么想。完全错误的想法，尽管正如 Will Ness 上面指出的那样，beta 缩减是将参数绑定到变量的位置。但是，当然，我忽略了 Haskell currying 意味着我们首先遵循 foldr 的扩展这一事实。
我还没有完全理解类型定义
foldr :: (a -> b -> b) -> b -> [a] -> b
不同于comment/guess，第一个a和[a]表示a是传入列表成员的类型，(a -> b -> b) 是 foldr 将做的事情的初步缩影，即，它将接受传入列表类型的参数（在我们的例子中是列表的元素？）然后是另一个类型的对象 b 并生成一个对象 b。所以种子参数是 b 类型，整个过程最终会产生 b 类型的东西，给定的函数参数也将采用 a 并最终返回一个对象 b 实际上也可能是 a 类型，实际上在上面的例子中是整数...IOW，我对类型定义没有真正的把握...
给定
> foldr (+) 5 [1,2,3,4]
15
第二个版本
foldr (\x n -> x + n) 5 [1,2,3,4]
也returns15。关于第二个版本，我不明白的第一件事是 foldr 如何知道哪个变量与累加器种子 5 相关联，以及哪个变量与列表变量的元素 [1,2,3,4] 相关联。在 lambda 演算方式中，x 似乎是因变量，n 是自变量。所以如果这个
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr _ z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
是foldr和这些
:type foldr
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
:t +d foldr
foldr :: (a -> b -> b) -> b -> [a] -> b
它的类型声明，我可以收集，从类型声明本身推断出 “哪个是依赖的，哪个是独立的” 的答案吗？上面 foldr 的两个例子似乎都必须这样做
(+) 1 ((+) 2 ((+) 3 ((+) 4 ((+) 5 0))))
我只是猜到了上面的第二个lambda函数版本，但我不太明白它是如何工作的，而第一个带有(+)的版本分解如上所示。
另一个例子是这个
length' = foldr (const (1+)) 0
const 似乎知道“丢弃”传入的列表元素并简单地递增，从初始累加器值开始。这与
length' = foldr (\_ acc -> 1 + acc) 0
再次，Haskell 知道 foldr 的第二个和第三个参数（累加器和列表）中的哪一个被视为因变量和自变量，这似乎是魔术。但是不，我确信答案在于类型声明（我无法破译，因此，这个 post），以及 lambda 演算的知识，我是初学者。
更新
我找到了这个
reverse = foldl (flip (:)) []
然后申请一个列表
foldl (flip (:)) [] [1,2,3]
foldl (flip (:)) (1:[]) [2,3]
foldl (flip (:)) (2:1:[]) [3]
foldl (flip (:)) (3:2:1:[]) []
. . .
这里很明显顺序是“累加器”，然后是列表，而flip是翻转第一和第二个变量，然后对它们进行(:)。同样，这
reverse = foldl (\acc x -> x : acc) []
foldl (\acc x -> x : acc) [] [1,2,3]
foldl (\acc x -> x : acc) (1:[]) [1,2,3]
. . .
似乎也依赖顺序，但在上面的示例中
length' = foldr (\_ acc -> 1 + acc) 0
foldr (\_ acc -> 1 + acc) 0 [1,2,3]
它怎么知道 0 是累加器并且绑定到 acc 而不是第一个（幽灵）变量？因此，据我所知（前五页）lambda 演算，任何“lambda'd”变量，例如 \x 都是因变量，所有其他非 lambda'd 变量都是独立的。上面，\_ 与 [1,2,3] 相关联，表面上是自变量的 acc 是 0；因此，命令 不是 指示分配。就好像 acc 是某个关键字，在使用时总是绑定到累加器，而 x 总是在谈论传入的列表成员。
此外，t a 转换为 [a] 的类型定义中的“代数”是什么？这是范畴论的东西吗？我明白了
Data.Foldable.toList :: t a -> [a]
在Foldable定义中。就这些了吗？
好吧，foldr 本身就知道这一点。它的定义方式使其函数参数接受累加器作为第二个参数。
就像你写一个div x y = ...函数一样，你可以自由使用y作为分红。
也许您对 foldr 和 foldl 在累加器函数中交换了参数这一事实感到困惑？
“依赖”很可能是指 绑定 变量。
“独立”很可能是指自由（即未绑定）变量。
(\x n -> x + n)中没有自由变量。 x 和 n 都出现在箭头的左边，->，所以它们被命名为这个 lambda 函数的参数，bound inside its body , 在箭头的右边。被绑定意味着当这个 lambda 函数确实应用于它的参数时，在函数体中每个对 n 的引用都被替换为对相应 参数 的引用).
同样，_ 和 acc 都绑定在 (\_ acc -> 1 + acc) 的体内。此处使用 通配符 的事实无关紧要。我们完全可以写 _we_dont_care_。
lambda 函数定义中的参数“分配”（也称为“绑定”）应用程序中参数的值，纯粹是位置上的。第一个参数将被绑定/分配给第一个参数，第二个参数 - 到第二个参数。然后进入lambda函数体，按照规则进一步缩减。
这有点不同，说明实际上在 lambda 演算中所有函数都只有一个参数，而多参数函数实际上是嵌套的单参数 lambda 函数；并且该应用程序是左关联的，即嵌套在左侧。
这实际上意味着很简单
(\ x n -> x + n) 5 0
=
(\ x -> (\ n -> x + n)) 5 0
=
((\ x -> (\ n -> x + n)) 5) 0
=
(\ n -> 5 + n) 0
=
5 + 0
至于Haskell如何从类型签名中知道哪个是哪个，同样，函数类型中的类型变量也是位置的，第一个类型变量对应于第一个预期参数的类型，第二个类型变量到第二个预期参数的类型，依此类推。
它是所有纯位置。
因此，作为纯机械和谨慎替换的问题，因为根据 foldr 的定义，它认为 foldr g 0 [1,2,3] = g 1 (foldr g 0 [2,3]) = ... = g 1 (g 2 (g 3 0))，我们有
foldr (\x n -> x + n) 0 [1,2,3]
=
(\x n -> x + n) 1 ( (\x n -> x + n) 2 ( (\x n -> x + n) 3 0 ))
=
(\x -> (\n -> x + n)) 1 ( (\x n -> x + n) 2 ( (\x n -> x + n) 3 0 ))
=
(\n -> 1 + n) ( (\x n -> x + n) 2 ( (\x n -> x + n) 3 0 ))
=
1 + ( (\x n -> x + n) 2 ( (\x n -> x + n) 3 0 ))
=
1 + ( (\x (\n -> x + n)) 2 ( (\x n -> x + n) 3 0 ))
=
1 + (\n -> 2 + n) ( (\x n -> x + n) 3 0 )
=
1 + (2 + (\x n -> x + n) 3 0 )
=
1 + (2 + (\x -> (\n -> x + n)) 3 0 )
=
1 + (2 + (\n -> 3 + n) 0 )
=
1 + (2 + ( 3 + 0))
也就是说(\x n -> x + n)和(+)完全没有区别。
至于foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b中的那个t，意思就是给定一个类型T a，如果instance Foldable T存在，那么这个类型就变成foldr :: (a -> b -> b) -> b -> T a -> b，当它与 T a.
一个例子是 Maybe a，因此 foldr (g :: a -> b -> b) (z :: b) :: Maybe a -> b。
另一个示例是 [] a，因此 foldr (g :: a -> b -> b) (z :: b) :: [a] -> b。
(edit:) 所以让我们关注列表。函数 foo 具有该类型意味着什么，
foo :: (a -> b -> b) -> b -> [a] -> b
？这意味着它需要一个 a -> b -> b 类型的参数，即一个函数，我们称它为 g，这样
foo :: (a -> b -> b) -> b -> [a] -> b
g :: a -> b -> b
-------------------------------------
foo g :: b -> [a] -> b
它本身就是一个函数，需要一些 b 类型的参数 z，因此
foo :: (a -> b -> b) -> b -> [a] -> b
g :: a -> b -> b
z :: b
-------------------------------------
foo g z :: [a] -> b
它本身就是一个函数，需要一些 [a] 类型的参数 xs，因此
foo :: (a -> b -> b) -> b -> [a] -> b
g :: a -> b -> b
z :: b
xs :: [a]
-------------------------------------
foo g z xs :: b
给定一个列表，例如 [x]（即 x :: a、[x] :: [a]），这样的函数 foo g z 可以做什么？
foo g z [x] = b where
我们需要生成一个 b 值，但是怎么做呢？嗯，g :: a -> b -> b 产生一个函数 b -> b 给定类型 a 的值。等等，我们有！
f = g x -- f :: b -> b
它对我们有什么帮助？嗯，我们有z :: b，所以
b = f z
如果是 [] 怎么办？我们根本没有任何 as，但是我们有一个 b 类型值，z——所以我们只定义
b = z
如果是 [x,y] 怎么办？我们将使用相同的 f 构建技巧，两次：
f1 = g x -- f1 :: b -> b
f2 = g y -- f2 :: b -> b
要生成 b，我们现在有很多选择：它是 z！或者，它是 f1 z!?或 f2 z？但是我们可以做的最一般的事情是所有我们可以访问的数据，是
b = f1 (f2 z)
获得对倍（......或者，
b = f2 (f1 z)
左 ).
如果我们代入并简化，我们得到
foldr g z [] = z
foldr g z [x] = g x z -- = g x (foldr g z [])
foldr g z [x,y] = g x (g y z) -- = g x (foldr g z [y])
foldr g z [x,y,w] = g x (g y (g w z)) -- = g x (foldr g z [y,w])
一种模式出现了。
等等等等等等
旁注：b 是一个糟糕的命名选择，这在 Haskell 中很常见。 r 会好得多——“递归结果”的助记符。
另一个助记符是 g 参数的顺序：a -> r -> r 暗示，不，指示，列表的元素 a 作为第一个参数出现； r 递归结果排在第二位（递归处理输入列表的其余部分的结果 -- 递归，因此以相同的方式);然后通过这个“步骤”函数生成总体结果，g.
这就是递归的本质：递归处理输入结构的自相似子部分，通过简单的一步完成处理：
a a
: `g`
[a] r
------------- -------------
[a] r
[a]
a [a]
--------
(x : xs) -> r
xs -> r
----------------------
( x , r ) -> r --- or, equivalently, x -> r -> r
正如 Steven Leiva 所说 here，foldr (1) 获取一个列表并用给定的函数替换缺点运算符 (:) 并且 (2) 替换最后一个空列表[] 与累加器种子，这就是 foldr 的定义所说的
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr _ z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
如此脱糖 [1,2,3] 是
(:) 1 ((:) 2 ((:) 3 []))
并且递归实际上是用 f 替换 (:)，正如我们在 foldr f z (x:xs) = f x (foldr f z xs) 中看到的那样，z 种子值正在运行直到它被替换为 [] 的基本情况，满足上面的 (1) 和 (2)。
我的第一个困惑是看到这个
foldr (\x n -> x + n) 0 [1,2,3]
并且不理解它会根据上面的定义扩展到
(\x n -> x + n) 1 ((\x n -> x + n) 2 ((\x n -> x + n) 3 0 ))
接下来，由于对实际的beta reduction如何进行了解不多，下面的第二步到第三步没看懂
(\x -> (\n -> x + n)) 1 ...
(\n -> 1 + n) ...
1 + ...
第二到第三步是 lambda 演算，虽然很奇怪，但它是 (+) 和 (\x n -> x + n) 是同一回事的根本原因。我不认为它是纯粹的 lambda 演算加法，但它（详细地）模仿递归中的加法。我可能需要跳回 lambda 演算才能真正理解为什么 (\n -> 1 + n) 变成 1 +
我最糟糕的心理障碍是认为我首先在括号内查看某种急切的评估
foldr ((\x n -> x + n) 0 [1,2,3,4])
foldr 的三个参数将首先交互，即 0 将绑定到 x，列表成员将绑定到 n
(\x n -> x + n) 0 [1,2,3,4]
0 + 1
。 . .然后我不知道该怎么想。完全错误的想法，尽管正如 Will Ness 上面指出的那样，beta 缩减是将参数绑定到变量的位置。但是，当然，我忽略了 Haskell currying 意味着我们首先遵循 foldr 的扩展这一事实。
我还没有完全理解类型定义
foldr :: (a -> b -> b) -> b -> [a] -> b
不同于comment/guess，第一个a和[a]表示a是传入列表成员的类型，(a -> b -> b) 是 foldr 将做的事情的初步缩影，即，它将接受传入列表类型的参数（在我们的例子中是列表的元素？）然后是另一个类型的对象 b 并生成一个对象 b。所以种子参数是 b 类型，整个过程最终会产生 b 类型的东西，给定的函数参数也将采用 a 并最终返回一个对象 b 实际上也可能是 a 类型，实际上在上面的例子中是整数...IOW，我对类型定义没有真正的把握...