[Haskell-cafe] Foldr tutorial, Inspired by Getting a Fix from a Fold

[Chris Moline]

I hope the following doesn't come across as
condescending...

The recent issue of The Monad Reader has generated
some excitement, mostly to do with the time travel
article. I, however, would like to discuss a simpler
solution to implementing dropWhile with foldr, which
is discussed in the first article of TMR.

When I was taught about folds, I was told that foldr
starts at the end of the list and then builds up the
result from there. But this turns out to be an
unhelpful way of thinking. It's better to say foldr
starts at the beginning of the list, just like foldl.
But how does this work? To see, we'll start by
implementing a simpler function than dropWhile, one
which determines whether we should cons an element
onto a list or just return the list.

dropHead p x xs = if p x then xs else x:xs

Note that I've funnily given a separate arg to the
head of the list and to its tail. That's not a typo
and later we will see why.

Now let's apply dropHead to each element of the list
[1, 2, 3, 4, 5]:

map (dropHead p) [1, 2, 3, 4 ,5] =>
[dropHead p 1,
 dropHead p 2,
 dropHead p 3,
 dropHead p 4,
 dropHead p 5]

Now we need to figure out where to get the second
argument for each of the dropHead applications. I
know! If a call to dropHead comes before another call
to dropHead, we'll pass the result of the second call
as the second arg of the first. And if there are no
calls after a call to dropHead, we'll pass our base
case as the second arg to that call. Let's have a
look:

threadResults basec [] = basec
threadResults basec [f:fs] = f $ threadResults basec
fs

threadResults [] [dropHead p 1 ...] =
 dropHead p 1 $
 dropHead p 2 $
 dropHead p 3 $
 dropHead p 4 $
 dropHead p 5 []

Let's see it in action! First let's let our predicate
determine whether a value is less than three.

dropHead (< 3) 5 [] =
 if (< 3) 5 then [] else 5:[] => [5]
dropHead (< 3) 4 [5] =
 if (< 3) 4 then [5] else 4:[5] => [4, 5]
dropHead (< 3) 3 [4, 5] =
 if (< 3) 3 then [4, 5] else 3:[4, 5] => [3, 4, 5]
dropHead (< 3) 2 [3, 4, 5] =
 if (< 3) 2 then [3, 4, 5] else 2:[3, 4, 5] => [3, 4,
5]
dropHead (< 3) 1 [3, 4, 5] =
 if (< 3) 1 then [3, 4, 5] else 1:[3, 4, 5] => [3, 4,
5]
=> [3, 4, 5]

Do you now see how foldr works? It starts at the
beginning of the list and applies the function you
gave it to the first element of the list. Then to get
the second argument of the first call, it applies your
function to the second element of the list and passes
the result of that to the first call. In other words,
it /recurs/ on the next element of the list. When we
finally get to the end, the base case is passed to the
final call of your function and it returns, and all
the previous calls return building their results from
the calls after.

So in other words to implement dropWhile with foldr
merely requires:

dropHead p x xs = if p x then xs else x:xs
dropWhile p l = foldr (dropHead p) [] l

Or even simpler:

dropWhile p = foldr (\x l' -> if p x then l' else
x:l') []

take 3 $ dropWhile (< 5) [1..]
=> [5, 6, 7]

No abtruse machinery required!

__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com