1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
|
{-# OPTIONS_GHC -fno-warn-redundant-constraints #-}
-- !!! Test polymorphic recursion
-- With polymorphic recursion this one becomes legal
-- SLPJ June 97.
{-
To: Lennart Augustsson <augustss@cs.chalmers.se>
Cc: partain@dcs.gla.ac.uk, John Peterson (Yale) <peterson-john@cs.yale.edu>,
simonpj@dcs.gla.ac.uk
Subject: Type checking matter
Date: Fri, 23 Oct 92 15:28:38 +0100
From: Simon L Peyton Jones <simonpj@dcs.gla.ac.uk>
I've looked at the enclosed again. It seems to me that
since "s" includes a recursive call to "sort", inside the body
of "sort", then "sort" is monomorphic, and hence so is "s";
hence the type signature (which claims full polymorphism) is
wrong.
[Lennart says he can't see any free variables inside "s", but there
is one, namely "sort"!]
Will: one for the should-fail suite?
Simon
------- Forwarded Message
From: Lennart Augustsson <augustss@cs.chalmers.se>
To: partain
Subject: Re: just to show you I'm a nice guy...
Date: Tue, 26 May 92 17:30:12 +0200
> Here's a fairly simple module from our compiler, which includes what
> we claim is an illegal type signature (grep ILLEGAL ...).
> Last time I checked, hbc accepted this module.
Not that I don't believe you, but why is this illegal?
As far as I can see there are no free variables in the function s,
which makes me believe that it can typechecked like a top level
definition. And for a top level defn the signature should be
all right.
-- Lennart
- ------- End of forwarded message -------
-}
module ShouldSucceed where
sort :: Ord a => [a] -> [a]
sort xs = s xs (length xs)
where
s :: Ord b => [b] -> Int -> [b] -- This signature is WRONG
s xs k = if k <= 1 then xs
else merge (sort ys) (sort zs)
where (ys,zs) = init_last xs (k `div` (2::Int))
-- Defns of merge and init_last are just dummies with the correct types
merge :: Ord a => [a] -> [a] -> [a]
merge xs ys = xs
init_last :: [a] -> Int -> ([a],[a])
init_last a b = (a,a)
|