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. | | 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 Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell