I don't understand how Haskell can destructure the array to a tuple

e.g., why this works

head :: [a] -> a 
head (x:xs) = x 

But this does not work

head :: [a] -> a 
head [x:xs] = x 

it's unintuitive to me

CodePudding user response：

(x:xs) is not a tuple, (x, xs) is a pattern for a 2-tuple. (x:xs) is short for ((:) x xs) where (:) is (one of the two) data constructors for a list. The other one is [], the empty list.

The (:) data constructor has two fields: the first one (here x) is the head that points to the first item of the list, and the second one (here xs) points to the list of the remaining elements. So this looks like a linked list.

[x:xs] is a short variant of [(x:xs)], so it binds with a list of lists where the outer list contains a single element, and that single element matches with (x:xs) so a non-empty list with x the first item of the only sublist, and xs the remaining elements of that sublist.

CodePudding user response：

why this works

head :: [a] -> a 
head (x:xs) = x 

But this does not work

head :: [a] -> a 
head [x:xs] = x 

This is a very common source of difficulty for people learning Haskell. These look similar in some cases, but mean different things:

• The type [a] is equivalent to [] a, meaning “the type of lists of zero or more elements that all have type a”.

• The pattern [p] is equivalent to p : [] and (:) p [], meaning “match a list of exactly one element that matches the pattern p”.

Note that a list pattern with a variable at the end matches any number of remaining elements, but if it ends with “nil” [] then it matches a fixed number of elements. Here are some examples for lists of length n:

• xs — n ≥ 0 — more than zero elements; any list
• p : xs — n ≥ 1 — more than one element; non-empty lists
• p₁ : p₂ : xs — n ≥ 2 — more than two elements
• p₁ : p₂ : p₃ : xs — n ≥ 3 — &c.
• …
• [] — n = 0 — exactly zero elements; empty lists
• [p] — n = 1 — exactly one element; singleton lists
• [p₁, p₂] — n = 2 — exactly two elements
• [p₁, p₂, p₃] — n = 3 — &c.
• …

Writing x : xs, which is the same as (:) x xs, matches a list of one or more elements. Putting that in parentheses (x : xs) is equivalent, it’s only necessary because of precedence rules: head x : xs means (head x) : xs, which is a valid expression but not a valid pattern.

Writing [x : xs], which is the same as (x : xs) : [] and (:) ((:) x xs) [], matches a list of exactly one element ([ e ]) where that element matches a list of one or more elements (e = x : xs). Here are some examples:

• let { x : xs = [1] } in (x, xs) evaluates to (1, []) because:
  • x : xs matches 1 : []
    • x = 1
    • xs = []
  • And these are all equivalent:
    • [1]
    • 1 : []
    • (:) 1 []
• let { x : xs = [1, 2, 3] } in (x, xs) evaluates to (1, [2, 3]) because:
  • x : xs matches 1 : 2 : 3 : []
    • x = 1
    • xs = [2, 3]
  • And these are all equivalent:
    • [1, 2, 3]
    • 1 : [2, 3]
    • 1 : 2 : [3]
    • 1 : 2 : 3 : []
    • (:) 1 ((:) 2 ((:) 3 []))
• let { x : xs = "hi" } in (x, xs) evaluates to ('h', "i") because:
  • x : xs matches 'h' : 'i' : []
    • x = 'h'
    • xs = "i"
  • And these are all equivalent:
    • "hi"
    • 'h' : "i"
    • 'h' : 'i' : []
    • (:) 'h' ((:) 'i' [])
• let { [x : xs] = [[1]] } in (x, xs) evaluates to (1, []) because:
  • [ x : xs ] matches [ [1] ]
  • x : xs matches 1 : []
    • x = 1
    • xs = []
• let { [x : xs] = ["yo"] } in (x, xs) evaluates to ('y', "o") because:
  • [ x : xs ] matches [ ["yo"] ]
  • x : xs matches 'y' : 'o' : []
    • x = 'y'
    • xs = "o"
• Neither x : xs nor [x : xs] matches an empty list []
• [x : xs] does not match ["ya", "no"] because x : xs : [] does not match "ya" : "no" : [], because [] does not match "no" : []
• [x : xs] does not match [[]] because x : xs does not match []