[Haskell-cafe] Avoiding the Y combinator for self-referencing types

Florian Weimer fw at deneb.enyo.de
Sun Dec 12 18:54:06 CET 2010

Suppose I've got some named objects which reference other objects by

> data NodeS = NodeS {nameS :: String, refsS :: [String]}

Through name resolution, the strings are translated to the actual
nodes they denote:

> data Node = Node {name :: String, refs :: [Node]}
> resolve :: [NodeS] -> Map String Node

NodeS and Node are quite similar, so they should probably be the same
parametrized type.  However, if I turn the type of the references into
a type parameter, I need the type-level Y combinator to avoid an
infinite type, and manipulating nodes turns a bit more tedious because
of increased syntactic overhead.

Is there a third choice, beyond manually expanding the type definition
or using Y?

More information about the Haskell-Cafe mailing list