Recursive types?

[Tom Pledger]

(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
with Overloading and Higher-Order Polymorphism).  I'm rapidly getting
out of my depth in bananas and lenses, so won't try to be more
specific about the similarity.

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