What is the difference between square brackets and parentheses in regard to lists?

user_8902744 0
Viewed 507

As the title implies, I am unsure about the difference between square brackets and parentheses in regard to lists.

Two versions of Haskell's insert defined, one using square brackets, the other using parentheses:

insert' :: Int -> [Int] -> [Int]
insert' y [] = [y]
insert' y (x:xs) | y <= x = y:x:xs | otherwise = x : insert' y xs
----
insert' y [x:xs] | y <= x = y:x:xs | otherwise = x : insert' y xs

What is the reason the second definition of insert' doesn't work?

The error message it gives, for anyone wondering:

test.hs:3:12: error:
    • Couldn't match expected type ‘Int’ with actual type ‘[Int]’
    • In the pattern: x : xs
      In the pattern: [x : xs]
      In an equation for ‘insert'’:
          insert' y [x : xs]
            | y <= x = y : x : xs
            | otherwise = x : insert' y xs
  |
3 | insert' y [x:xs] | y <= x = y:x:xs | otherwise = x : insert' y xs
  |
type-mismatch recursion pattern-matching haskell types
2 Answers

As in almost all other languages, parentheses in Haskell don't really do anything. They help the parser know which things you intended to group together, and that's it; they don't change the meaning of the thing that's inside them, and if the parser could magically guess which way you intended to group things at every choice point we wouldn't need them at all. So all of these patterns behave exactly the same:

x
(x)
((x))
(((((((((x)))))))))

All of these patterns are also exactly the same:

x:xs
(x:xs)
((x:xs))
(((((((((x:xs)))))))))

Sometimes we must use one of the later ones -- like (x:xs) -- instead of the first one -- x:xs -- to inform the parser that we intended these things to be grouped together. But the parentheses don't otherwise change anything about what the pattern means.

Square brackets, on the other hand, are used for constructing lists. They have an actual run-time meaning: they allocate a new data structure in memory and initialize it. For example, 3 is a number, but [3] is a list with a single element, [3,4] is a list with two elements, [[3]] is a list of lists, and so on. The same behavior applies to patterns:

x -- match anything (even a list!) and bind x to its value
[x] -- match a list with a single element, and bind x to that element's value
[x,y] -- match a list with two elements, and bind x and y to those elements' values
[[x]] -- match a nested list; the outer and inner lists both have one element; bind x to the first element's first element

Now we can address your specific example. The pattern x:xs is a pattern that matches any list with at least one element, binding x to that first element and xs to the rest of the list. The pattern (x:xs) does exactly the same thing. The pattern [x:xs], on the other hand, matches a list with exactly one element, because there are square brackets; the only element of that list is then matched against the pattern x:xs, with the behavior described above.

One consequence of this is that x:xs can match lists with any type of element -- say, Int -- but [x:xs] can only match lists whose elements are lists.

user_7916040

(x:xs) as a pattern will match any non-empty list with x its head and xs its tail.

[x:xs] as a pattern will match a singleton list -- a list containing exactly one item -- which is a non-empty list, matching the pattern (x:xs). The pattern [x:xs] is in fact equivalent to the pattern [(x:xs)]. It is a nested pattern, and Haskell allows that. The outer pattern matches a singleton list, and the inner pattern matches a non-empty list. The parentheses in this position are optional.

That's why your second definition implies the type of the second argument is [[a]], but you've declared it to be [Int]. And Int can't match [a]. (That a is also determined to be an Int, since you compare x and y, and y the first argument is declared to be an Int, but that doesn't change anything).

     [ [a] ]
     [ Int ]
 ----------------
  ***mismatch***
user_8498910
Related