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.