Mark Carroll <mark(a)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
