«
»

foldr Starts at the Head

It took me long enough to realize that foldr still moves from the beginning to the end of a list. Somehow I thought it started at the right (i.e. the tail) of the list. Once I realized that Exercise 7 was easy:

Write your own definition of the standard takeWhile function, first using explicit recursion, and then foldr.

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

fMyTakeWhile :: (a -> Bool) -> [a] -> [a]
fMyTakeWhile f (xs) = foldr step [] xs
     where step x ys | f x = x : ys
                     | otherwise = []
«
»

This entry was posted on Wednesday, January 21st, 2009 at 11:03 PM and is filed under Haskell. You can follow any responses to this entry through the Atom feed. You can skip to the end and make a comment. Pinging is currently not allowed.

One Response to “foldr Starts at the Head”

  1. Leif Warner Says:
    May 10th, 2009 at 11:31 PM

    foldr does move from the end of the list to the beginning.
    foldr f x [1..5] = f 1 (f 2 (f 3 (f 4 (f 5 x)))),
    while
    foldl f x [1..5] = f (f (f (f (f x 1) 2) 3) 4) 5
    You can see a difference using scanl or scanr, which leave a trail of their steps:
    scanl1 (+) [1..10] = [1,3,6,10,15,21,28,36,45,55]
    scanr1 (+) [1..10 = [55,54,52,49,45,40,34,27,19,10]
    Even though the end result is the same (55), the intermediate numbers are different because the operation was started from different ends.
    The reason foldr (:) [] is an identity operation on lists is because lists are created by starting at the end and appending items to the head.

Leave a Reply