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.

  I asked on irc and had a few good answers, or rather questions, such as
  “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.

Update: I discussed on #haskell, the suggestion was made that
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
already defined, so this answer might not be to specification.

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!)