Recursive types?

[David Bakin]

Thank you.

Now, on seeing your Tree example I tried to use it by defining height
using structural recursion.  But I couldn't find a valid syntax to
pattern match - or otherwise define the function - on the type CT.  Is
there one?  Or, maybe, are constructor classes the only way to use these
types?  If that's the case - is that inherent in these types or just the
way Haskell does it?  Because I was thinking that although you don't
know much about these types (e.g., the operations you can perform on k)
you should be able to compute height (& size) and leaves :: Tree c k e
-> [e] and even replMin on the information that's there in the type.

-- Dave


-----Original Message-----
From: Tom Pledger [mailto:Tom.Pledger@peace.com]
Sent: Monday, May 21, 2001 7:25 PM
To: haskell@haskell.org
Subject: Recursive types?


David Bakin writes:
 | I'm having trouble understanding recursive types (e.g., as described
in
 | Functional Programming with Overloading and Higher-Order Polymorphism
by
 | Jones.
 | =20
 | He gives as an example
 | =20
 | =20
 | > data Mu f =3D In (f (Mu f))
 | =20
 | > data NatF s =3D Zero | Succ s
 | > type Nat =3D Mu NatF
 | =20
 | Among the things I don't get are:
 | =20
 | 1.  Comparing this to the non-higher-order type:
 | =20
 | > data NatX =3D Zero | Succ NatX
 | =20
 | What are the advantages of the higher-order type?  What are the
 | disadvantages (incl. runtime costs)?
 | =20
 | 2.  How are values of type Nat represented? (It helps me to think
about
 | these things concretely.)

    _|_
    In _|_
    In Zero
    In (Succ _|_)
    In (Succ (In _|_))
    In (Succ (In Zero))
    In (Succ (In (Succ _|_)))
    In (Succ (In (Succ (In _|_))))
    In (Succ (In (Succ (In Zero))))

and so on.  If you never care about distinguishing In _|_ from _|_,
you can save space and time by declaring `newtype Mu ...' instead of
`data Mu ...', in which case Nat's run-time representation is the same
size as NatX's.

One advantage of such higher-order types is reusability.  For example,
this

    type CT c k e
        =3D c k (Tree c k e)    -- Contained Tree, container, key, =
element
    data Tree c k e
        =3D Empty
        | Node (CT c k e) e (CT c k e)

can be used with no frills

    newtype Plain k t =3D Plain t
    ... :: Tree Plain () e

or with every subtree labelled

    ... :: Tree (,) String e

or with every subtree inside the ST monad

    import ST
    ... :: Tree STRef s e

etc.  I don't know whether this is a shining example of an advantage,
and am keen to see other comments.

Regards,
Tom

_______________________________________________
Haskell mailing list
Haskell@haskell.org
http://www.haskell.org/mailman/listinfo/haskell