ghc/tests/typecheck/should_compile/tc091.hs

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