Writing a counter function

[Andrew J Bromage]

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