Введение

Прочитав недавно статью про список на Haskell, решил тоже немного рассказать о реализации базовых структур на ФЯП (F#). Статья не несёт практической ценности, поскольку готовых реализаций полно в интернете. Цель статьи — рассказать о том, как можно реализовать неизменяемую очередь на F# и как она работает.
Для начала немного терминологии.
F# — это язык программирования из семейства .NET, который, помимо объектно-ориентированного и императивного подходов, реализует функциональный подход в программировании.
Неизменяемые объекты – это такие объекты, которые будучи созданными один раз, в дальнейшем не могут быть изменены. Например, в C# есть такой тип данных, как string, экземпляры которого являются неизменяемыми. Добавляя символ в строку, вы получаете новую строку и имеете неизменной старую. Подробнее тут.

Односвязный список

Для реализации очереди нам понадобится односвязный список. Напомню, что односвязный список — это такая структура данных, каждый элемент которой содержит хранимое значение и ссылку на предыдущий элемент.
То же самое на F#:

type public 'a List = //Объявление типа List с generic-параметром 'a, указывающим тип хранимых значений     | Empty                  //Пустой список     | Node of 'a * 'a List    //Пара: значение - остальной список ("хвост") 

Эта запись означает, что список может быть либо пустым, либо представлять из себя пару «голова»-«хвост», где «хвост» тоже список.
Рассмотрим основные операции над списком и оценим их сложность.

Добавление элемента в список

Чтобы добавить элемент и при этом оставить неизменным старый список, нужно создать новый список, где голова – добавляемый элемент, хвост – старый список. На F# записывается одной строкой:

member this.Cons x = Node(x, this) 

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

На рисунке List1 – список до добавления элемента, List2 – список после добавления элемента. При этом List1 также является «хвостом» списка List2.
Очевидно, что сложность добавления элемента не зависит от длины списка и равна O(1).

Извлечение элемента из списка

Извлечь элемент так же просто, как и добавить. Последний добавленный элемент просто берём из «головы»; для получения списка без этого элемента, берём «хвост».

member this.Head  =           match this with             | Empty -> failwith "Empty stack"             | Node(head, tail) -> head member this.Tail =          match this with             | Empty -> failwith "Empty stack"             | Node(head, tail) -> tail 

Очевидно, что сложность и этих операций — О(1).

Разворот списка

Ещё одна полезная операция над списком – разворот, т.е. изменение порядка следования элементов. Для разворота необходимо последовательно извлекать элементы из оригинального списка и помещать их в новый. Новый и старый списки не будут иметь общих данных. Сложность будет всегда O(N). Код и иллюстрация ниже:

let rec reverse destList sourceList =     match sourceList with          | Empty -> destList          | Node(sourceHead, sourceTail) ->  reverse (Node(sourceHead, destList)) sourceTail 

На рисунке List1 – список до разворота, List2 – после.

Очередь

Односвязный список с операциями добавления и извлечения элементов идеально подходит для реализации стека. Однако, если взять пару таких списков, можно реализовать очередь.
Очередь — структура данных с принципом доступа к элементам «первый пришёл — первый вышел» (FIFO).
Для реализации очереди понадобятся тыловой (rear) список, в который добавляются новые элементы, и фронтальный (front) список, из которого элементы извлекаются.

type 'a Queue (front:'a List, rear: 'a List)  = // Объявление типа Queue как пары списков     static member Empty = Queue(List.Empty, List.Empty) // Пустая очередь - пара пустых списков 

Добавление элемента в очередь

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

    member this.Snoc value = Queue(front, rear.Cons value) 

Очевидно, что оценка сложности добавления элемента в очередь совпадает с оценкой сложности добавления элемента в односвязный список – O(1).

Извлечение элемента из очереди

Перед тем, как извлечь элемент из фронтального списка, проверяем не пуст ли он. Если он пуст, берём тыловой и разворачиваем его – теперь он фронтальный, а тыловым назначаем пустой список. Сложность извлечения в худшем случае равна сложности разворота списка O(N).

    let frontToBack =          match front, rear with              |Empty, rear -> (rear.Reverse, Empty)              |x -> (x)                  member this.Head =          match frontToBack with             | Empty, _ -> failwith "Empty or not reversed"             | List.Node(a, __), _ -> a      member this.Tail =          match frontToBack with             |Empty, _ -> failwith "Empty"             |List.Node(a, tail), r -> Queue(tail, r) 

Ниже приведена иллюстрация «из жизни» очередей, где отображено последовательное выполнение операций добавления и извлечения.

На рисунке схематично изображены четыре очереди: А – пустая очередь, Б – очередь после последовательного добавления чисел 1, 2, 3 и 4, В – очередь после извлечения одного элемента (числа 1), Г – очередь после добавления числа 5.

Заключение

Рассмотренный в начале статьи односвязный список может быть использован не только как стек, но и как коллекция с произвольным доступом. Для этого понадобятся операции вставки и удаления. Сложность их зависит от места вставки/удаления и в худшем случае равна O(N). Реализацию оставляю за читателем.
И список, и очередь для некоторых операций имеют не самую лучшую сложность — O(N). Ситуация может быть улучшена вплоть до O(1), если в реализации правильно применить ленивые вычисления. Как это делается, я расскажу в следующей статье, если уважаемый Читатель проявит к теме интерес.

Используемая литература

В качестве основного источника информации использовалась книга Chris Okasaki “Purely Functional Data Structures”