Why does Haskell let me return an empty list where a list inside a list is expected?

Question

I'm really new to Haskell and have been going through the 99 problems translation. This is my solution to number 9:

pack :: (Eq a) => [a] -> [[a]]
pack (xs)
    | null xs = []
    | otherwise = 
        let (matched, unmatched) = span (== head xs) xs
        in [matched] ++ pack unmatched

I don't get how I'm allowed to do | null xs = [] when the type signature says the function returns a [[]]. I've seen other solutions to the same problem do the same thing.

I mean, I'm not complaining, but is this something specifically allowed? Are there any caveats I have to look out for?

I'm using the GHCi on a default Windows 7 Haskell Platform 2013.2.0.0 installation, if that helps.

Answer 1

[] is an empty list. It has the following type:

[] :: [b] -- Note: I'm using b instead of a because your function already uses a

That b can be everything. Can you choose a b such that [b] ~ [[a]]? (~ is equality for types)? Yes, just use b ~ [a] and the type of [] becomes:

[] :: [b] :: [[a]]     -- When b ~ [a]

So [] is also a value of type [[a]]. [] is a valid value for any type of list, be it a list of a's or a list of lists of a's.

Answer 2

[Integer] is the type meaning "a list of integer values". Can there be a value in this type that doesn't actually contain any integers? Yes, the empty list [] contains zero integers.

[[Integer]] is the type meaning "a list of lists of integer values". Can there be a value in this type that doesn't actually contain any lists? Yes, the empty list [] contains zero lists.

Note that [] with type [[Integer]] is quite different from [[]] with the same type. The first represents the empty list of lists. The second is a non-empty list; it contains exactly one element, which is itself the empty list. A box containing one empty box is not the same thing as a box containing nothing at all! We could of course have [[], [], [], []] as well, where the outer non-empty list contains several elements, each of which is a empty list.

If it helps, think of the type [[Integer]] as representing list of rows, where each row is a list of integers. For example, the following:

11, 12, 13;
21, 22, 23, 24;
31;

is one way of visualising the [[Integer]] value [[11, 12, 13], [21, 22, 23, 24], [31]], where I've used commas to separate elements of the inner lists, and also semicolons to terminate each row (also line breaks to make it easy to read).

In that scheme, [[]] is the list consisting of one empty row. so you'd write it as just a single line ending in a semicolon. Whereas [] is a list with no rows at all, not even empty ones. So you'd write it as a blank file with no semicolons.

If that helped, then it should be easy to see how that applies to more abstract types like [[a]]. In general tough, [] with some list type (regardless of what type is written between the brackets) is always the list consisting of zero of the element type; it doesn't matter whether the element type itself is a list (or anything else with a concept of "empty").

Answer 3

Because [] is of type [[a]] in this case: it is a list containing exactly 0 alpha lists.
In general, the empty list can match any list type because every element (all zero of them) is of the correct type.

Answer 4

You already have a lot of great examples, but this might be a useful way to think about it.

Consider a type isomorphic to Haskell's lists, but without the syntactic sugar:

data List a = Nil
            | Cons a (List a)

Each type in Haskell is classified by its kind. This List type is of kind * -> *, which you can think of as a sort of type-level function that takes a basic type (of kind *) and returns another basic type.

You'll notice that the Cons constructor is also parameterized this way; it will be different for every different type a passed to the List type. But the Nil constructor is not parameterized that way; this means that the empty list constructor is the same for every type a that you may pass to List a. Nil remains polymorphic even when List a is constrained to a single type because its value does not depend on what a we choose!

So, the type of Nil is List a. This corresponds to [] in standard list notation. But how does [[]] translate to this desugared list type? The value is Cons Nil Nil and the type is List (List a)! In this syntax it is clearly not an empty list; it is a single-element list containing the empty list. It's still fully polymorphic, since nothing has yet constrained a to a single type, but it's definitely not empty.

The confusing thing about your example is that the name of the overall list type is the same as one of its constructors. If you see [[a]] in code you have to look at whether it's in a type context or a value context. In the former, it would mean (in our desugared notation) the type List (List a) while in the latter it would mean the value Cons (Cons a Nil) Nil.

Answer 5

This is not an answer, but may I suggest using pattern matches instead of head and null?

pack :: (Eq a) => [a] -> [[a]]
pack xs = case xs of
    []  -> []
    x:_ ->
        let (matched, unmatched) = span (== x) xs
        in [matched] ++ pack unmatched

This has the benefit the compiler will statically check that you don't access the first element of the list when the list is empty. Generally, use of head is considered non-idiomatic.

Answer 6

The following would be perhaps instructive: instead of

pack :: (Eq a) => [a] -> [[a]]
pack (xs)
    | null xs = []
...

try to write it thus:

pack :: (Eq a) => [a] -> [[a]]
pack (xs)
    | null xs = xs -- since xs is the empty list (WRONG!)
...

Based on the following (wrong) reasoning: We know that we must return the empty list when the argument is empty, hence, we can save typing [] (which would require pressing AltGr, for example on german keyboards) and return the argument right away -- it is the empty list, after all, as the null check confirmed.

The type checker will disagree, however, on this point. As a matter of fact, for the typechecker there exist infinitely many different empty lists, each possible list element type has its own empty list. In most cases, however, the type checker will identify the correct one when you give him [] - after all, in our example it knows that it must be a list of lists of as from the type signature.