Non type-variable argument in the constraint error while using foldl with ++

2
votes

I am trying to use fold with ++. It should work as I check the type of it:

> :t foldl (++)
foldl (++) :: Foldable t => [a] -> t [a] -> [a]

When I try to use it like this

> foldl (++) [1] [1,2,3]

I get an error like:

Non type-variable argument in the constraint: Num [a] (Use FlexibleContexts to permit this)

What am I doing wrong?

1
haskell
Your fold evaluates to ((([1] ++ 1) ++ 2) ++ 3) which is ill typed, since ++ needs two lists. GHC tries to make this work by converting each of 1,2,3 to a list, by requiring Num [a], which fails. – chi

1 Answers

8
votes

I think you misunderstand the type of your foldl (++) function, the t is important here:

foldl (++) :: Foldable t => [a] -> t [a] -> [a]

If you pass [1] :: Num n => [n] as a first argument, that is not a problem, since then your [1] as type [a], and hence a ~ n.

The second argument however is a problem. You here pass a list [1,2,3] :: Num m => [m], with a type Num m => [m], or more canonical Num m => [] m. The only possible way to let this match with t [a], is to set t ~ [] (t is the list type constructor), and then [a] should match with m, but Haskell does not know a Num type m that is a list [a], hence it fails.

You can call this with for example:

Prelude> foldl (++) [1] [[2], [3,4]]
[1,2,3,4]

Since Haskell here will generate an expression that looks like:

(([1] ++ [2]) ++ [3]) ++ [4]

which is equivalent to:

[1,2,3,4]

We can also pass other Foldable types, like a Maybe for example:

Prelude> foldl (++) [1] (Just [2])
[1,2]
Prelude> foldl (++) [1] Nothing
[1]

In that case the second parameter should have type Maybe [Int].