Пытаясь понять этот блок кода в OCaml - PullRequest
Новая
       10

Пытаясь понять этот блок кода в OCaml

4 голосов
/ 24 января 2012

Я пытаюсь понять, что делает этот блок кода: 

let rec size x =
    match x with
      [] -> 0
    | _::tail -> 1 + (size tail) ;;

Я знаю, что это выражение вычисляет размер списка, но я не понимаю, где в коде оно уменьшает список один за другим. Например, я думаю, что нужно перейти от [1; 2; 3] к [2; 3] к [3], но где или как это происходит? Я не понимаю

Спасибо.

Ответы [ 5 ]

10 голосов
/ 24 января 2012

Список в OCaml строится рекурсивно с использованием конструктора пустого списка ([]) и cons (::). Так что [1; 2; 3] является синтаксическим сахаром 1::2::3::[].

Размер вычисляется путем уменьшения x на каждом шаге с использованием шаблона _::tail (_ означает, что мы игнорируем заголовок списка) и вызова той же функции size для tail. Функция в конечном итоге завершается, когда список пуст и шаблон [] успешен.

Вот краткая иллюстрация того, как size [1; 2; 3] вычисляется: 

   size 1::2::3::[]
~> 1 + size 2::3::[] // match the case of _::tail
~> 1 + 1 + size 3::[] // match the case of _::tail
~> 1 + 1 + 1 + size [] // match the case of _::tail
~> 1 + 1 + 1 + 0 // match the case of []
~> 3

В качестве примечания вы можете видеть на рисунке, что в стеке необходимо хранить много информации для вычисления size. Это означает, что ваша функция может привести к ошибке переполнения стека, если входной список длинный, но это другая история.

4 голосов
/ 24 января 2012

Каждый раз, когда вы сопоставляете список, вы можете сопоставить шаблон вида head::tail, где head получит значение первого элемента, а tail - остаток.Этот шаблон будет соответствовать любому непустому списку, потому что tail может быть пустым, но head должен существовать.

Во-вторых, любой шаблон, который вы подходите в Ocaml, если вы хотите, вы можете заменить переменную подчеркиванием наскажите «сопоставьте что-то здесь, но я не собираюсь использовать это на самом деле, поэтому я не буду называть это именем».Таким образом, в этой программе вместо записи head::tail -> 1 + (size tail) они пишут _::tail -> 1 + (size tail), поскольку на самом деле они не используют первый элемент, а просто обеспечивают его существование.

4 голосов
/ 24 января 2012

Согласно этой статье , в которой на самом деле есть конкретный пример, который вы обсуждаете:

Как мы видели, список может быть либо пустым (список имеет форму []), либо состоять из первого элемента (его голова) и подсписка (его хвост). Список тогда имеет вид h::t.

Приведенный оператор просто дает 0, если список соответствует пустому списку или использует сопоставление с образцом для извлечения головы (первый элемент) и хвоста (все остальные элементы), а затем использует рекурсию для получения длины хвоста.

Итак, _::tail уменьшает список, а 1 + (size tail) вычисляет размер. Бит перед | является, конечно, завершающим условием для рекурсии.

Это может быть более понятно (на мой взгляд), если рассматривать как: 

let rec size x = match x with
            []  ->  0
    |  _::tail  ->  1 + (size tail)
    ;;

(на самом деле это очень похоже на формат, используемый на связанной странице, я просто немного изменил его, чтобы выстроить в ряд символы ->).

4 голосов
/ 24 января 2012

На самом деле этот фрагмент кода использует возможности сопоставления с образцом для вычисления размера списка.

match означает, что вы попытаетесь заставить x ввести один из следующих шаблонов.

Первый [] означает, что ваш список пуст, поэтому его размер равен 0. А второй _::tail означает, что у вас есть один элемент (*), за которым следует остальная часть списка, поэтому в основном размер это 1 + size(rest of the list)

(*) Подчеркивание означает, что вам не важно значение этого элемента.

1 голос
/ 24 января 2012

Он использует сопоставление с образцом для извлечения хвоста списка (назвав его tail), а затем вызывает себя с хвостом.Возможно, недостающий кусок для вас - сопоставление с образцом.

...