PIH - ch7 - Higher-order functions 2/3

by @ardumont on 05 Jan 2013

For the first exercises, see this post.

curry/uncurry

Without looking at the standard prelude, define the higher-order library function curry that converts a function on pairs into a curried function, and, conversely, the function uncurry that converts a curried function with two arguments into a function on pairs.

Hint: First write down the types of the two functions.

curry

First the type:

A function that takes a pair as parameter and output something is typed: ((a,b) -> c) A currified function that takes 2 parameters and output something is typed: a -> b -> c Thus the final type:

curry :: ((a,b) -> c) -> a -> b -> c

Now the definition:

curry :: ((a,b) -> c) -> a -> b -> c
curry f = \x -> \y -> f (x,y)

Simpler

curry :: ((a,b) -> c) -> a -> b -> c
curry f x y = f (x,y)

Examples:

We need a function that takes a pair as parameter:

add :: Num a => (a,a) -> a
add (x,y) = x + y

Here is how is used the function add:

*Ch7_2> add (1,2)
3

Given that, a simple scenario to currify add is:

*Ch7_2> (curry add) 1 2
3
*Ch7_2> ((curry add) 1) 2
3

uncurry

Conversely, the uncurrified function's type:

uncurry :: a -> b -> c -> (a, b) -> c

Now the definition:

uncurry :: (a -> b -> c) -> (a, b) -> c
uncurry f = \ (x, y) -> (f x y)

Simpler

uncurry :: (a -> b -> c) -> (a, b) -> c
uncurry f (x, y) = f x y

*Ch7_2> add (1,2)
3
*Ch7_2> (curry add) 1 2
3
*Ch7_2> uncurry (curry add) (1,2)
3

unfold

A higher-order function unfold that encapsulates a simple pattern of recursion for producing a list can be defined as follows:
unfold p h t x | p x = []
               | otherwise = h x : unfold p h t (t x)
That is, the function unfold p h t produces the empty list if the predicate p is true of the argument, and otherwise produces a non-empty list by applying the function h to give the head, and the function t to generate another argument that is recursively processed in the same way to produce the tail of the list.

For example, the function int2bin can be rewritten more compactly using unfold as follows:
int2bin = unfold (== 0) (`mod` 2) (`div` 2)
Redefine the functions chop8, map f and iterate f using unfold.

chop8

Split a bits list into a list of 8-bits list.

Recall the definition of the chop8 function:

chop8 :: [Bit] -> [[Bit]]
chop8 [] = []
chop8 bits = take 8 bits : (chop8 (drop 8 bits))

Here is the 3 functions needed:

predicate: check if a list is empty, we can use the null function for that
head: we take 8 bits
tail: we drop 8 bits

Using unfold:

chop8 :: [Bit] -> [[Bit]]
chop8 = unfold null (take 8) (drop 8)

map f

Map a function f to a list

Recall the recursive definition of map:

map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x:(map f xs)

From this we deduce the 3 needed functions:

predicate: check if a list is empty
head: f . head (first extracting head, then applying f to it)
tail: extracting the tail, tail.

map :: (a -> b) -> [a] -> [b]
map f = unfold null (f . head) tail

*Ch7_2> map (+1) [1,2,4]
[2,3,5]
*Ch7_2> map even [1,2,4]
[False,True,True]
*Ch7_2> map int2bin [1,2,4,8,16]
[[1],[0,1],[0,0,1],[0,0,0,1],[0,0,0,0,1]]

iterate f

lazy and infinite iteration over f=

A recursive definition of iterate can be:

iterate :: (a -> a) -> a -> [a]
iterate f x = x : iterate f (f x)

Example:

*Ch7_2> take 10 (iter (+1) 10)
[10,11,12,13,14,15,16,17,18,19]

Given this, here are the needed functions:

predicate: we want an infinite function, so a function that takes a parameter and returns False, (\ _ -> False) is a good default
head: as we always return false, we'll never pass here, so identity is a good shot
tail: at last, it's where all the work is done, we want f to be applied

iterate :: (a -> a) -> a -> [a]
iterate f = unfold (\ _ -> False) id f

Note I discovered the function const So we can replace this definition by this one:

iterate :: (a -> a) -> a -> [a]
iterate f = unfold (const False) id f

Example:

*Ch7_2> take 10 (iterate (+2) 0)
[0,2,4,6,8,10,12,14,16,18]