Writing a counter function

[Jon Cast]

Mark Carroll <mark@chaos.x-philes.com> wrote:
> On Sat, 29 Jun 2002, Samuel E. Moelius III wrote:
> (snip)
> > Here's another not-exactly-what-you-wanted solution.  :)
> (snip)

> 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.

That's because the problem requires an infinitely-recursive type.

> I'm sure it would have been easy in Lisp, and he already gave a Perl
> equivalent,

That's because both Lisp and Perl are weakly typed.  Haskell is
strongly typed.  Consider Lisp:

(defun self-apply (f)
"Apply F to itself."
       (f f))

No problem (and I'm sure you can pull the same trick off in Perl).
Consider Haskell:

self-apply f = f f

The *typing algorithm* (the thing that didn't complain in Lisp)
proceeds roughly as follows:

f is applied to at least one argument, so f must have type a -> b.
Therefore, f's argument (f) must have type a.  So, we conclude:

f :: a -> b
f :: a

But f can only have one type, so we set its types equal:

a = a -> b

This is clearly recursive, right?

> so I'm wondering if it could be at all sane for Haskell to allow
> such stuff

Sure.  All it has to do is:

1. Create its own newtype in response to such things as
`self-apply' above.

2. Ensure that

self-apply f = f f

and

self-apply' g = g g

have the same type.  I would *love* to hear ideas on how to do that,
but it's difficult.

> and if Haskell is somehow keeping us on the straight and narrow by
> disallowing the exact counter that was originally requested.

Well, it's a more general problem than the `exact counter'.  And, yes,
Haskell is erring on the side of safety here; there's a reason it's
called a ``statically typed language''.

> The beauty of his request was that it was so simple and seemed to
> make sense; I went ahead and tried to fulfill it before realising I
> couldn't do it either.

Well, it makes sense, yes.  But I think learning to manually `unify'
these things (add a newtype) is not hard, and probably useful ---
Haskell is not the only statically-typed language out there.
Learn how to solve this problem, and you understand the problem, the
solution, typing, and life in general :)

> -- Mark

Jon Cast