CODEWITHSUNDEEP
haskell
A.B.
A.B.

Reputation: 16650

What does [a] stand for exactly?

I'm doing some exercises from "Real World Haskell". One is to design a safe version of init :: [a] -> [a].

I'm supposed to start from safeInit :: [a] -> Maybe [a]

This is what I have at the moment.

safeInit :: [a] -> Maybe [a]
safeInit [] = Nothing
safeInit [a] = if length [a] <= 1
    then Nothing
    else Just (take (length [a] -1) [a])

In GCHi, when testing safeInit [1,2] I get the error message

* Exception: ch4exercise.hs:(21,1)-(24,44): Non-exhaustive patterns in function safeInit

I was under the impression that [a] simply stands for a list (of any size) of a's. What am I doing wrong?

Upvotes: 3

Views: 270

Answers (4)

Ben
Ben

Reputation: 71515

One thing you'll have to get used to in Haskell, which isn't very intuitive until you're reasonably experienced, is that the "namespace" for type-level things is completely separate from the namespace for value-level things. This means the same source text can have a completely different meaning when you're talking about types than when you're talking about values.

safeInit :: [a] -> Maybe [a]

Everything following the :: is talking about types. Here [a] is the list type constructor applied to the type variable a.1 So it's the type of lists (of any size) whose elements are of type a.

safeInit [a] = if length [a] <= 1
    ...

OTOH this equation is at the value level. Here [a] isn't a type, it's a value (on the left hand side of the = it's a pattern to be matched by the value to which safeInit was applied; on the right hand side it's just a value). At the value level the square bracket syntax isn't the list type constructor, it's syntactic sugar for writing lists, with all the elements of the lists separated by commas inside the brackets. So [a] is the value of a list containing one single element, which is denoted by the variable a. If we wanted the list to be empty we'd write []. If we wanted the list to contain just a and b we'd write [a, b], etc.

At the value level it wouldn't make much sense for [a] to be a list of any number of as, because (during any particular evaluation of this code) a is one particular value, such as 3.4. What use is an expression for a list of any number of 3.4s?

1 Just as Maybe a is the Maybe type constructor applied to the type variable a; the only thing that's special about the list type constructor is that it's called [] rather than a normal name, and gets this odd "surrounding" syntax for application rather than the usual prefix form.

Upvotes: 3

Josiah
Josiah

Reputation: 1374

[] is the empty list, a list containing nothing. [a] is a list containing exactly one element, and that element (not the list) will be identified as "a" in the function. You therefore still need to consider the case where the list contains several elements.

If you just use "a" rather than "[a]", then "a" will refer to the whole list, and you can start taking it apart with the functions you have to hand.

Note that you've already dealt with the situation in which you have an empty list, so you shouldn't need to check it again in the if statement.

Upvotes: 4

mhwombat
mhwombat

Reputation: 8136

There's a problem with this line:

safeInit [a] = if length [a] <= 1

On the left side of the equation, [a] will match a list with exactly one element. So the compiler sees that you have a version of safeInit for an empty list, a version of safeInit for a list with one element, but nothing for a list with more elements. That's why it's complaining about Non-exhaustive patterns.

I think that what you really want is

safeInit a = if length a <= 1
    then Nothing
    else Just (take (length a -1) a)

To summarise:

  • In a type signature, [a] stands for a list of elements of arbitrary type a.

  • In a pattern, [a] matches a list with exactly one element.

Upvotes: 0

sepp2k
sepp2k

Reputation: 370327

As a type, [a] does stand for "a list of any size of as". As a pattern however, [a] stands for "a list containing exactly one element, which shall henceforth be known by the name a". Similarly [a,b] would mean "a list containing two elements, the first of which shall be known as a and the second of which shall be known as b" and so. [], as you already seem to know, stands for "a list containing exactly 0 elements".

This is analogous to how you'd write list literals as expressions. I.e. if you write myList = [], myList is the empty list and if you write myList = [x], myList is a list containing exactly one element, which is the value of the variable x.

Upvotes: 14

Related Questions