Recursive types?

Tom Pledger Tom.Pledger@peace.com
Wed, 23 May 2001 10:23:10 +1200

```(Bailing out to haskell-cafe because this stuff is probably old hat)

David Bakin writes:
| 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?

No.  You can generalise over some structures

ctHeight :: (CT c k e -> Tree c k e) -> CT c k e -> Int
ctHeight extract ct
= case extract ct of
Empty      -> 0
Node l _ r -> let hl = ctHeight extract l
hr = ctHeight extract r
in  1 + max hl hr

plainHeight = ctHeight (\(Plain t) -> t)

labelledHeight = ctHeight snd

where the role of `extract' is a simplification of that of `phi' in
section 5.1 of the paper you mentioned (MPJ's Functional Programming
out of my depth in bananas and lenses, so won't try to be more

Anyway, the type of ctHeight is not appropriate for all possible
structures.  For example, to follow an STRef you must visit an ST:

import ST

stHeight :: CT STRef s e -> ST s Int
stHeight ct
= do t <- readSTRef ct
case t of
Empty      -> return 0
Node l _ r -> do hl <- stHeight l
hr <- stHeight r
return (1 + max hl hr)

- Tom

:
| -----Original Message-----
| From: Tom Pledger [mailto:Tom.Pledger@peace.com]
:
| 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

```