Hi,
> As a naive implementation of "all" and "any", one of my students coped
> with these definitions:
> any' p xs = [x | x <- xs, p x] /= []
> all' p xs = [x | x <- xs, p x] == xs
> As expected, the type for any' is Eq a => (a -> Bool) -> [a] -> Bool because
> of the use of ==. Nevertheless, the definition of all' does not type check:
...
> Any (simple) answer? (I'm afraid monad stuff, aggh)... I have many
> ML-minded students blaming at hugs because is not able to print the
> result of evaluating [] without a type
The problem is indeed related to monads, but arises due to Haskell's
restriction to contexts of the form: C alpha. Thus, an implementation of
Haskell must be able to either discharge a predicate or reduce it to
this simple form. For example, the predicates Eq Int and Eq alpha are
leagal in Haskell--- the first can be dischared (i.e., the implementation
for int equality is completly determined, while the second is in the form
C alpha.
The above example can be better understood by first considering the following
simple definition:
t xs = [x | x <- xs],
which is assigned the type:
Monad c => c a -> c a.
If we now assume that ys has type (c a) we then the application (t ys)
has type c a--- note that the result type is of the form c a, where c is
a type constructor variable. Now, given (==) :: Eq a => a -> a -> Bool,
forgeting about Haskell context restrictions the defintion
t xs = [x | x <- xs] == xs,
has type
Eq (c a) => c a -> c a -> Bool.
Of course an implementation of Haskell 1.4 suold reject this type as it
does not have a context of the form C alpha. This problem does not
arise with the definition
t xs = [x | x <- xs] /= [],
because the type of [] is [b] and thus the monad constraint (Monad c) becomes
Monad [], which can be discharged and thus, the type for t becomes
Eq [a] => [a] -> [a] -> Bool.
Now, unlike the predicate Eq c a, the predicate Eq [a] can be simplified
to Eq a, which is a valid Haskell context.
I beleive that the problem of context reduction in the presence of constructor
classes is currently under review for Standard Haskell.
An easy soloution to your problem, which may help to avoid other similar
error messages, may be to use Hugs 1.3c. This new release of the Hugs 1.3
development system refrains from doing any context reduction, also no
monad comprehensions, so typing in the definition
all' p xs = [x | x <- xs, p x] == xs
and then typing :t all' results in the type
any' :: Eq [a] => (a -> Bool) -> [a] -> Bool,
as expected.
The Hugs 1.3c can be downloaded from
http://www.cs.nott.ac.uk/~mpj/hugs13/
I hope this helps.
Best wishes
Ben
--------
Benedict R. Gaster.
Languages and Programming Group, University of Nottingham.
A thing of beauty is a joy forever -- John Keats (1795--1821).
