Union Types for Haskell!?

Marcin 'Qrczak' Kowalczyk qrczak@knm.org.pl
27 Nov 2000 18:36:57 GMT

Mon, 27 Nov 2000 09:30:17 +0100, Bernd Holzmüller <holzmueller@ics-ag.de> pisze:

> Consider you have a data structure (e.g. an abstract syntax tree)
> consisting of nodes belonging to different data types. The difficulty
> is to write a function that abstracts from the traversal of that
> tree. I.e. try to write a map and a filter function on such data
> structures (what's the type of the function argument to map/filter?).

Union types don't help here. You cannot use standard map nor filter
because they work on lists. Functor instance does not work too because
your tree contain some specific types.

You have to write your own map implementation anyway. Then just let it
take separate functions of appropriate types for all kinds of nodes.
Otherwise it cannot be type safe.

> Finally, the result has again to be untagged to get a structure of
> the original types.

What if the original type demanded a particular type and the mapping
function produced something different?

The function to be mapped really corresponds to a set of functions,
one for each kind of information. So it's simpler to be explicit and
take separate things separately.

If you think it's too constraining, represent the tree with less
static type safety. You cannot have both: applying unsafely typed
functions to get safely typed trees.

If union types can be well defined to fit Haskell and be useful,
it must be a different purpose.

 __("<  Marcin Kowalczyk * qrczak@knm.org.pl http://qrczak.ids.net.pl/
  ^^                      SYGNATURA ZASTĘPCZA