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:
-
iterate
has noisTheFinal
parameter, so in theunfold
function, it is likeisTheFinal
is just some function that always returns False, i.e. "every item is not the final item." Can you see how to useconst
for this? Can you see what function to pass as theisTheFinal
parameter? -
iterate
has nochange
parameter, so in theunfold
function, it is likechange
is just a function that does not change anything. Can you see how to useid
for this? Can you see what function to pass as thechange
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:
-
to change
unfold
tomap
, first pass alist
as theitem
parameter forunfold
.a.
item
becomeslist
,isTheFinal
becomes what?b.
item
becomeslist
,next
becomes what? -
the
change
function inside ofunfold
is a combinationchange
andhead
inside ofmap
function. We can combine functions like so:(\list -> change (head list))
. Now we can pass this lambda function as thechange
parameter to theunfold
function.