unfold-to-map-and-iterate.md

Well I think you have made a wise decision to learn Haskell, but it is really unlike any programming language you have probably learned until now.

Lets first review what id and const do.

The id function is a function that doesn't change anything -- whatever you pass to it, the same value comes out unchanged. So id 5 equals 5, id False equals False id "hello" equals "hello", id () equals ().

The const function is a function that always returns the same value, no matter what you give to it. const 5 True equals 5, const 5 "hello" equals 5, const 5 () equals 5, no matter what, const 5 always returns 5.

Now, do you understand what the map and iterate do? The map function takes a list and a function and uses the function to modify each elements in the list with the function. For example:

list :: [Int]
list = [1, 3, 5, 7]

main :: IO ()
main = print $
    map (\x -> x - 1) list

The map function will subtract one from every item in list, so the result of this program will be [0, 2, 4, 6]. It is very easy to write the map function yourself:

map :: (a -> b) -> [a] -> [b]
map change list
    | null list = []
    | otherwise = change (head list) : map change (tail list)

The iterate function takes an element and and a function, applies the function to the element to produce the next list element, then repeatedly applies the function to the next list elements to create an infinite list. For example, to generate the list of all odd numbers you can write:

main = print $ take 100 $
    iterate (\x -> x + 2) 1

This will take the number 1, put it in the list, then add 1 + 2 = 3 and put the number 3 into the list, then add 2 + 3 = 5, and put the number 5 into the list, then add 2 + 5.... and will do that forever. The take 100 will limit the loop to 100 items.

The iterate function is also very easy to write by yourself:

iterate :: (a -> a) -> a -> [a]
iterate next item = item : iterate (next item)

So what do map and iterate have in common? Well for starters the are both recursive (they both calls themselves), but more importantly they both generate a list from an initial item and a function. The initial item of the map function's is a list like [1, 3, 5, 7] and the initial item of the iterate function is a single element like the number 1. Both functions take a function like (\x -> x - 1) or (\x -> x + 2).

The unfold function combines both map and iterator into a single function. We do this sometimes when writing Haskell programs, we start with a more general "higher order" function and then derive simpler functions from it. That is what this practice problem is doing , it is giving you unfold and asking you to derive the simpler map and iterate functions.

To review, the unfold function is defined as:

unfold :: (a -> Bool) -> (a -> b) -> (a -> a) -> a -> [b]
unfold isTheFinal change next item
    | isTheFinal item = []
    | otherwise       = change item : unfold isTheFinal change next (next item)

Take a close look at all three functions together:

map change list
    | null list = []
    | otherwise = change (head list) : map change (tail list)

iterate next item = item : iterate (next item)

unfold isTheFinal change next item
    | isTheFinal item = []
    | otherwise       = change item : unfold isTheFinal change next (next item)

Can you start to see the similarities? Maybe now you can start to guess how to derive map and iterate from unfold?

I think iterate might be easier to start with. How can we change this:

unfold isTheFinal change next item
    | isTheFinal item = []
    | otherwise       = change item : unfold isTheFinal change next (next item)

to this:

iterate next item = item : iterate (next item)

by only passing functions like id or const to the unfold function? Here are two hints:

1. iterate has no isTheFinal parameter, so in the unfold function, it is like isTheFinal is just some function that always returns False, i.e. "every item is not the final item." Can you see how to use const for this? Can you see what function to pass as the isTheFinal parameter?

2. iterate has no change parameter, so in the unfold function, it is like change is just a function that does not change anything. Can you see how to use id for this? Can you see what function to pass as the change parameter?

Now lets look at map. How can we change this:

unfold isTheFinal change next item
    | isTheFinal item = []
    | otherwise       = change item : unfold isTheFinal change next (next item)

to this:

map change list
    | null list = []
    | otherwise = change (head list) : map change (tail list)

by only passing functions to the unfold function?

Here are two hints:

1. to change unfold to map, first pass a list as the item parameter for unfold.

   a. item becomes list, isTheFinal becomes what?

   b. item becomes list, next becomes what?

2. the change function inside of unfold is a combination change and head inside of map function. We can combine functions like so: (\list -> change (head list)). Now we can pass this lambda function as the change parameter to the unfold function.