More suitable data structure needed

[Ken Shan]

--mYCpIKhGyMATD0i+
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

On 2002-08-22T17:04:02+0930, Dr Mark H Phillips wrote:
> But for the "Trie" type you have above, I am not aware of any way of
> converting this to an "essential type".  What I am thinking, is
> something like
>     [(a, *)]
> where '*' means to recursively refer to yourself.

I guess this depends on what you mean by "essential type".  If you are
willing to grant me a few additional types as essential ones:

    data Fix f =3D Fix (f (Fix f))

    newtype Pair    f g a =3D Pair (f a, g a)
    newtype Compose f   a =3D Compose (f a)
    newtype Self        a =3D Self a
    newtype Const   t   a =3D Const t

then I can build a type roughly isomorphic to what you call "[(a,*)]":

    type T a =3D Fix (Compose [] (Pair (Const a) Self))

For example, the value "[('a', [])]" would be written

    Fix (Compose [Pair (Const 'a', Self (Fix (Compose [])))])
    :: Fix (Compose [] (Pair (Const Char) Self))

One place to learn more about these things is section 4 of

    Mark P. Jones. Functional programming with overloading and
    higher-order polymorphism. In Johan Jeuring and Erik Meijer,
    editors, Advanced Functional Programming: First International Spring
    School on Advanced Functional Programming Techniques, number 925 in
    Lecture Notes in Computer Science, pages 97-136. Springer-Verlag,
    Berlin, 1995.

    http://www.cse.ogi.edu/~mpj/pubs/springschool.html

The paper is also a great read otherwise!

--=20
Edit this signature at http://www.digitas.harvard.edu/cgi-bin/ken/sig
http://oxford.freeexchange.co.uk/pages/6001.html

--mYCpIKhGyMATD0i+
Content-Type: application/pgp-signature
Content-Disposition: inline

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.7 (GNU/Linux)

iD8DBQE9ZTu7zjAc4f+uuBURAnsAAJoCRzB0lCfO2EVHqQbMcuFMN2vmvACg+ZBb
HWKB/6ppZ+vAr7HwhedrIIA=
=cuQX
-----END PGP SIGNATURE-----

--mYCpIKhGyMATD0i+--