Recursive types?
David Bakin
davidbak@microsoft.com
Mon, 21 May 2001 18:23:31 -0700
This is a multi-part message in MIME format.
------_=_NextPart_001_01C0E25D.CFC0BA65
Content-Type: text/plain;
charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
I'm having trouble understanding recursive types (e.g., as described in
Functional Programming with Overloading and Higher-Order Polymorphism by
Jones.
=20
He gives as an example
=20
=20
> data Mu f =3D In (f (Mu f))
=20
> data NatF s =3D Zero | Succ s
> type Nat =3D Mu NatF
=20
Among the things I don't get are:
=20
1. Comparing this to the non-higher-order type:
=20
> data NatX =3D Zero | Succ NatX
=20
What are the advantages of the higher-order type? What are the
disadvantages (incl. runtime costs)?
=20
2. How are values of type Nat represented? (It helps me to think about
these things concretely.)
=20
Thanks! -- Dave
=20
=20
------_=_NextPart_001_01C0E25D.CFC0BA65
Content-Type: text/html;
charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META HTTP-EQUIV=3D"Content-Type" CONTENT=3D"text/html; =
charset=3Diso-8859-1">
<META content=3D"MSHTML 5.50.4522.1800" name=3DGENERATOR></HEAD>
<BODY>
<DIV><SPAN class=3D796581801-22052001><FONT face=3DArial size=3D2>I'm =
having trouble=20
understanding recursive types (e.g., as described in <EM>Functional =
Programming=20
with Overloading and Higher-Order Polymorphism</EM> by=20
Jones.</FONT></SPAN></DIV>
<DIV><SPAN class=3D796581801-22052001><FONT face=3DArial=20
size=3D2></FONT></SPAN> </DIV>
<DIV><SPAN class=3D796581801-22052001><FONT face=3DArial size=3D2>He =
gives as an=20
example</FONT></SPAN></DIV>
<DIV><SPAN class=3D796581801-22052001><FONT face=3DArial=20
size=3D2></FONT></SPAN> </DIV>
<DIV><SPAN class=3D796581801-22052001><FONT face=3DArial=20
size=3D2></FONT></SPAN> </DIV>
<DIV><SPAN class=3D796581801-22052001><FONT face=3DArial size=3D2>> =
data Mu f =3D In=20
(f (Mu f))</FONT></SPAN></DIV>
<DIV><SPAN class=3D796581801-22052001><FONT face=3DArial=20
size=3D2></FONT></SPAN> </DIV>
<DIV><SPAN class=3D796581801-22052001><FONT face=3DArial size=3D2>> =
data NatF s =3D=20
Zero | Succ s</FONT></SPAN></DIV>
<DIV><SPAN class=3D796581801-22052001><FONT face=3DArial size=3D2>> =
type Nat =3D Mu=20
NatF</FONT></SPAN></DIV>
<DIV><SPAN class=3D796581801-22052001><FONT face=3DArial=20
size=3D2></FONT></SPAN> </DIV>
<DIV><SPAN class=3D796581801-22052001><FONT face=3DArial size=3D2>Among =
the things I=20
don't get are:</FONT></SPAN></DIV>
<DIV><SPAN class=3D796581801-22052001><FONT face=3DArial=20
size=3D2></FONT></SPAN> </DIV>
<DIV><SPAN class=3D796581801-22052001><FONT face=3DArial =
size=3D2>1. Comparing=20
this to the non-higher-order type:</FONT></SPAN></DIV>
<DIV><SPAN class=3D796581801-22052001><FONT face=3DArial=20
size=3D2></FONT></SPAN> </DIV>
<DIV><SPAN class=3D796581801-22052001><FONT face=3DArial size=3D2>> =
data NatX =3D=20
Zero | Succ NatX</FONT></SPAN></DIV>
<DIV><SPAN class=3D796581801-22052001><FONT face=3DArial=20
size=3D2></FONT></SPAN> </DIV>
<DIV><SPAN class=3D796581801-22052001><FONT face=3DArial size=3D2>What =
are the=20
advantages of the higher-order type? What are the disadvantages =
(incl.=20
runtime costs)?</FONT></SPAN></DIV>
<DIV><SPAN class=3D796581801-22052001><FONT face=3DArial=20
size=3D2></FONT></SPAN> </DIV>
<DIV><SPAN class=3D796581801-22052001><FONT face=3DArial =
size=3D2>2. How are=20
values of type Nat represented? (It helps me to think about these things =
concretely.)</FONT></SPAN></DIV>
<DIV><SPAN class=3D796581801-22052001><FONT face=3DArial=20
size=3D2></FONT></SPAN> </DIV>
<DIV><SPAN class=3D796581801-22052001><FONT face=3DArial =
size=3D2>Thanks! --=20
Dave</FONT></SPAN></DIV>
<DIV><SPAN class=3D796581801-22052001><FONT face=3DArial=20
size=3D2></FONT></SPAN> </DIV>
<DIV><SPAN class=3D796581801-22052001><FONT face=3DArial=20
size=3D2></FONT></SPAN> </DIV></BODY></HTML>
------_=_NextPart_001_01C0E25D.CFC0BA65--