写折叠作为折叠混淆

Question

我知道还有其他帖子,但我的情况略有不同.

我有一个执行任务的功能foldl,使用foldr.我有解决方案给我,但希望有助于理解.

foldlTest:: (b -> a -> b) -> [a] -> (b -> b)

foldlTest f xs = foldr (\x r b -> r (f b x))
                (\b -> b)
                xs

它被称为使用这样的东西:

foldlTest (-) [1,2,3] 10 = -4

---

我理解的第一件事是我的函数接受2个参数,但在上面的测试用例中给出了3个参数.这意味着10将参与我假设的lambda表达式.

1)是否10采取的地方b的b -> b？(那么b将是初始累加器值)

我不明白的是这(\x r b -> r (f b x))部分的作用.

2)每个变量的价值是多少？我对这个lambda函数非常困惑.

3)lambda函数究竟做了什么以及它与常规函数有什么不同foldr？

Answer 1

好吧,既然我们的常驻Haskell专家都没有加紧解释这个问题,我想我已经开始了.请大家,随时纠正你认为错误的任何事情,因为我真的只是在这里找到答案的方式,而且其本质上就是有点漫无边际.

首先,和Haskell一样,查看类型是个好主意:

Prelude> :t foldl
foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b

由于我们只对这里的列表感兴趣,而不是通用Foldable的,所以让我们专门研究:

foldl ::  (b -> a -> b) -> b -> [a] -> b

并与您给出的功能进行比较:

foldlTest:: (b -> a -> b) -> [a] -> (b -> b)

由于Haskell函数是curry,这是另一种说法->类型签名中的箭头是右关联的方式,因此最后一对括号是不必要的,所以这与:

foldlTest:: (b -> a -> b) -> [a] -> b -> b

与foldl上面的相比,我们看到它们是相同的,除了最后两个参数 - [a]和b- 已被翻转的事实.

所以我们已经可以观察到,虽然库函数foldl采用了折叠函数,一个启动累加器和一个折叠列表来生成一个新的累加器,但foldlTest版本采用了折叠函数,一个折叠列表和一个启动累加器,产生一个新的累加器.这听起来就像是完全相同的东西,但是如果我们现在重新引入我几步之前取出的那对括号,我们会看到,foldlTest以您所示的形式,可以将其视为:

获取折叠函数和列表,并生成一个函数b -> b,该函数描述了如何折叠列表将初始累加器转换为最终结果.

特别要注意的是,在这个公式中它返回的确实是一个函数.

所以现在我们已经准备好看看你见过的实际实现了:

foldlTest f xs = foldr (\x r b -> r (f b x))
                (\b -> b)
                xs

我会第一个承认这是相当复杂的,甚至是令人困惑的.和以前一样,让我们​​检查一下类型.

输入类型很简单.我们从上面的讨论中知道f有类型b -> a -> b,并且xs有类型[a].

好吧,那个lambda怎么样？让我们分阶段:

• 它需要3个参数,x,r并b按此顺序.
• 函数调用的结果是r (f b x).如果我们坐下来思考它,这已经告诉了我们很多!
• 首先,我们知道f有类型b -> a -> b,所以从f b x我们知道b有类型b和x类型a.
• 至于r,我们看到它必须是一个函数,因为它适用于f b x.我们知道后者有类型b(来自类型签名f).所以r有类型b -> c,对于一些类型c.
• 因此,我们复杂的lambda函数具有类型a -> (b -> c) -> b -> c,其中c某种类型我们还没有确定.
• 现在来了一个关键点.这个lambda被表示为函数的第一个参数(fold函数)foldr.因此d -> e -> e,对于某些类型d和类型,它必须具有类型e.
• 请记住函数是curry,虽然看起来lambda的签名需要3个参数,但我们可以通过重写将其减少到2 a -> (b -> c) -> (b -> c).这与我们所知道的签名完全匹配foldr,d等于a和e等于b -> c.

它我们专门foldr的签名,以便它接受这种类型的功能,我们发现它是:

foldr :: (a -> (b -> c) -> (b -> c)) -> (b -> c) -> [a] -> (b -> c)`

我们仍然不知道是什么c- 但我们不必再怀疑更长时间了.以上是针对越过列表的折叠签名aS,并产生一个函数从b到c.下一个foldr是类型的参数b -> c(由我们试图解释的实现)给出\b -> b.当然,这只是身份功能,而且至关重要的是它是从类型到自身的功能.所以b -> c类型实际上必须是b -> b,或者换句话说c就是一直相同b!

因此lambda必须具有以下类型:

a -> (b -> b) -> (b -> b)

它需要一个a和一个内同态b(这只意味着一个函数从b它自身),并返回另一个内同态b.这就是我们将a使用身份函数作为起点折叠s 列表的函数,以产生b -> b将实现我们所追求的左侧折叠的内同态.

对自己的上述类型的签名不给我们如何实现它,因为这么多的线索a,并b可以是任何东西.但是,我们确实有f与它们相关的函数- 回想它需要a b和a a,并产生一个b.鉴于(通过再次撤消currying),上面的函数需要我们,给定a一个b -> b函数,并且a b,生成另一个函数b,我只能看到两个非平凡的方法:

• 应用功能的b,然后应用f到a和结果.
• 适用f于a和b,然后应用b -> b函数的结果

这两个中的第二个正是你所询问的那个lambda,正如希望看到的那样显而易见.(第一个选项是写的\x r b -> f (r b) x.我真的不确定它会产生什么样的整体效果,虽然我没有想太多.)

我已经涵盖了很多方面,虽然它感觉比实际情况更多,因为我试图非常辛苦.回顾一下,在什么样foldlTest的功能确实是,给出一个列表aS和功能f :: b -> a -> b,产生一个功能b -> b是通过与身份功能出发,走从右到左沿列表,改变当前的功能内置r :: b -> b到一个发送b到r (f b x)- x :: a我们当前所在列表的元素在哪里.

这是一个相当算法的描述foldlTest.让我们试着看看它对实际列表的作用 - 不是具体的列表,而是让我们说一个3元素的列表[a1, a2, a3].我们从身份函数开始\b -> b,然后将其转换为:

• b -> f b a3(回想一下,r作为身份功能开始)
• b -> f (f b a2) a3(这只是将以前的函数替换为rinto \b -> r (f b x),a2现在扮演的角色x)
• b -> f (f (f b a1) a2) a3

我希望你现在可以看到这看起来非常像从左侧折叠具有相同功能的列表f.而且"看起来非常像",我的意思是它完全相同!(如果您之前没有看过或尝试过,请尝试写出连续的阶段,foldl f b [a1, a2, a3]然后您会看到相同的模式.)

再次道歉,这有点夸张,但我希望这给了你足够的信息来回答你提出的问题.不要担心,如果它让你的大脑受到一点伤害 - 它也是我的!:)