Using folds to make a function more elegant

Question

I originally presented my function as a solution where myTakeWhile returns elements of (x:xs) as a list until it reaches an element which the function argument equates to false. After which another solution was presented, which is below.

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)

I'm having real trouble running through the fold step by step in my head, especially the counter-intuition of a right fold starting from the left side of the list in the tests I have tried below.

*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]

Fundamentally I somewhat understand how a fold works through looking at lecture notes. However the fold in context is confusing me, even with the currying removed! How do I go about understanding this fold step by step?

Answer 1

let's do it step by step with the example [8,10,12,1,2].

I assume you understand that you can think about a right-fold foldr f a xs by replacing : with `f` and [] with a in xs:

with 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]

how does foldr work

to see why foldr does the replacement you just have to remember the definition:

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

the trick is to think recursive (with induction):

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 }

expanded example

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)