[Haskell-beginners] type signature error in a where clause

[Kim-Ee Yeoh]

On Sat, Nov 24, 2012 at 10:32 PM, Mark Wallace <lotabout at gmail.com> wrote:

> > 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?

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 at 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.
>>
> Thanks for answering so fast. And all of your answers are very helpful.
> 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?
>
>
> ______________________________**_________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/**mailman/listinfo/beginners<http://www.haskell.org/mailman/listinfo/beginners>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20121125/e8530d07/attachment.htm>