使用摺疊使功能更優雅

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)