I start off confidently, typing in the first example into my scratch

file:

> data Tree=Leaf a|Branch (Tree a) (Tree a)

Of course, ghci complains bitterly, and strangely

Prelude> :l 7.hs

[1 of 1] Compiling Tree ( 7.hs, interpreted )

7.hs:5:19: Not in scope: type variable `a'

7.hs:5:36: Not in scope: type variable `a'

7.hs:5:45: Not in scope: type variable `a'

Failed, modules loaded: none.

Eventually I realise I started off a little too confidently and left out

the parametrised variable…

> data Tree a=Leaf a|Branch (Tree a) (Tree a)

I'm trying to practise my syntax by reading the definitions of the

functions (`mapTree`, `fringe`) etc., and then writing

them out before compiling and checking in the book. As it happens I've

previewed them before, but at least this helps get the syntax into my

head!

I'm still finding the error messages hard to read:

7.hs:13:27:

Couldn't match expected type `a' (a rigid variable)

against inferred type `[a]'

`a' is bound by the type signature for `fringe' at 7.hs:11:19

In the expression: fringe x

In the first argument of `(++)', namely `[fringe x]'

In the expression: [fringe x] ++ [fringe y]

This is because the expression at the bottom should have been

fringe x ++ fringe y

as `fringe` already returns a list.

### Curried datatypes

I thought I'd test the functions and tried it out

*Tree> fringe t

<interactive>:1:7:

Couldn't match expected type `Tree a'

against inferred type `Tree Integer -> Tree Integer'

In the first argument of `fringe', namely `t'

In the expression: fringe t

In the definition of `it': it = fringe t

Which I thought was odd. Where was the `â€œTree Integer -> Tree
Integerâ€` coming from?

*Tree> :t t

t :: Tree Integer -> Tree Integer

I tried constraining the definition of my tree, `t`:

> t::Tree Integer

> t=Branch (Branch (Leaf 2) (Leaf 3))

Which of course gave a similar error, and I eventually realised that I'd

missed off the second branch…

>-- much better

> t=Branch (Branch (Leaf 2) (Leaf 3)) (Leaf 4)

What can I say, it's been a long day at work… Anyway, with a

structure like this I can play with the functions

*Tree> fringe $ mapTree (*2) t

[4,6,8]

### Ex 7.1 Look at the definitions of fringe and treeSize.

Are there commonalities that can be abstracted out, like they were

when we developed `fold`?

> fringe::Tree a->[a]

> fringe (Leaf x)=[x]

> fringe (Branch x y)=fringe x ++ fringe y

> treeSize::Tree a->Integer

> treeSize (Leaf _)=1

> treeSize (Branch x y)=treeSize x + treeSize y

I looked at this stupidly for some time thinking â€œBut the bit that

handles the leaf isn't the same function as the one that sums together

the branches!â€ and then eventually realised that modern functional

programming languages can probably handle more than one functional

argument…

I came up with

>-- a new Higher Order Function for trees??

> treeF::(a->b)->(b->b->b)->Tree a->b

> treeF f o (Leaf x)=f x

> treeF f o (Branch x y)=(treeF f o x) `o` (treeF f o y)

Which would then be used with functions like

> fringeF::Tree a->[a]

> fringeF=treeF list (++)

> where list x=[x]

> treeSizeF::Tree a->Integer

> treeSizeF=treeF one (+)

> where one _=1

which, incredibly, works! The formulation for treeHeight is a bit

uglier:

> treeHeightF::Tree a->Integer

> treeHeightF=treeF zero maxPlusOne

> where zero _=0

> maxPlusOne x y=1 + max x y

{

Parenthesis on const: I don't like having to create little lexical

stubs to give the literal 0 and 1 above. In Perl you would just do sub {1}

for example, which made be think of a lambda: (\_ -> 1) which is

hideous. Now if only there was a function that threw away one of its

arguments. I got as far as defining it*Tree> let _ & a = a

*Tree> map (&1) [2,3,4]

[1,1,1]when I remembered that I'd seen it in the prelude. It's a bit less

compact than my operator version, but it is calledâ€œconstâ€,

which makes sense. So now we can write> treeHeightF::Tree a->Integer

> treeHeightF=treeF (const 0) maxPlusOne

> where maxPlusOne x y=1 + max x y}

And, the definition of mapTree was written more intuitively than

rationally – I can barely believe that it works:

> mapTreeF::(a->b)->Tree a->Tree b

> mapTreeF f=treeF mapLeaf Branch

> where mapLeaf x=Leaf (f x)

See that?! The two things that absolutely blew me away were

- The function,
`f`is folded into the Branch calculation -

e.g. it didn't just do`Branch (mapTree x) (mapTree y)`, but

`(mapTree f x)`etc. I didn't*understand*this, but it

felt right, so I tried to compile it… - You can use the
`Branch`constructor as a function! Er, ok,

that might seem old hat if you know algebraic datatypes, but for some

reason I was pleased with that.

Anyway, the new functions work:

*Tree> fringeF $ mapTreeF (*2) t

[4,6,8]

### Exercise 7.2 takeTree and takeTreeWhile

Using the definition of InternalTree

> data InternalTree a=ILeaf

>|IBranch a (InternalTree a) (InternalTree a)

I came upon something like the following:

> takeTree::Int->InternalTree a->InternalTree a

> takeTree n (IBranch w x y)

>|n > 0=IBranch w (takeTree (n-1) x) (takeTree (n-1) y)

> takeTree _ _=ILeaf

Well, er. That compiles! Which you have to admit is a start. But is

it correct? Hudak's been a little unhelpful here by not actually

providing any debugging tools or setting those as exercises. I was

about to start creating a function `dumpTree` until I remembered

something about `Show`

> data InternalTree a=ILeaf

>|IBranch a (InternalTree a) (InternalTree a)

> deriving Show

>

>-- here's an example InternalTree to play with.

> itree=IBranch 1 (IBranch 2 ILeaf (IBranch 3 ILeaf ILeaf)) ILeaf

Does that work? If it does, then we'll be able to enter it on the ghci

interactive prompt and have a nice dumped representation:

*Tree> itree

IBranch 1 (IBranch 2 ILeaf (IBranch 3 ILeaf ILeaf)) ILeaf

Yay! So let's try the takeTree function

*Tree> takeTree 0 itree

ILeaf

*Tree> takeTree 1 itree

IBranch 1 ILeaf ILeaf

*Tree> takeTree 2 itree

IBranch 1 (IBranch 2 ILeaf ILeaf) ILeaf

*Tree> takeTree 3 itree

IBranch 1 (IBranch 2 ILeaf (IBranch 3 ILeaf ILeaf)) ILeaf

*Tree> takeTree 4 itree

IBranch 1 (IBranch 2 ILeaf (IBranch 3 ILeaf ILeaf)) ILeaf

Cheered by this success, I wrote the takeTreeWhile function quite easily

> takeTreeWhile::(a->Bool)->InternalTree a->InternalTree a

> takeTreeWhile p (IBranch w x y)

>|p w=IBranch w (takeTreeWhile p x) (takeTreeWhile p y)

> takeTreeWhile _ _=ILeaf

And again, that seems to give sensible results:

*Tree> takeTreeWhile (<2) itree

IBranch 1 ILeaf ILeaf

*Tree> takeTreeWhile (<3) itree

IBranch 1 (IBranch 2 ILeaf ILeaf) ILeaf

*Tree> takeTreeWhile (<4) itree

IBranch 1 (IBranch 2 ILeaf (IBranch 3 ILeaf ILeaf)) ILeaf

### Exercise 7.3 define foldr and repeat for InternalTree

This is a slightly tricksy question – what does `foldr`

mean for a Tree? Do its subfunctions take a Tree input, or does it work

on the values contained therein? If the latter (which I think is more

probable), then for the Tree datatype above, the implementation could be

trivially expressed as

> foldTree::(a->b->b)->b->Tree a->b

> foldTree f init t=foldr f init (fringe t)

*Tree> fringe t

[2,3,4]

*Tree> foldTree (+) 0 t

9

Of course, the InternalTree doesn't have values stored at the fringe.

We could define a similar function first

> iTreeVals :: InternalTree a -> [a]

> iTreeVals (ILeaf) = []

> iTreeVals (IBranch w x y) = w : iTreeVals x ++ iTreeVals y

> foldITree::(a->b->b)->b->InternalTree a->b

> foldITree f init t=foldr f init (iTreeVals t)

*Tree> iTreeVals itree

[1,2,3]

*Tree> foldITree (+) 0 itree

6

This of course means iterating the whole tree to get the values before

then iterating the list to fold over it, which might be inefficient. So

we could instead try to fold as we iterate the tree:

>-- does this work?

> foldITree'::(a->b->b)->b->InternalTree a->b

> foldITree' op init (ILeaf)=init

> foldITree' op init (IBranch w x y)

>=w `op` (foldITree' op init x) `op` (foldITree' op init y)

My main doubt was about the last line: how do we fold down 2 separate

paths? It turns out to be justified

7.hs:76:10:

Couldn't match expected type `a' (a rigid variable)

against inferred type `b' (a rigid variable)

`a' is bound by the type signature for `foldITree'' at 7.hs:73:19

`b' is bound by the type signature for `foldITree'' at 7.hs:73:22

In the first argument of `op', namely

`w `op` (foldITree' op init x)'

In the expression:

(w `op` (foldITree' op init x)) `op` (foldITree' op init y)

In the definition of `foldITree'':

foldITree' op init (IBranch w x y)

= (w `op` (foldITree' op init x)) `op` (foldITree' op init y)

I think that error message is relating to the `op` line, and thinking

about it, it `op` is (a->b) then `w `op` x `op` y` can't

work, because the intermediate result is of type b rather than a. (And

in fact, commenting the second `op` allows it to compile. I'm not

quite sure of how to proceed here. I could change the type signature of

op to (a->b->b->b) but that seems rather clumsy. I may come back to

this.

Now let's turn to ** repeat**. The function is defined

> repeat::a->[a]

if given an element 12, it will repeat it infinitely [12,12,12,12,12].

What does that mean for a tree? One thing I note from above is that we

use ILeaf as the base case just like we use [] in a list. Perhaps

`repeat` will simply substitute all ILeaves for the list again?

> repeatITree::InternalTree a->InternalTree a

> repeatITree t=let t'=t

> in_repeatITreet'

> where_repeatITree(ILeaf)=t

>_repeatITree(IBranch w x y)

>=IBranch w (_repeatITreex) (_repeatITreey)

I think this is doing the right thing:

-- formatted the show output manually

*Tree> takeTree 1 $ repeatITree itree

IBranch 1

ILeaf ILeaf

*Tree> takeTree 2 $ repeatITree itree

IBranch 1

(IBranch 2 (IBranch 1

ILeaf ILeaf) ILeaf ILeaf)

*Tree> takeTree 3 $ repeatITree itree

IBranch 1

(IBranch 2 (IBranch 1

(IBranch 1 (IBranch 3 (IBranch 2 ILeaf)

ILeaf ILeaf) ILeaf ILeaf)) ILeaf ILeaf)

### Ex 7.3. Using any of the definitions of tree above, define

versions of `zip` and `zipWith`

Let's stick with InternalTree for the moment

> zip::[a]->[b]->[(a,b)]

> zipITree::InternalTree a->InternalTree b->InternalTree (a,b)

> itree=IBranch 1 (IBranch 2 ILeaf (IBranch 3 ILeaf ILeaf)) ILeaf

> itree'=IBranch 3 (IBranch 4 ILeaf (IBranch 5 ILeaf ILeaf)) ILeaf

> zipITree::InternalTree a->InternalTree b->InternalTree (a,b)

> zipITree (ILeaf) (ILeaf)=ILeaf

> zipITree (IBranch w x y) (IBranch w' x' y')

>=IBranch (w,w') (zipITree x x') (zipITree y y')

*Tree> zipITree itree itree'

IBranch (1,3) (IBranch (2,4) ILeaf (IBranch (3,5) ILeaf ILeaf)) ILeaf

Do the structures of the trees have to be identical? would it make

sense to zip a Leaf with a Branch? What would go in the tuple (a,b) in

that case? We could supply an â€œinitâ€ argument to use instead. (Or

rather, two init arguments, one for each type of tree). I think right

now it makes sense to stick with the same structured tree. Zipping a

different kind of tree will complain about non exhaustive search

patterns, but we could do one better and define something like

> zipITree _ _=error "zipITree can only zip trees with the same structure"

zipWithTree is straightforward to define at this stage

> zipWithITree::(a->b->c)->InternalTree a->InternalTree b->InternalTree c

> zipWithITree _ (ILeaf) (ILeaf)=ILeaf

> zipWithITree fn (IBranch w x y) (IBranch w' x' y')

>=IBranch (fn w w') (zipWithITree fn x x') (zipWithITree fn y y')

And you have no idea how smug^whappy I feel about being able to call a

recursive function with pattern matching and polymorphic types

â€œstraightforwardâ€ ;-)

*Tree> zipWithITree (+) itree itree'

IBranch 4 (IBranch 6 ILeaf (IBranch 8 ILeaf ILeaf)) ILeaf

and we can defined zipITree in terms of zipWithITree as

> zipITree'::InternalTree a->InternalTree b->InternalTree (a,b)

> zipITree'=zipWithITree pair

> where pair x y=(x,y)

### Ex 7.5. Enhance the Expr datatype with variables and Let

expressions

When I skimmed through this chapter a couple of weeks ago I had the idea

that this exercise would be trivial in Haskell and, as my laptop was out

of action, I wrote it out longhand with pen and paper. I was so chuffed

by this that I had to dial up my web host from my phone and type it into

a text editor and compile. Modulo a couple of syntax errors, this

worked first time. Apart from a small tweak (my original Let

expressions only took constant values rather than the result of an

arbitrary Expr) this is what I wrote:

>-- the following is copied from SOE, with addition of V and Let lines

> data Expr=C Value

>|Expr :+ Expr

>|Expr :- Expr

>|Expr :* Expr

>|Expr :/ Expr

>|V String

>|Let String Expr Expr

>

> type Value=Float

>

>-- we need a table of String -> Value, which I chose

>-- to define as a list of tuples:

> type Vars=[(String, Value)]

>

>-- the following is taken from the book, with very few

>-- changes: mainly the propagation of the Vars table:

> evaluate::Vars->Expr->Value

> evaluate _ (C x)=x

> evaluate vs (e1 :+ e2)=evaluate vs e1 + evaluate vs e2

> evaluate vs (e1 :- e2)=evaluate vs e1-evaluate vs e2

> evaluate vs (e1 :* e2)=evaluate vs e1 * evaluate vs e2

> evaluate vs (e1 :/ e2)=evaluate vs e1 / evaluate vs e2

>-- just the following deal with setting and getting variables from

>-- the table

> evaluate vs (V v)=findVar vs v

> evaluate vs (Let k e' e)=(evaluate (setVar vs k (evaluate vs e')) e)

>

>-- and we need a couple of noddy functions to get and "set" (i.e.,

>-- return a new version of the table but with the variable added

>

> findVar::Vars->String->Value

> findVar ((k,v):vs) s=if s == k then v

> else findVar vs s

> findVar _ s=error ("Couldn't find variable " ++ s);

>

> setVar::Vars->String->Value->Vars

> setVar vs k v=(k,v) : vs

And that's it! When people say, as they often do, that Haskell is a

great language to write programming languages in, I'd never understood

them, but I think I'm starting to get it. As well as supporting the

â€œdata as codeâ€ idea like Lisp, the pattern matching and algebraic types

make the above really compact. In other languages you might have to

mess about with a whole lot of tree-walking and book-keeping code.

(My delight at the ease and simplicity of this question are tempered

slightly by the pain and confusion I subsequently faced on several

of the questions in earlier chapters though…)