Ambiguous types using ListLike

Question

I'm writing a function in Haskell to make a histogram from any ListLike with Ord elements:

import qualified Data.ListLike as LL
...
frequencies :: (Ord x, LL.ListLike xs x) => xs -> [(x, Int)]
frequencies xs = LL.map (\x->(LL.head x, LL.length x)) $ LL.group $ LL.sort xs

When trying to compile the above code i get an error message about ambiguous types:

 Ambiguous type variable `full0' in the constraint:
 (LL.ListLike full0 xs) arising from a use of `LL.group'
 Probable fix: add a type signature that fixes these type variable(s)
 In the expression: LL.group
 In the second argument of `($)', namely `LL.group $ LL.sort xs'
 In the expression:
 LL.map (\ x -> (LL.head x, LL.length x)) $ LL.group $ LL.sort xs

LL.group has type (ListLike full0 full, ListLike full item, Eq item) => full -> full0 which corresponds to (Eq a) => [a]->[[a]] speaking in terms of ordinary lists.

I dont understand why there is a problem with ambigious types. Is Haskell somehow unable to infer that there is such a type as "ListLike with full as elements", i.e full0?

Answer 1

Is Haskell somehow unable to infer that there is such a type as "ListLike with full as elements", i.e full0?

No, the problem is there are too many types to choose full0 from and the Haskell compiler does not know which to use. Think about it: in general, there can be more than one type full0 which is a list-like type with full as elements: [full] or Data.Sequence.Seq full or many other choices. And because of the generality of the definition of LL.map, full0 is not constrained to be [full] from the return type of the function frequencies.

If you want to restrict full0 to [full], one way to do this is to replace LL.map in the definition of frequencies with the plain old map for lists.