Question

In a test I'm asked to infer the type of:

let pr = map head.group.sortBy(flip compare)

I've concluded after inferring it myself that the type was:

Ord a => [a] -> [a]

However when doing :t in GHCi it says the type is:

pr :: [()] -> [()]

What is going on?

Also if in GHCi I do:

map head.group.sortBy(flip compare) [1,2,3,4,100,50,30,25,51,70,61]

I get an error:

 Couldn't match expected type `a0 -> [b0]' with actual type `[a1]'
In the return type of a call of `sortBy'
Probable cause: `sortBy' is applied to too many arguments
In the second argument of `(.)', namely
  `sortBy (flip compare) [1, 2, 3, 4, ....]'
In the second argument of `(.)', namely
  `group . sortBy (flip compare) [1, 2, 3, 4, ....]'

However if I do:

sortBy(flip compare) [1,2,3,4,100,50,30,25,51,70,61]
[100,70,61,51,50,30,25,4,3,2,1]

It works just fine. Why is the first expression failing when the second evaluates sortBy just fine with the exact same arguments?

Was it helpful?

Solution

Your first problem is the dreaded combination of the Monomorphism Restriction, GHCi's inability to see your whole program at once, and GHCi's extended defaulting rules.

In a nutshell, Haskell doesn't like to infer types with polymorphic type class constraints (the Ord a => part of your type signature) for top-level bindings that are written as equations that syntactically do not have arguments. pr = map head.group.sortBy(flip compare) falls foul of this rule (it's a function, so semantically it has arguments, but the equation you're using to define it doesn't), so Haskell wants the Ord-constrained a to be something concrete.

If you put this in a source file and compile it (even via GHCi):

import Data.List

pr = map head.group.sortBy(flip compare)

You get outright errors, like:

foo.hs:3:33:
    No instance for (Ord b0) arising from a use of `compare'
    The type variable `b0' is ambiguous
    Possible cause: the monomorphism restriction applied to the following:
      pr :: [b0] -> [b0] (bound at foo.hs:3:1)
    Probable fix: give these definition(s) an explicit type signature
                  or use -XNoMonomorphismRestriction
    Note: there are several potential instances:
      instance Integral a => Ord (GHC.Real.Ratio a)
        -- Defined in `GHC.Real'
      instance Ord () -- Defined in `GHC.Classes'
      instance (Ord a, Ord b) => Ord (a, b) -- Defined in `GHC.Classes'
      ...plus 22 others
    In the first argument of `flip', namely `compare'
    In the first argument of `sortBy', namely `(flip compare)'
    In the second argument of `(.)', namely `sortBy (flip compare)'
Failed, modules loaded: none.

For some types in particular (notably numeric types) this kind of "ambiguous type variable" error comes up a lot and would be irritating, so Haskell has some defaulting rules. For example, it will assume an ambiguous type variable constrained only by Num should be Integer. Of course, if you use the function anywhere in the same file like so:

import Data.List

pr = map head.group.sortBy(flip compare)

answer = pr [1,2,3,4,100,50,30,25,51,70,61]

then Haskell can take into account. It still refuses to infer a polymorphic type for pr, but in this case pr is only ever used as if it were [Integer] -> [Integer], so it'll give it that type and allow your code to compile, rather than issue the ambiguous type variable error (the Integer itself is also a result of type defaulting).

In GHCi, your code is compiled one statement at a time, so it can't take into account your use of pr to decide what type to give it. It would give you an ambiguous type error except that GHCi has extended defaulting rules, which kick in here to "save the day" and allow your expression to compile. By defaulting the Ord a => a type variable to the unit type (), your declaration can be interpreted as the definition of a function for condensing arbitrary lists of () into [()] (or [] if the input was empty). Thanks GHCi!

You can resolve this in a few of different ways. One is to add an argument to both sides of your definition of pr, like so:

let pr z = map head.group.sortBy(flip compare) $ z

Now the equation defining pr has an argument syntacically (it's type/meaning still has the same number of arguments), the Monomorphism Restriction doesn't kick in, and Haskell is happy to infer a polymorphic type for pr.

Another is to explicitly tell it you don't want to use the Monomorphism Restriction by either adding {-# LANGUAGE NoMonomorphismRestriction #-} to the top of your module, or by using :set -XNomonomorphismRestriction at the GHCi prompt. Then it will again infer the type Ord a => [a] -> [a] for pr.

A third way is to explicitly give the polymorphic type signature for your function:

import Data.List

pr :: Ord a => [a] -> [a]
pr = map head.group.sortBy(flip compare)

Or in GHCi:

> let { pr :: Ord a => [a] -> [a] ; pr = map head.group.sortBy(flip compare) }

Since even with the Monomorphism Restriction in force Haskell is happy for pr to have a polymorphic type, it just won't infer one for it.

The explicit type signature is probably the most common way people avoid this problem in compiled files, because many people consider it good style to always provide type signatures for top level definitions. In GHCi it's pretty annoying, as you can see; I usually turn off the Monomorphism Restriction there.


As for your second problem, I'm afraid this:

map head.group.sortBy(flip compare) [1,2,3,4,100,50,30,25,51,70,61]

is very different from this:

pr [1,2,3,4,100,50,30,25,51,70,61]

When you've got pr defined as a function, pr refers to the whole function map head.group.sortBy(flip compare), so feeding it an argument feeds an argument to that function. But when you write out the whole expression, just sticking a list to the right of it does not pass it as an argument to the whole expression. It's parsed a bit more like this:

(map head) . (group) . (sortBy (flip compare) [1,2,3,4,100,50,30,25,51,70,61])

As you can see, the list is inside the last function in the pipeline; sortBy (flip compare) [1,2,3,4,100,50,30,25,51,70,61] is being used as a function, which will take an argument and feed its output further through the pipeline (to group). That clearly doesn't make sense, and is why you get an error message complaining about too many arguments being given to sortBy; it's not that you have provided too many arguments to sortBy, but rather that you've provided all its arguments and then used it in a position where it would have to be able to take one more.

This can sometimes be surprising until you get used to it, but any alternative is surprising more frequently (you implicitly depended on parsing working this way in your use of map head and sortBy (flip compare)). All you need to do is remember that ordinary function application (by just sticking two expressions next to each other) is always higher precedence than infix operators (like .); whenever you've got an expression mixing infix operators and ordinary application, each normal application chain (groups of non-operator expressions separated only by whitespace) becomes only a single argument as far as the infix operators are concerned (and then precedence/associativity is used to resolve what the arguments of the infix operators are).

To fix it, you need to add parentheses around the composition pipeline before you introduce the argument, like so:

(map head.group.sortBy(flip compare)) [1,2,3,4,100,50,30,25,51,70,61]

Or use $ to put a "wall" between the composition pipeline and the argument, like so:

map head.group.sortBy(flip compare) $ [1,2,3,4,100,50,30,25,51,70,61]

This works because $ is another infix operator, so it forces all the "normal application" sequences to its left and right to be resolved before one can be applied to the other. It's also a very low precedence operator, so it almost always works when there are other infix operators in play as well (like the .). It's quite a common idiom in Haskell to write expressions of the form f . g . h $ a.

OTHER TIPS

  1. You've been bitten by defaulting, where GHCi (interactive GHCi, not GHC compiling something) will put () in any uninstantiated type parameter in certain cases.

  2. I think you've mixed up . and $. Consider your original expression:

    map head . group . sortBy(flip compare) [1,2,3,4,100,50,30,25,51,70,61]
    

    That composes the functions map head, group, and sortBy (flip compare) [...]. Unfortunately, sortBy (flip compare) [...] is a list, not a function, so it can't be composed like that. sortBy (flip compare), however, is, and if we compose those functions together and then apply that function to the list, it'll work:

    map head . group . sortBy (flip compare) $ [1,2,3,4,100,50,30,25,51,70,61]
    
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top