The unspoken wisdom goes something like this: the classic top-down FP way of coding has you sketch out most if not all of your function signatures. So when you hit the keyboard, a very natural thing to do is to key in all those signatures stubbing out definitions using "undefined". You proceed from there.
Sometimes people just use haskell as a calculator on steroids, especially when solving project-euler-type problems. In which case, anything goes. Needless to say, if all the practice a beginner gets is project euler, they're missing out a lot.
-- Kim-Ee
On Sat, Nov 24, 2012 at 10:32 PM, Mark Wallace
<lotabout@gmail.com> wrote:
On 11/24/2012 11:07 PM, Daniel Fischer wrote:
On Samstag, 24. November 2012, 22:04:15, Mark Wallace wrote:
I'm writing a merge sort function, but I get type error under such
implementation:
mergesort :: (a -> a -> Ordering) -> [a] -> [a]
mergesort cmp xs = mergeAll (map (\x -> [x]) xs)
where
mergeAll :: [[a]] -> [a]
mergeAll [x] = x
mergeAll xs = mergeAll (mergePairs xs)
mergePairs :: [[a]] -> [[a]]
mergePairs (a:b:xs) = merge a b : mergePairs xs
mergePairs xs = xs
merge :: [a] -> [a] -> [a]
merge as@(a:as') bs@(b:bs')
| cmp a b == GT = b : merge as bs'
| otherwise = a : merge as' bs
merge [] bs = bs
merge as [] = as
And ghc says:
Couldn't match type `a1' with `a'
`a1' is a rigid type variable bound by
the type signature for merge :: [a1] -> [a1] -> [a1]
at
/home/ice/Study/Haskell/tutorials/99Questions/21to30.hs:135:7
`a' is a rigid type variable bound by
the type signature for
mergesort :: (a -> a -> Ordering) -> [a] -> [a]
at
/home/ice/Study/Haskell/tutorials/99Questions/21to30.hs:124:1
In the first argument of `cmp', namely `a'
In the first argument of `(==)', namely `cmp a b'
In the expression: cmp a b == GT
But if I comment all type signatures, ghc works fine on it.
I would really appreciate it if you can point out what causes this
question?
Type variables are implicitly for all-quantified. Thus the type variable a in
the signatures of the local functions is a fresh type variable and has nothing
to do with the a from the top-level signature.
It is equivalent to you writing
merge :: [b] -> [b] -> [b]
except there it is obvious that the type signature is wrong.
And how to fix it without changing the structure of the program (i.e. not
adding function `cmp' as a parameter of `merge' etc.).
1. Just omit the type signatures, they can be inferred.
That's the portable way.
2. Bring the type variable a into scope
{-# LANGUAGE ScopedTypeVariables #-}
mergesort :: forall a. (a-> a-> Ordering) -> [a] -> [a]
then an (unquantified) a in a local type signature refers to the type from the
top-level signature.
That's a GHC-only (as far as I know) way.
I've tested these two solutions, all works fine.
Now I understand how type signature works in such condition.
Somehow it might seem a bit easier to me to grasp the function of a function with the help of type signature.
I'll try just omitting the signatures, it's easier and more handy isn't it?