使用折叠使功能更加优雅

Question

我最初将我的函数作为一个解决方案提出,其中myTakeWhile将(x:xs)的元素作为列表返回,直到它到达函数参数等于false的元素.之后提出了另一种解决方案,如下所示.

myTakeWhile :: (a -> Bool) -> [a] -> [a] 
myTakeWhile p []     = []
myTakeWhile p (x:xs) = if p x then x : myTakeWhile p xs else []   

myTakeWhile :: (a -> Bool) -> [a] -> [a] 
myTakeWhile p (x:xs) = foldr (\x acc -> if p x then x : acc else []) [] (x:xs)

我在一步一步地在脑袋里跑步时遇到了麻烦,特别是在我在下面尝试的测试中从列表左侧开始的右侧折叠的反直觉.

*Assignment1a> myTakeWhile (\x -> x `mod` 2 == 0) [1, 2, 3, 4, 5]
[]
*Assignment1a> myTakeWhile (\x -> x `mod` 2 == 0) [8, 10, 12, 1, 2, 3, 4, 5]
[8,10,12]

从根本上说,我通过查看讲义来了解折叠是如何工作的.然而,即使在移除了currying的情况下,上下文也令我感到困惑!我如何逐步理解这个折叠？

Answer 1

让我们一步一步地用这个例子来做[8,10,12,1,2].

我想你明白,你可以想想一个右倍foldr f a xs更换:与`f`和[]用a在xs:

用f = \x acc -> if even x then x:acc else []:

myTakeWhile even [8,10,12,1,2]
= foldr f [] [8,10,12,1,2]
= foldr f [] (8:10:12:1:2:[])
{ replace the : with `f` and [] with [] }
= 8 `f` (10 `f` (12 `f` (1 `f` (2 `f` []))))
{ 2 is even so f 2 [] = 2:[] }
= 8 `f` (10 `f` (12 `f` (1 `f` (2:[]))))
{ 2:[] = [2] }
= 8 `f` (10 `f` (12 `f` (1 `f` [2])))
{ 1 is odd so f 1 [2] is [] }
= 8 `f` (10 `f` (12 `f` ([])))
{ ([]) = [] }
= 8 `f` (10 `f` (12 `f` []))
{ 12 is even so f 12 [] = 12:[] }
= 8 `f` (10 `f` (12:[]))
{ 12:[] = [12] }
= 8 `f` (10 `f` [12])
{ 10 is odd so f 10 [12] = 10:12 }
= 8 `f` (10:[12])
{ 10:[12] = [10,12] }
= 8 `f` [10,12]
{ 8 is odd so f 8 [10,12] is 8:[10,12] }
= 8:[10,12]
{ 8:[10,12] = [8,10,12] }
= [8,10,12]

怎么foldr工作

为什么foldr替换你只需要记住定义:

foldr _ a []     = a
foldr f a (x:xs) = f x (foldr f a xs) = x `f` (foldr f a xs)

诀窍是认为递归(带感应):

foldr f a []
{ definition }
a

foldr f b (b:bs)
{ definition foldr x <- b; xs <- bs }
= b `f` (foldr f a bs)
{ induction/recursion }
= b `f` { bs with : replaced by `f` and [] by a }

扩展的例子

foldr f a [b1,b2]
{ [b1,b2] = b1:b2:[] }
= foldr f a (b1:b2:[])
{ definition foldr x <- b1; xs <- b2:[]}
= b1 `f` (foldr f a (b2:[]))
{ definition foldr x <- b2; xs <- []}
= b1 `f` (b2 `f` (foldr f a []))
{ definition foldr empty case }
= b1 `f`(b2 `f` a)