Mark Carroll
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