G'day all. On Sat, Jun 29, 2002 at 05:26:46PM -0500, Mark Carroll wrote:
Do any of the experimental extensions to Haskell allow a what-he-wanted solution? I couldn't arrange one in H98 without something having an infinitely-recursive type signature. I'm sure it would have been easy in Lisp, and he already gave a Perl equivalent, so I'm wondering if it could be at all sane for Haskell to allow such stuff and if Haskell is somehow keeping us on the straight and narrow by disallowing the exact counter that was originally requested.
In principle it's perfectly possible to have a type system which works over regular trees. The main difficulty is how to actually express a type. You'd need something like letrec for types. typedef Counter = letrec x = Int -> (Int, x) in x It makes a few type-related things more inefficient, but it need not impose a huge cost in places where it's not used. It's fairly straightforward to optimise non-recursive types to the way they are handled at the moment at the cost of a more complex compiler. At least that's the story before you add all the other features of Haskell's type system. I'm not sure, for example, how it would interact with overlapping typeclass instances. This is the central problem with extensions to the type system: how well or badly it combines with all the other extensions that have been added over the years. In this case, I really don't see that you would get much in the way of extra expressiveness. Breaking recursion is as simple as introducing a newtype. Moreover, it's arguably "the Haskell way" just to introduce a new type whenever you need one, because it's so cheap to do. Cheers, Andrew Bromage