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.