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:[EMAIL PROTECTED]]
Sent: Monday, May 21, 2001 7:25 PM
To: [EMAIL PROTECTED]
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.
|
| He gives as an example
|
|
| > data Mu f = In (f (Mu f))
|
| > data NatF s = Zero | Succ s
| > type Nat = Mu NatF
|
| Among the things I don't get are:
|
| 1. Comparing this to the non-higher-order type:
|
| > data NatX = Zero | Succ NatX
|
| What are the advantages of the higher-order type? What are the
| disadvantages (incl. runtime costs)?
|
| 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
= c k (Tree c k e) -- Contained Tree, container, key, element
data Tree c k e
= Empty
| Node (CT c k e) e (CT c k e)
can be used with no frills
newtype Plain k t = 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
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
_______________________________________________
Haskell mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
