Tree handling

[Lars Lundgren]

On Mon, 26 Feb 2001, Martin Gustafsson wrote:

> Hello=20
>=20
> I'm a haskell newbie that tries to create a tree with arbitary numbers of=
 childs.=20
> I create the data structure but i can't do anything on it can someone ple=
ase help
> me with a small function that sums the values of the leafs, so i don=B4t =
loose my hair
> so fast.
>=20
> The datastructure looks like this and a binary tree built with it would l=
ook like this:
>=20
>=20
> data GeneralTree  =3D Nil | Node (Integer,[GeneralTree])
>=20

As you said you were a newbie I will ask a few questions about your
datastructure.

Do you know that there is no need to tuple the elements in the Node if you
do not want to. You can write:

data GeneralTree  =3D Nil | Node Integer [GeneralTree]


What is the intended difference between (Node 5 []) and (Node 5 [Nil]) ?


>=20
> tree =3D=20
>   (20,
>    [
>     (-20,[(30,[Nil]),(20,[Nil])]),
>     (40,[(65,[Nil]),(-40,[Nil])])
>    ]
>   )

This is not of type GeneralTree! (And its layout is messed up)

Hint: write the type of every expression you write, and debugging will be
much easier.

tree :: GeneralTree

ERROR tree.hs:8 - Type error in explicitly typed binding
*** Term           : tree
*** Type           : (a,[(b,[(c,[GeneralTree])])])
*** Does not match : GeneralTree

This is an expression with type GeneralTree:

tree :: GeneralTree
tree =3D Node 20 [Node (-20) [Node 30 [Nil], Node 20 [Nil]],
                Node 40    [Node 65 [Nil], Node (-40) [Nil]]]

Now it should be very easy to write a function to sum the nodes in a tree

sumTree :: GeneralTree -> Integer
sumTree Nil =3D 0
sumTree (Node n ts) =3D ... write this yourself=20

hint - sum and map are very useful functions (defined in the prelude) as
are recursion.

Good luck!

/Lars L