使用折叠使功能更优雅

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] 

基本上我有点理解折叠如何通过查看讲义。然而，在上下文中的折叠使我感到困惑，即使在咖啡因被删除的情况下！我如何逐步理解这个折叠？

Answer 1

让我们按照[8,10,12,1,2]的示例一步一步做。

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

与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工作

to为什么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)