Recursive types?

[Tom Pledger]

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