Chapter 9: More about Higher Order Functions (part 1)

I looked at chapter 8 in terror and ran to the (comparative) familiarity
of this chapter.

Currying

I remember a couple of years ago, when I was looking up Functional
Programming early on, I came across the idea that functional programming
languages didn't take multiple arguments, but returned a function at
each step. I think I scoffed slightly at this idea, which seemed as
ridiculous as the idea that my Dad tried to explain once, that Latin
didn't usually use personal pronouns.

But all of these funny looking function signatures like

 > makeChange :: Int -> [Int] -> [Int] > -- rather than > -- makeChange :: ( Int [Int] ) -> [Int]

begin to make sense in the concept of currying.

The explanation of the currying simplification, whereby

  > reverse xs = foldl revOp [] xs  >   where revOp acc x = x : acc

is by steps turned into

  > reverse = foldl (flip (:)) []

is instructive (and slightly terrifying. I mean, just look at that
definition!)

Ex 9.1 simplify a fragment of containsS

  > (Polygon pts) `containsS` p  >   = let leftOfList  = map isLeftOfp  >                         (zip pts (tail pts ++ [head pts]))  >         isLeftOfp p' = isLeftOf p p'  >     in and leftOfList

Immediate candidate for simplification is:

  >         isLeftOfp = isLeftOf p

so possibly

  > -- untested  > (Polygon pts) `containsS` p  >   = and $ map (isLeftOf p)   >               (zip pts (tail pts ++ [head pts]))

Ex 92. Show that flip (flip f) is the same as f

The definition of flip given was:

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

f is a function (a -> b -> c).

  flip (flip f) x y = (flip f) y x  flip f y x = f x y  flip (flip f) x y = f x y  -- so  flip (flip f) = f

Ex. 9.3. What is the type of ys?

    xs = [1,2,3] :: [Float]    ys = map (+) xs

I suppose we have to know what types the functions involved are:

  Prelude> :t map  map :: (a -> b) -> [a] -> [b]  Prelude> :t (+)  (+) :: (Num a) => a -> a -> a

(+) works on the same type o Num a. (+) on a single number will return
a function (Float -> Float), so the mapped version should be

  > ys :: [(Float -> Float)]

Let's check it out!

  Prelude> let xs = [1,2,3] :: [Float]  Prelude> :t  map (+) xs  map (+) xs :: [Float -> Float]

OK, so that's [Float -> Float], it seems that the parentheses aren't
needed here.

Ex. 9.4. Define a function applyEach

such that

  > applyEach [simple 2 2, (+3)] 5   > --                             => [14,8]where simple is defined
  > simple x y z = x * (y + z)
  > applyEach :: [a->b] -> a -> [b]  > applyEach (f:fs) a = f a : applyEach fs a  > applyEach []     _ = []

which is the definition I made for unmap in Chapter 5. But we
can do better than that. If we just swap the item and the list, we can
use map:

  > applyEach fs a = map apply fs  >     where apply f = f a

And of course, if we use the application operator, ($), we can
simplify that to

  > applyEach  fs a = map ($ a) fs

now, as we're swapping the order of parameters, it occurs to me we could
so something with flip:

  > applyEach    = flip applyEach'  > applyEach' a fs = map ($ a) fs

which can be simplified to:

  > applyEach    = flip applyEach'  > applyEach' a = map ($ a)

which is

  > applyEach = flip (\a -> map ($ a))

But I don't know if you can get rid of the remaining parameter somehow.

Ex. 9.5. Define a function applyAll

such that

  > applyAll [ simple 2 2, (3)] 5  > --                            => 20

Similarly I think this might be a fold. And it has to work such that
the input and output types are the same so

  > applyAll :: [a->a] -> a -> a

Because we're starting with the initial value, we don't plug it
into the apply lexical function, but rather use it as the init argument
to foldr.

  > applyAll fs a = foldr apply a fs  >     where apply f a = f a

Therefore, we can think of simplifying apply by currying:

  >     where apply f = f

and then I really want to do

  >     where apply =                    -- Error!

But funnily enough, that's a syntax error :-) As it happens, we can use
the application operator ($) just like above

  > applyAll fs a = foldr ($) a fs

Ooo!, and we can do this with a flip, like so

  > applyAll = flip . foldr ($)  -- dammit, that doesn't work  > applyAll = flip foldr ($)    -- neither does that, and it gives a                                 -- crazy type, that spans multiple                                 -- lines!  > applyAll = flip $ foldr ($)  -- Yay!  That's the one.

As you can see, machine gun debugging (inserting and removing operators
at random until things compile) is still a preferred technique…

Ah! But actually, though this gives the same result as before, I'm
a little doubtful

    *Main> applyAll [(+2), (*2)] 4    10

I'd expect it to be 4+2=6 *2=12. The problem will be the use
of foldr!

  > applyAll = flip $ foldl ($)

But this gives me an error!:

    Occurs check: cannot construct the infinite type: b = a -> b    Probable cause: `$' is applied to too many arguments    In the first argument of `foldl', namely `($)'    In the second argument of `($)', namely `foldl ($)'

I'm not sure what's going on here, apart from that it's an example of
what Hudak mentions about the choice between foldl and
foldr being about a) efficiency and b) sometimes one of the
options being “more defined” than the other.

Ex. 9.6. Which of these functions is more efficient?

  > appendr, appendl :: [a] -> [a] -> [a]  > appendr          = foldr (flip (++)) []  > appendl          = foldl (flip (++)) []

I'm not sure what this does, so instead of typing it into ghci I'm going
to try to work it out first.

  appendr [1,2] [3,4]    => foldr (flip (++)) [] [1,2] [3,4]

Er. Actually, no, I'm confused now. I think foldr op init vs
is expecting one further argument (vs), but appendr takes 2. So I try
in ghci and indeed it doesn't compile. If I comment the signature line,
then it does with the type signature:

  *Main> :t appendr  appendr :: [[a]] -> [a]

So let's try again:

  let <<++>> = (flip (++))  appendr [ [1,2], [3,4] ]    => foldr <<++>> [] [[1,2],[3,4]]    => [1,2] <<++>>   foldr <<++>> [] [[3,4]]    => [1,2] <<++>>   [3,4] <<++>> foldr <<++>> [] []     => [1,2] <<++>>   [3,4] <<++>> []     => [1,2] <<++>> ( []  ++  [3,4] )    => [1,2] <<++>> [3,4]    => [3,4]   ++   [1,2]     => [3,4,1,2]

Perhaps this would be clearer with 3 elements?

  appendr [ [1,2], [3,4], [5,6] ]    => [1,2] <<++>> ([3,4] <<++>> ([5,6] <<++>> []))    => [1,2] <<++>> ([3,4] <<++>> ([] ++ [5,6]))    => [1,2] <<++>> ([3,4] <<++>> [5,6])    => [1,2] <<++>> ([5,6] ++ [3,4])    => [1,2] <<++>> [5,6,3,4]    => [5,6,3,4] ++ [1,2]    => [5,6,3,4,1,2]
  appendl [ [1,2], [3,4], [5,6] ]    => (([] <<++>> [1,2]) <<++>> [3,4]) <<++>> [5,6]    => ([1,2] ++ []) <<++>> [3,4]) <<++>> [5,6]    => ([1,2] <<++>> [3,4]) <<++>> [5,6]    => ([3,4] ++ [1,2]) <<++>> [5,6]    => [3,4,1,2] <<++>> [5,6]    => [5,6] ++ [3,4,1,2]    => [5,6,3,4,1,2]

From the discussion in Chapter 5, we see that concatenating with (++)
takes time proportional to the number of elements in the left-hand list.
appendl repeatedly concatenates the left hand side of the list,
so should be slower. (Though in this case, appendr scores 0+2+4=6,
while appendl scores 2+2+2=6, which is equal).

Ex. 9.7. Define a function twice

  > (twice (+1)) 2 => 4

That's easy enough:

  > twice :: (a->a) -> a -> a  > twice op v = op (op v)

Now, what does twice twice do? I have no idea, given that
twice takes a function (a->a) while twice itself
isn't such a function. Or… maybe it is if you read it as
(a->a) -> (a->a).

Here, my notes show that I am confused, as I make notes such as “GRAAAH”
and “WTF?” as well as going through the (.) and ($) options again:

    *Main> :t twice twice    twice twice :: (t -> t) -> t -> t    *Main> :t twice $ twice    twice $ twice :: (t -> t) -> t -> t    *Main> :t twice . twice    twice . twice :: (t -> t) -> t -> t

The end result of this confusion was that twice op returns a
function of the same sort as required for twice, so twice
twice
should simply do the operation 4 times. And twice twice
twice
will do it 16 times.

what about “twice(twice twice)“ I would think that would be the same as
“twice twice twice”, and in fact it is (though perhaps there are
efficiency concerns again)

Ex. 9.8. define a function power

  > power (+2) 5 1 => 11
  > power :: (t->t) -> Integer -> t -> t  > power f n init  >     | n==1      = f init  >     | otherwise = f (power f (n-1) init)
  > twice :: (a->a) -> a -> a  > twice f = power f 2

Now, to define something useful… I suppose we can do multiplication,
though to be honest it seems a bit naff:

  > mult x y = power (+x) y 0

The second half of this chapter is quite tricky, and I'm tired, so I'm
going to break off here.