type inference question

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

type inference question

I. J. Kennedy
Given a sort function that works on numbers, you can sort
in reverse order by first negating the list, then sorting, then
negating again:

 Prelude Data.List> let revsort = (map negate) . sort . (map negate)

The function sort takes any list of Ord; negate works on any Num.

 Prelude Data.List> :t negate
 negate :: (Num a) => a -> a
 Prelude Data.List> :t sort
 sort :: (Ord a) => [a] -> [a]

I'd therefore expect my revsort function to work on any type that is
both an Ord and a Num.  However:

Prelude Data.List> :t revsort
revsort :: [Integer] -> [Integer]

I was expecting something like
 revsort :: (Ord a, Num a) => [a] -> [a]
instead.

Question: Why did the GHCI's type inference mechanism jump to
the conclusion that revsort should only work with Integer lists?
Reply | Threaded
Open this post in threaded view
|

type inference question

Daniel Fischer-4
Am Sonntag 23 August 2009 20:12:16 schrieb I. J. Kennedy:

> Given a sort function that works on numbers, you can sort
> in reverse order by first negating the list, then sorting, then
> negating again:
>
>  Prelude Data.List> let revsort = (map negate) . sort . (map negate)
>
> The function sort takes any list of Ord; negate works on any Num.
>
>  Prelude Data.List> :t negate
>  negate :: (Num a) => a -> a
>  Prelude Data.List> :t sort
>  sort :: (Ord a) => [a] -> [a]
>
> I'd therefore expect my revsort function to work on any type that is
> both an Ord and a Num.  However:
>
> Prelude Data.List> :t revsort
> revsort :: [Integer] -> [Integer]
>
> I was expecting something like
>  revsort :: (Ord a, Num a) => [a] -> [a]
> instead.
>
> Question: Why did the GHCI's type inference mechanism jump to
> the conclusion that revsort should only work with Integer lists?

Because you defined it without an argument or type signature.
By the monomorphism restriction (
http://www.haskell.org/haskellwiki/Monomorphism_Restriction ), such values must have a
monomorphic type and by the defaulting rules, that is chosen as Integer.

You can
a) specify a type signature (good in source files)
b) define it as a function binding
let revsort xs = map negate . sort . map negate $ xs
c) turn off the monomorphism restriction in ghci:
Prelude> :set -XNoMonomorphismRestriction
Prelude> :m +Data.List
Prelude Data.List> let revsort = map negate . sort . map negate
Prelude Data.List> :t revsort
revsort :: (Num a, Ord a) => [a] -> [a]
(might put :set -XNoMonomorphismRestriction in your .ghci file)

btw, another way to revsort is
let revsort = sortBy (flip compare)