# Chapter 5: Polymorphic and Higher-Order functions

This is an interesting chapter, working on the higher order functions
rather than actually drawing shapes.

It covers:

• Polymorphic types
• Principal type – this is an interesting idea, the type inferencer can
determine that something works on an Int, say, or â€œNumber stuffâ€, or
â€œjust any stuffâ€, or â€œa list of stuffâ€. Too general and it's no longer
useful. The principal type is the most general type determinable for
the function that is still useful.
• map, yay! (OK, so Perl isn't well known as a functional
programming language, though see Dominus's Higher Order Perl,
but at least map and grep (filter I think in
Haskell) are well within my comfort zone.
• This is quite cute: sequence_ (map aux css). i.e. you
can use map for actions too.
• Implementing â€œappendâ€ – fixity is important consideration, e.g. whether
left associative or right associative
• One of the things that always baffled me with the definition of
fold was why you needed an init argument at all. It
just seems clumsy to be doing foldl (*) 1 or foldl (+)
0
when you could just use the first item of the list and get the
same result.

â€œWhat do you do with the empty list?â€ and â€œWhat happens when they're
different types?â€ (Note in fact that there are potentially two types,
a and b.

` *Five> :t foldl foldl :: (a -> b -> a) -> a -> [b] -> a`

But in fact there is a version that takes the first
element, called foldl1.

One of the nice things I'm beginning to discover about fold is that you
can use the init argument as a sort of accumulator, for example
[], I think I have examples of this a bit later.

• The extended example of how to implement reverse example is
nice. I found it quite tricky to read at first, but following
through it, it begins to make sense.
• Error handling (briefly)
• I like the definitions for (&&), (||) :: Bool -> Bool -> Bool

### Ex 5.1 Rewrite the equation for the area of a polygon given in Section 2.2. in a higher-order, nonrecursive way, using operators such as map, fold, and so on.

Obviously â€œnon-recursiveâ€ really means without explicit recursion
(although I suppose once you have abstracted it that way, the
implementation could choose to do the mapping non-recursively
as an optimization).

The original was like this:

``` >  -- this is the original function from section 2.2 >  area_orig (Polygon (v1 : vs)) = polyArea vs >      where polyArea                 :: [Vertex] -> Float >            polyArea (v2 : v3 : vs') = triArea v1 v2 v3 >                                        + polyArea( v3 : vs') >            polyArea _               = 0
```

I mutated it into a version using a fold (in the form of sum),
but then I got stuck and had to invent my own higher order function,
map2, which iterates 2 list items at a time.

``` >  import Shape > >  map2 :: (a -> a -> a1) -> [a] -> [a1] >  map2 f (a1 : a2 : as) = (f a1 a2) : map2 f (a2 : as) >  map2 _ _              = [] > >  area_new (Polygon (v1 : vs)) >      = let doTri v2 v3 = triArea v1 v2 v3 >        in sum \$ map2 doTri vs
```

Thinking that maybe I should try using just functions that have been
mentioned up until now, I tried the same using zip (of vs and
tail vs), which is a cute trick I read later in the book I think…
I had the lovely experience of writing the algorithm in Haskell as fast
as I could think, and it working first time!

``` >  area_new2 (Polygon (v1 : vs)) >      = let doTri (v2, v3) = triArea v1 v2 v3 >        in sum \$ map doTri \$ zip vs (tail vs)
```

### Ex 5.2 What is the principal type of each of the following expressions

• map map
• foldl foldl
• map foldl

I don't really understand this. I know that â€œmap mapâ€ returns a
new curried function, but we haven't covered that yet, and I'm
a bit baffled.

```    > :t map    map :: (a -> b) -> [a] -> [b]
```

In â€œmap mapâ€, the first map takes a function which is map, which goes
from (a->b) to [a]->[b]. So

`    -- On writing this up properly, I don't even understand what     -- the following snippets were trying to get at...    map map :: ((a->b) -> ([a] -> [b])) -> ??    map (+1) \$ map (*2) [1,2,3]`

but no, we want

`    map map`

which means map a function that maps stuff over the argument.
This is making me crabby, so I tried it out:

`    *Five> :t map map    map map :: [a -> b] -> [[a] -> [b]]`

Ok, so this maps a list of functions (a->b) to a list of functions
([a]->[b]). Right now I feel like crying, I don't know what this is
for, I think this question is an unpleasant and confusing one in the
middle of some decent exercises. That, or I'm missing something
obvious. Either way, I'm giving up and moving on.

map upgrades a function (a->b) to being ([a]->[b]).

So,

```  >  map     ::  (a->b)  ->  ([a]->[b])  >  map map :: [(a->b)] -> [([a]->[b])]
```

OK. Right now, that isn't looking as impossible to understand as I'd
previously thought (though I'd still like to see an example of map
map
used in anger,) so let's look at the next one, â€œfoldl
foldlâ€

```  > foldl :: (a -> b -> a) -> a -> [b] -> a  > foldl foldl :: ?
```

OK, The following is trying to substitute a with
(a->b->a):

```  > foldl foldl :: ((a->b->a) -> b -> (a->b->a)) -> (a->b->a) -> [b] -> (a->b->a)
```

but that isn't the way we did it for map. First of all we
formatted the type in a way that it was recognizably the same as the
type of the expected function. And here's a thing

```  > foldl :: (a -> b -> a) -> a -> [b] -> a
```

doesn't match (a->b->a).

` *Five> :t foldl foldl <interactive>:1:6:    Couldn't match expected type `b -> [b]' against inferred type `[b]'    In the first argument of `foldl', namely `foldl'`

I'm not quite sure what this question was trying to get at in this case,
apart from beware of trick questions.

Let's try one more time with the last item, â€œmap foldlâ€.

```  > map       ::  (a->b)  ->  ([a]->[b])  > foldl     :: (a -> b -> a) -> (a -> [b] -> a)  > map foldl :: ?
```

Is it…

```  > map foldl :: [a->b->a] -> [a->[b]->a]  -- ?
```

Yes it is, callooh callay. Still, I would cut this exercise out, or move it
to a point in the text where it's clearer what to do with it.

### Ex 5.3. Rewrite the definition of length nonrecursively

My first thought on this is that you can sum 1 for each item in the
list, so

```  > length2 :: [a] -> Int  > length2 xs = sum \$ map (\x ->1) xs
```

But something which I finally understood about the init argument of
fold, that it's an accumulator means that you can do

```  > length3 xs = foldl (\acc _ -> acc+1) 0 xs
```

See, we're folding over the elements but not using them at all (hence
the _), the accumulator is doing all the work. I think that's
quite cute.

### Ex 5.4

Using the higher order functions that we've now defined, fill in the two
missing functions, f1 and f2, in the evaluation below so that it is
valid:

```  > f1 (f2 (*) [1,2,3,4]) 5 => [5,10,15,20]
```

f2 is likely to be a map:

`  (map (*) [1,2,3,4])    => [(1*), (2*), (3*), (4*)]`

so f1 is something like a reverse map

```  >  unmap (v:vs) x = (v x) : unmap vs x  >  unmap [] _     = []
```
`  *Five> unmap (map (*) [1,2,3,4]) 5   [5,10,15,20]`

Except that unmap (which is almost certainly defined in the Standard
Prelude with a better name/implementation) isn't one of the functions we

### Exercise 5.5.: define functions that do various things…

As these are easy questions, I just defined these at the ghci prompt:

`    *Five> let doubleEach xs = map (*2) xs    *Five> doubleEach [1,2,3]    [2,4,6]`
`    *Five> let pairAndOne xs = map (\x -> (x,x+1)) xs    *Five> pairAndOne [1,2,3]    [(1,2),(2,3),(3,4)]`
`    *Five> let addEachPair xs = map (\(a,b) -> a + b) xs    *Five> addEachPair [(1,2),(3,4),(5,6)]    [3,7,11]`

I love how you can pattern match on tuples, very cool.

### Ex 5.6. defined maxList that computers the maximum element of a list.

`  *Five> let maxList xs = foldl (\a b-> if a > b then a else b) 0 xs  *Five> maxList [6,7,5,8,4,9,2]`

Of course this won't work with negative numbers:

`  *Five> maxList [-6,-7,-5,-8,-4,-9,-2]  0`

We could use the first element of the list, but we need to manage the
case in which there is none (e.g., the empty list)

```  > maxList (v:vs) = foldl (\a b -> if a > b then a else b) v vs  > maxList []     = 0
```

Of course there's a nice function â€œmaxâ€ that does the same as that
lambda

```  > maxList (v:vs) = foldl max v vs  > maxList []     = 0
```

analogously

```  > minList (v:vs) = foldl min v vs  > minList []     = 0
```

but I guess at this point we'd want to abstract these similar functions.

```  > foldlf f base (v:vs) = foldl f v vs  > foldlf _ base _      = base  >  > maxList xs = foldlf max 0 xs  > minList xs = foldlf min 0 xs
```

Which is more or less the same as the standard foldl1 higher
order function, except that that one seems to just throw an exception in
the case of an empty list (which actually, when you think about it, does
make some sense – is the â€œmaximumâ€ of an empty list really 0?)

### Ex 5.7 Function to add â€œpointwiseâ€ elements of a list of pairs

`  *Five> let addPairsPointwise xs              = foldl (\(x1,y1) (x2,y2) -> (x1+x2, y1+y2)) (0,0) xs  *Five> addPairsPointwise [(1,2),(3,4),(5,6)]  (9,12)`

### Ex 5.8 Create an encryption function for frogs

``` >  incChar, decChar :: Char -> Char >  incChar c = toEnum \$ (fromEnum c) + 1 >  decChar c = toEnum \$ (fromEnum c) - 1 > >  encrypt, decrypt :: String -> String >  encrypt s = map incChar s >  decrypt s = map decChar s
```

Let's try this out:

`  *Five> encrypt "Hello Francine!"  "Ifmmp!Gsbodjof\""  *Five> decrypt "Ifmmp!Gsbodjof\""  "Hello Francine!"`

While I was playing around with this, I came across an interesting
oddity:

`  *Five> fromEnum 'x'  120  *Five> toEnum 120  120  *Five> toEnum \$ fromEnum 'x'  120`

The explanation seems to be that the last â€œ120â€œ isn't a common or garden
120:

`  *Five> :t 120  120 :: (Num t) => t  *Five> :t toEnum 120  toEnum 120 :: (Enum a) => a`

This is a â€œgeneric Enumâ€ of value 120. In fact, if we constrain the
type, we get â€˜xâ€™ as expected:

`    *Five> toEnum 120 :: Char    'x'`

Which is what's happening with the functions incChar and decChar above:
the typing sorts them out.

`  *Five> decChar 'x'  'w'`

If we commented the type:

`  -- incChar, decChar :: Char -> Char`

Then we get the unspecified Enum again:

`  *Five> decChar 'x'  119`

But

`  *Five> encrypt "Hello Francine!"  "Ifmmp!Gsbodjof\""`

still works! Because the string is still constrained. If we commented
that line too…

`  -- encrypt, decrypt :: String -> String`

Then we get

`  *Five> encrypt "Hello Francine!"  [73,102,109,109,112,33,71,115,98,111,100,106,111,102,34]`

I don't know why this idea tickles me so much, but I had fun playing
around with various other Enums like Bool

`  *Five> toEnum 0 :: Bool  False  *Five> toEnum 1 :: Bool  True  *Five> toEnum 2 :: Bool  *** Exception: Prelude.Enum.Bool.toEnum: bad argument`

### 5.9 define makeChange such that

`  makeChange 99 [5,1] => [19,4]`

We can assume that the coin denominations are in descending order, and
that the unit coin (of value 1) will always be present

This is just that bit tricky that I can't jump straight to the higher
order definition. So, the first, recursive version:

```  > makeChange :: Int -> [Int] -> [Int]  > makeChange amt denominations  >   = _makeChange amt denominations []  >     where   >       _makeChange :: Int -> [Int] -> [Int] -> [Int]  >       _makeChange amt (denom:ds) ans  >         = let num  = amt `quot` denom  >               left = amt `mod`  denom  >           in _makeChange left ds (ans ++ [num])  >       _makeChange 0 [] ans = ans  >       _makeChange _ _ _    >             = error "This shouldn't happen due to assumptions"
```

I like the idea of using a fold with an accumulator.
However, as we need to thread not just the current amount left, but also
the answer, I ended up using a tuple and the following, which I think
might be a little clumsy:

```  > makeChange :: Int -> [Int] -> [Int]  > makeChange amt denominations  >   = snd \$ foldl aux (amt, []) denominations  >     where  >       aux :: (Int, [Int]) -> Int -> (Int, [Int])  >       aux (amt, ans) d  >         = let num  = amt `quot` d  >               left = amt `mod`  d  >           in (left, (ans ++ [num]))
```

I wonder what the best way to do this would be.
Also note that the function doesn't work for cases where taking the most
of the current highest possible denomination is suboptimal. For example

`    12 [10,6,1]     => [1,0,2] -- what we get    => [0,2,0] -- the ideal`

however this kind of coin system is generally unusual, and I think the
answer would involve backtracking and is probably out of scope at this
point. (Maybe one to come back to though!)