### 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.