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

Ex. 9.9.

I banged my head against this exercise on fix for far too long.

I've confused myself enough times trying to understand “The Why of Y” paper that I have this silly idea that fixed point combinators (if that's the right terminology) are somehow hard

I don't think that setting the question with the hint “(This is tricky!)“ and then expecting your student to work out recursion using fix by themselves is really good pedagogic practise.

quicksilver on #haskell showed his charitable nature in two ways:

Firstly, by suggesting that perhaps Hudak is expecting the teacher using the workbook to explain the details. (I on the other hand had by this point vowed to track down the author and give him a damn good spanking.)

Secondly, he very kindly took some time to explain to me.

I'd noticed that the whole thing expands to an infinite sequence:

  > fix f = f $ f $ f ... (fix f)

and he pointed out the similarity between

  > ones = 1 : ones
  > ones = fix (1:)

and in fact, now that I have my ghci handy, I can indeed confirm that:

  > *Main> take 10 $ fix (1:)
  > [1,1,1,1,1,1,1,1,1,1]

He pointed out that I could pass the function as a parameter to the fixed subroutine. I sort-of-knew this, in that I remember reading it from WhyOfY, but I hadn't managed to get it compile. Tonight I modified what I'd written to:

  > remain f a b = if a < b then a
  >                else f (a-b) b

(I'd had f f (a-b) b for some reason). And that works:

  *Main> (fix remain) 10 3
  1

Now, given that Haskell already has recursion and this adds no power or expressivity, and actually just adds noise (the f parameter) and confusion (Huh? How does that even work), I can't see any possible use for this apart from that it's awfully clever. But, though I no longer feel like crying I should probably try to unfold what's happening.

  *Main> :t fix
  fix :: (t -> t) -> t

As I pointed out, this could be better written as

  fix :: ((a->b) -> (a->b)) -> (a->b)

to make it clear that we're fixing a function (except, apparently, you can fix other things too). So fix is passed a function remain which has type

  *Main> :t remain
  remain :: (Num a, Ord a) => (a -> a -> a) -> a -> a -> a

Meh. I'm lost again. Let's try to unroll it.

  > remain f a b = if a < b then a
  >                else f (a-b) b

So

  fix remain = remain (fix remain)

If we were evaluating eagerly that would expand to

  fix remain = remain (remain (remain (remain (... fix remain)

But for now it'll stay unexpanded. So.

  (remain (fix remain)) 10 3
  => (fix remain) (10-3) 3
  =>    (remain (fix remain)) 7 3
  =>    (fix remain) (7-3) 3
  =>       (remain (fix remain) 4 3
  =>       (fix remain) 1 3 
  =>       1

OK. When you expand that lazily, it looks far less insane. I think the visual insanity of

   > fix f = f (fix f)

which suggests that the two are equivalent and that it would therefore have to magically find the right value of (fix f) for which an equivalence would hold, really puts you off.

Update: rereading the wikipedia article on fixed point combinators, I liked one part where they compared a fixed point of a simple function, which is a value: like 0 is for add, or 1 is for multiplication. Well, the fixed point for a recursive function isn't a simple value, but another function. I'd originally looked at the definition as if it was an equation, and gone momentarily bonkers thinking “How does Haskell know which value to put in there to make it true!”

I'm going through one of those Blub moments where I just want to dismiss whole swathes of functional programming (in this case, fixed point combinators) as useless and annoying. I guess that's interesting and something to watch out for (I have a sneaky suspicion I will feel like this about plenty of other things along the way.)

(That said, I'd still say that this exercise has no place in that chapter, and probably no place in an introductory textbook at all.)

Later...

Ex. 9.10. Rewrite the expression as a composition of sections

  > map (\x -> (x+1)/2) xs

First we add the one, then we divide. However the dot doesn't work left-to-right like a pipeline, remember the type-signature Hudak offers is

  > (.)   :: (b->c) -> (a->b) -> a -> c

So it should be

  > map ((/2) . (+1)) xs

Ex. 9.11. Rewrite a nested map using function composition

  > map f (map g xs)

Every element is first mapped with g, and then has f applied. So this should be the same as

  > map (f.g) xs

While testing, I still find it odd that a->b->c (alphabetically incrementing) are ordered sequentially too, while f.g is actually applied the wrong way (it ‘should’ be g.f I think).

Now we are supposed to rewrite the earlier example as a map of a map.

  > map ((/2) . (+1)) xs
  > map (/2) (map (+1) xs) -- using the equivalence above

Ex. 9.12. Go back to any exercises prior to this chapter and simplify your solutions with the ideas learned here.

Here's an example from Chapter 7:

  > treeHeightF :: Tree a -> Integer
  > treeHeightF = treeF (const 0) maxPlusOne
  >     where maxPlusOne x y = 1 + max x y

The repeated x y cries out to be simplified. And with a bit of composition, this seems to work > treeHeightF :: Tree a -> Integer > treeHeightF = treeF (const 0) maxPlusOne > where maxPlusOne = max . (1+)

Er, right. That compiles, but I don't understand why, and I have a feeling it may be wrong.

    *> let maxPlusOne x y = 1 + max x y
    *> let maxPlusOne'    = max . (1+)
    *> maxPlusOne 0 0
    1
    *> maxPlusOne 0 1
    2
    *> maxPlusOne' 0 0
    1
    *> maxPlusOne' 0 1
    1 <--- this is wrong!

OK, so that didn't work. I think my original intuition was correct, and it should have been

    *> let maxPlusOne'    = (1+) . max

Except that max takes Ord, while (1+) takes Num. I end up trying to make a version of max that takes Num like so:

  > max' :: (Num a) => a -> a -> a
  > max' x y = max x y

but it doesn't like that. Looking for the diagram in chapter 12 (page 156 in my edition of the book), I see that Num doesn't extend Ord, only Real does. Bah. After lots of faffing about with trying to impose a type of Real in various flailing-about ways, one of the errors vaguely suggests to me that the problem is with the 2 parameters. And in fact

  > treeHeightF :: Tree a -> Integer
  > treeHeightF = treeF (const 0) maxPlusOne
  >     where maxPlusOne x = (1+) . max x

actually compiles. Though that can hardly be said to be simpler (a maximum is necessarily of 2 arguments, proposing only 1 is just odd).

This doesn't seem to have worked very well. I'm aware that some of my exercises used the “points free” style alreay and, yes, in some cases its usage is intuitive. But, if you'll permit another Blub moment, sometimes it's just bloody-minded obfuscation to define a function without making obvious what parameters it takes!

I feel a bit guilty about not proceeding with this exercise, given that the example above didn't really work out. But I suppose the “rules” that I'm realising I'm working to are as follows:

• I will attempt every question
• I do not need to succeed in every question
• I don't need to understand every concept (this is an important principle in life and learning I think. Sometimes you just have to say, “OK, I don't understand Monads/fix/whatever, but I'll just let it slide for now and come back to it later”
• Obviously, if I go through a chapter and fail to answer any question or understand any concept, then I will have to make the decision to either skip and come back to later, or to go over it again. I'll make a judgement call at the time which path to take.