In class I said that implementing foldr by using foldl was cheating and less fun. It turns out there are a couple of useful things that implementation brings out. I've added the following to the Project 5b write-up.

-- An alternative approach to implementing myFoldr is simply to reverse the third

-- argument and use myFoldl. To do that we also have to reverse the parameters of

-- the function given to myFoldl. It turns out that Haskell has a function that

-- does exactly that: flip. We will implement our own versions of both reverse and  

-- flip.

myFoldr' :: (a -> b -> b) -> b -> [a] -> b           

myFoldr' f accInit xs = myFoldl (myFlip f) accInit (myReverse xs)

-- The following is a naïve version of reverse. It’s naïve because (a) it is O(n^2)

-- and (b) it is not tail recursive.  It’s O(n^2) because the entire list must be

-- traversed to put each element at the end.

naiveReverse :: [t] -> [t]

naiveReverse [] = []

naiveReverse (x:xs) = naiveReverse xs ++ [x]

-- This is a more traditional approach to reversing a list: use an accumulator.

-- This version is tail recursive and is O(n).

myReverse1 :: [t] -> [t]

myReverse1 xs = myReverse1Aux [] xs

  where myReverse1Aux acc [] = acc

        myReverse1Aux acc (x:xs) = myReverse1Aux (x:acc) xs

-- But as long as we are using an accumulator, why not use foldl?

myReverse :: [t] -> [t]

myReverse xs = foldl (\acc x -> x:acc) [] xs

myFlip :: (a -> b -> c) -> (b -> a -> c)

myFlip f = \y x -> f x y