Что означает сопоставление с образцом h :: t в OCaml?

Question

Я читаю https://ocaml.org/learn/tutorials/99problems.html, и у него есть 2 примера:

# let rec last_two = function
    | [] | [_] -> None
    | [x;y] -> Some (x,y)
    | _::t -> last_two t;;

Я понимаю первый: _::t означает, что шаблон соответствует чему угодно и назову его t

Но на

# let rec at k = function
    | [] -> None
    | h :: t -> if k = 1 then Some h else at (k-1) t;;

Я не понимаю, что означает h. Для меня это должно быть _:: t -> ..., чтобы сопоставить что-нибудь и назвать это t

Answer 1

Шаблон _ :: t не означает, что вы говорите. Он соответствует любому непустому списку и вызывает конец списка t.

Шаблон h :: t соответствует любому непустому списку, вызывает заголовок списка h (один элемент, первый) и хвост списка t (ноль или более элементов после первого).

Оператор :: является конструктором списка (часто его называют "cons"), поэтому эти шаблоны соответствуют спискам.

Вот примеры :: в качестве конструктора списка:

# true :: [];;
- : bool list = [true]
# 1 :: [2; 3];;
- : int list = [1; 2; 3]

Как обычно в OCaml, шаблон для списка использует тот же синтаксис, что и конструктор.

# match [1;2;3] with [] -> None | h :: t -> Some (h, t);;
- : (int * int list) option = Some (1, [2; 3])

Answer 2

Шаблон h::t сопоставляет начало и конец списка с переменными h и t. Поэтому, если я сопоставлю шаблон следующим образом:

match [1; 2; 3] with
| h::t -> (* Some code... *)

h будет иметь значение 1, а t будет иметь значение [2; 3].

:: является конструктором . Сопоставление с образцом в этом образце сопоставляется с конструкторами. Они создают новый тип данных из двух значений. :: является конструктором, а его тип, list, является рекурсивным. Вот примерное определение типа list:

type 'a list =
    | []
    | (::) 'a ('a list)

;;

Таким образом, тип list является рекурсивным, потому что его конструктор, ::, вызывает сам себя.

Честно говоря, я мог бы написать половина книги в списках. Они - хлеб с маслом функциональных языков программирования.

Если вам интересно, почему вы не можете сопоставить шаблоны с операторами , вот почему. Вы не можете сопоставлять шаблоны для операторов, только конструкторы.