PIH - ch7 - Higher-order Functions 1/3

by @ardumont on 05 Jan 2013

In this chapter were described:

higher-order functions

No difference exists between a value and a function, thus permitting a function to either manipulate other functions, either returning another function (or both).

composition of functions

As in mathematics, a function can be composed of multiple other functions.

foldr definition:

It's a basic function that represents a recursion pattern that's associative to the right.

foldl definition

It's another basic function representing another recursion pattern associative to the left.

In this post, I'll first give my solutions for the first 5 exercises of the chapter.

Higher-order functions

Show how the list comprehension [ f x | x ← xs, p x ] can be re-expressed using the higher-order functions map and filter.

What does the list comprehension do?

filter all elements from xs according to the predicate p
then apply f on the remaining elements

fmap0 :: (a -> a) -> (a -> Bool) -> [a] -> [a]
fmap0 f p xs = [ f x | x <- xs, p x]

Here is an example with:

(+1) as the function f,
even as the predicate p
[1..10] as the list xs

*Ch7> fmap0 (+1) even [1..10]
[3,5,7,9,11]

With the preceding definition, we can indeed write the same definition using map and filter:

fmap1 :: (a -> a) -> (a -> Bool) -> [a] -> [a]
fmap1 f p xs = map f (filter p xs)

Using the same example:

*Ch7> fmap1 (+1) even [1..10]
[3,5,7,9,11]

Define HOF

Without looking at the definitions from the standard prelude, define the higher-order functions all, any, takeWhile, and dropWhile.

all

Check that given a predicate and a list of elements, all the elements satisfies this predicate.

Recall the and function:

and :: [Bool] -> Bool
and = foldl (&&) True

So composing the mapping of the predicate p to the and function will do the trick.

all :: (a -> Bool) -> [a] -> Bool
all p = and . map p

Example:

*Ch7> all even [1,2,4]
False
*Ch7> all even [0,2,4]
True

any

Check that given a predicate and a list of elements, at least one of those elements satisfies this predicate.

any :: (a -> Bool) -> [a] -> Bool
any p = or . map p

*Ch7> any odd [0,2,1]
True
*Ch7> any odd [0,2,4]
False

takeWhile

Given a predicate and a list of elements, take those elements as long as the predicate is satisfied.

takeWhile :: (a -> Bool) -> [a] -> [a]
takeWhile _ [] = []
takeWhile p (x:xs) | p x       = x : takeWhile p xs
                   | otherwise = []

Examples:

*Ch7> takeWhile even [0,2,3,4,5,6]
[0,2]
*Ch7> takeWhile even []
[]

dropWhile

Given a predicate and a list of elements, drop those elements as long as the predicate is satisfied.

dropWhile :: (a -> Bool) -> [a] -> [a]
dropWhile _ [] = []
dropWhile p (x:xs) | p x        = dropWhile p xs
                    | otherwise  = x : xs

Examples:

*Ch7> dropWhile odd [1,3,5,7,0,2,3,4,5,6]
[0,2,3,4,5,6]
*Ch7> dropWhile odd []
[]

map, filter

Redefine the functions map f and filter p using foldr.

map

The recursive definition of map follows the recursive pattern that foldr represents.

Here is the definition of map using recursion:

mrmap :: (a -> a) -> [a] -> [a]
mrmap _ [] = []
mrmap g (x:xs) = f x:(mrmap g xs)

Recall the definition of foldr:

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

Following this, we can define map using foldr like this:

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

Example:

*ch7> map even [1,2,3]
[False,True,False]
*Ch7> map (*3) [1,2,3]
[3,6,9]

filter

The same way, here is the definition of filter using recursion:

mfilter :: (a -> Bool) -> [a] -> [a]
mfilter p xs = [x | x <- xs, p x]

Then:

filter :: (a -> Bool) -> [a] -> [a]
filter p = foldr (\ x xs -> if (p x) then x : xs else xs) []

dec2int

Using foldl, define a function dec2int :: [ Int ] → Int that converts a decimal number into an integer.

For example:
> dec2int [2, 3, 4, 5]
2345

Given a list of int [d,c,b,a] representing a 4-digit number, a decimal conversion can be rewritten like this:

[d, c, b, a]
1000 * d + 100 * c + 10 * b + 1 * a
(100 * d + 10 * c + b) * 10 + a
(((10 * d + c) * 10) + b) * 10 + a
((((d + 0) * 10 + c) * 10) + b) * 10 + a

What do we see from this:

It's associative to the left.
The initial value is 0.
The pattern we see is x * 10 + y

Indeed, we can then use foldl to define dec2int:

dec2int :: [Int] -> Int
dec2int = foldl (\ x y -> x * 10 + y) 0

Example:

*Ch7> dec2int [2,3,4,5]
2345
*Ch7> dec2int [9,8,7,5,3,0]
987530

Invalid definition

Explain why the following definition is invalid:
sumsqreven = compose [sum, map (↑2), filter even]=

Recall the definition of the compose function:

compose :: [a -> a] -> (a -> a)
compose = foldr (.) id

The signatures of the functions in the problem:

sum         :: [Int] -> Int
map (^2)    :: [Integer] -> [Integer]
filter even :: [Integer] -> [Integer]

Because of the sum function, the signatures of the list does not match the one of compose.

For it to work, we must separate the sum from the other function:

sumsqeven :: [Integer] -> Integer
sumsqeven = sum . (compose [map (^2), filter even])

Example:

*Ch7> sumsqeven [1..10]
220
*Ch7> sumsqeven [0,1,2]
4