Статьи

Эрланг: кортежи и списки

Сентябрь 7, 2018

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

И кортежи, и списки представляют собой набор значений; однако некоторые практические правила (imho) для выбора между ними:

  • кортежи имеют дело с разнородными значениями, а списки являются домогенными. Затем кортеж обычно создается как последовательность значений разных типов, в то время как все значения списка относятся к одному и тому же типу. Эта структура и дифференциация массива верны и в Python.
  • Кортежи и списки сопоставляются с шаблоном по-разному (мы увидим больше при написании кода соответствия шаблону, конечно).
  • Кортежи имеют O (1) произвольный доступ, в то время как списки имеют O (N) произвольный доступ, будучи построенными из cons-ячеек.
  • В общем случае структуры фиксированного размера моделируются как кортежи, а последовательности из N значений (где N изменяется во время выполнения) моделируются как списки.

Кортеж

Кортежи Эрланга похожи по синтаксису на Python:

1> MyTuple = {number, 42}.
{number,42}
2> tuple_size(MyTuple).
2
3> element(1, MyTuple).
number
4> element(2, MyTuple).
42

И, конечно, они неизменны, как и любая другая ценность:

5> setelement(2, MyTuple, 43).
{number,43}
6> MyTuple.
{number,42}

Они могут иметь любое количество значений:

7> {true, 23, "Hello"}.
{true,23,"Hello"}

И пустой кортеж это:

8> {}.                 
{}

Списки

Списки строятся как последовательность cons-ячеек (одна из базовых структур данных LISP; cons означает конструкцию *). Каждая cons-ячейка состоит из значения и указателя на другую cons-ячейку, которая может быть пустой.

Таким образом, список [1, 2, 3] состоит из трех cons-ячеек:

p1: [1, p2]
p2: [2, p3]
p3: [3, p_to_empty_list]

Списки могут быть построены как последовательности или даже путем непосредственного указания cons-ячеек. В первом случае значения разделяются `,`, а во втором они разделяются `|`:

1> []
1> .
[]
2> [1].
[1]
3> [1, 2].
[1,2]
4> [1 | [2]].
[1,2]
5> [1, 2, 3].
[1,2,3]
6> [1 | [2 | [3]]].
[1,2,3]

Каждая функция, работающая со списками, определяется в терминах двух примитивов, head и tail, которые возвращают соответственно первый элемент списка и остальную часть списка с удаленным этим элементом.

В то время как в других языках эти функции представлены как head / 1 и tail / 1 (car и cdr для друзей), в Erlang они реализованы посредством сопоставления с образцом; это означает, что они встроены в синтаксис языка. Наше небольшое упражнение на сегодня — написать эти конструкции как обычные функции, чтобы представить, как сопоставление с образцом работает в списках.

голова / 1

Давайте начнем с простого случая: пустой список. Если вы запрашиваете первый элемент такого списка, наша реализация должна вызвать ошибку, поскольку такого элемента нет.

#!/usr/bin/escript
head([]) -> throw(error).

main(_) -> head([]).

Это действительно показывает:

escript: exception throw: error
  in function  erl_eval:local_func/5
  in call from escript:interpret/4
  in call from escript:start/1
  in call from init:start_it/1
  in call from init:start_em/1

когда выполнено.

Что случилось? Мы можем поместить литеральные значения в формальные аргументы функции, и тело функции будет выполнено, только если значения соответствуют этим литералам. Конечно, это также означает, что когда мы выполняем:

main(_) -> head([1]).

мы получаем:

escript: exception error: {function_clause,[{local,head,[[1]]}]}

поскольку функция определена только для [] в качестве аргумента.

Давайте добавим еще один пункт, чтобы он работал и для списков из 1 элемента:

#!/usr/bin/escript
head([]) -> throw( error);
head([Element]) -> Element.

main(_) -> E = head([1]),
           io:format("Head: ~p~n", [E]).

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

Здесь мы не использовали буквальный шаблон, так как мы не знаем, что в списке вообще. Мы использовали имя переменной, так что Element заполняется значением единственного элемента списка.

Теперь мы можем расширить код, чтобы он работал со списками с несколькими значениями:

#!/usr/bin/escript
head([]) -> throw( error);
head([Element]) -> Element;
head([Element | _Tail]) -> Element.

main(_) -> io:format("Head of [1]: ~p~n", [head([1])]),
           io:format("Head of [1, 2]: ~p~n", [head([1, 2])]).

Мы используем _Tail вместо Tail, чтобы сказать Эрлангу, что нам не нужно значение этого аргумента, но он должен существовать.

На самом деле, мы знаем, что [1] на самом деле [1 | []] , поэтому мы можем немного упростить этот код, так как третье предложение будет соответствовать случаю списка из одного элемента:

#!/usr/bin/escript
head([]) -> throw( error);
head([Element | _Tail]) -> Element.

main(_) -> io:format("Head of [1]: ~p~n", [head([1])]),
           io:format("Head of [1, 2]: ~p~n", [head([1, 2])]).

Вы не ограничены сопоставлением с образцом для работы со списками: изучите модуль lists *, чтобы увидеть, как member (), nth () или length () можно использовать для проверки наличия элемента, чтения одного значения или вычисления длины список.

На сегодня мне не хватает места, поэтому я оставляю аналогичную реализацию tail / 1 в качестве упражнения для читателя.

Выводы

Кортежи и списки являются базовыми структурами данных Erlang. Упражняйтесь с ними и с сопоставлением с шаблоном в оболочке, чтобы убедиться, что вы знаете, как манипулировать переменными, прежде чем перейти от определения функций к их совместной работе.

44
Share: