Pull to refresh

Реализация стека, очереди и дека на языке F# в функциональном стиле

Reading time 5 min
Views 5.3K
Недавно я познакомился с концепцией функционального программирования. Возможно, в этой статье я изобретаю велосипед, однако я считаю, что эти действия являются весьма полезными для обучения, а также для более чёткого понимания функционального программирования.

Давайте попробуем реализовать основные типы данных: стек, очередь и дек — на языке F#, по возможности используя чистые функции. Естественно, они будут основаны на списках.

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

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

Стек


Прежде всего начнём со стека. В F# основным типом данных для хранения нескольких однотипных элементов является не массив, а список. Если перед нами стоит задача превратить список в стек, то какие функции нам понадобятся?

Во-первых, нам необходима функция для добавления элемента в вершину стека. Эта функция традиционно называется push. Однако эта функция нас особо не интересует, поскольку она очень просто реализуется:

let push stk el = el :: stk


Довольно простая функция, которая имеет тип 'a list -> 'a -> 'a list, однако не все дальнейшие функции позволят обращаться с собой таким простым способом.

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


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

Первый подход не может быть выполнен в функциональном стиле, поскольку это явный пример функции с побочным эффектом: значение стека возвращается как результат функции, и его удаление является побочным эффектом.
Более того, применяя первый подход, мы лишаемся и детерминированности функции: применение её к одному и тому же экземпляру стека даст нам разный результат.

Так что остановимся на втором подходе. Для этого напишем две функции: head, которая будет возвращать значение в вершине стека, и pop, которое будет возвращать список, лишённый вершины.

Будем разбираться с первой. Что нам необходимо возвратить? Всего возможно два варианта: стек пустой или стек не пустой. Если стек не пустой, то всё ясно: выводим элемент из вершины. А если стек пустой? Ведь вместо условных операторов в F# используется сопоставление шаблонов. У нас стоит ограничение, что при применении разных шаблонов должны возвращаться данные одинакового типа. На помощь приходят т. н. опциональные типы, которые принимают значения Some(x) или None.

Теперь мы можем написать функцию:
let head stk =
 match stk with
 |[] -> None
 |hd :: _ -> Some(hd)


Если мы посмотрим на тип функции head, мы увидим, что она имеет тип 'a list -> 'a option, т. е. принимает список в качестве параметра и возвращает значение опционального типа.
Функция работает следующим образом: приняв список stk, она смотрит на его значение. Если он пустой, т. е. stk = [], то она возвращает None, что соответсвует тому, что вершины у этого списка нет, если не пустой, то отделяет первый элемент списка от остальных и возвращает его в виде опционального типа. Знак подчёркивания в сопоставлении шаблонов означает, что функции неважно, что должно находиться в этом месте.
При этом наша функция является чистой: присутствует детерминированность, отсутствуют побочные эффекты.

Глядя на эту функцию, теперь мы легко напишем и функцию pop, которая будет в некотором роде симметрична, однако не будет нуждаться в опциональном типе, поскольку роль None будет выполнять пустой список:

let pop stk =
 match stk with
 |[] -> []
 |_:: tl -> tl


Эта функция имеет тип: 'a list -> 'a list

Таким образом, следующий код даёт нам все функции для работы со стеком.
let push stk el = el :: stk

let head stk =
 match stk with
 |[] -> None
 |hd :: _ -> Some(hd)

let pop stk =
 match stk with
 |[] -> []
 |_ :: tl -> tl


Очередь


Очередь отличается от стека тем, что добавление нового элемента происходит в конец списка, а извлечение происходит из начала очереди. Реализуем функции add (добавление элемента в очередь), head (кто сейчас стоит в очереди) и delque (удаление элмента из очереди). И если функции head и delque не вызывают сомнений, то попытка написать let head = que :: el приведёт к ошибке компиляции, поскольку оператор :: имеет тип 'a -> 'a list -> 'a list, т. е. левый операнд не может быть списком.

Проблема вновь решается с использованием сопоставления шаблонов, однако теперь у нас в ход вводятся рекурсивные функции для того, чтобы добраться до конца. Если очередь пустая, то ей всё равно, добавлять с конца или с начала, поскольку их нет, так что добавим в начало, которое одновременно будет концом. Если же список не пустой, то разобьём его на первый элемент и все остальные, и применим рекурсивно нашу функцию к оставшимся элементам списка.
let rec add que el = 
 match que with
 |[] -> el :: []
 |hd :: tl -> hd :: (add tl el) 


Таким образом, полный набор функций для очереди имеет вид:
let rec add que el = 
 match que with
 |[] -> el :: []
 |hd :: tl -> hd :: (add tl el) 

let  head que =
 match que with
 |[] -> None
 |hd :: _ -> Some(hd)

let delque que =
 match que with
 |[] -> []
 |_ :: tl -> tl


Дек


Наиболее интересная структура данных — это дек, или двунаправленная очередь, т. е. добавление и удаление элементов может происходить как с начала, так и с конца. По аналогии с функциями head и pop для стека введём функции tail и delend для дека. Здесь реализация уже будет поинтереснее. Нам нужен последний элемент, однако в функциональном программировании нет циклов. Как нам быть? Вновь на помощь приходит рекурсия, однако рано радоваться.
Если мы напишем совсем по аналогии:

let rec tail deq =
 match deq with
 |[] -> None
 |_ :: tl -> tail tl


то мы успешно получим None для любого аргумента. Это связано с тем, что любой список в F# представим в виде a = a :: [], т. е. если мы последовательно будем разматывать клубок списка, то в конце концов у нас ничего не останется.
Эта проблема решается добавлением всего лишь одного условия, если вспомнить, что оператор :: имеет тип 'a -> 'a list -> 'a list, т. е. операнд, стоящий слева от ::, должен иметь тип элемента списка, а не быть самим списком, поэтому изменим код следующим образом:
let rec tail deq =
 match deq with
 |[] -> None
 |hd :: [] -> Some(hd)
 |_ :: tl -> tail tl


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

С этим разобрались, а что нам делать с функцией delend? Нам надо заменить последний элемент списка, но как это сделать? Давайте вспоним, что оператор :: возвращает список и является ассоциативным справа, что позволяет рассмотреть следующий код:

let rec delend deq =
 match deq with
 |[] -> []
 |hd1 :: hd2 :: [] -> hd1 :: []
 |hd :: tl -> hd :: (delend tl)


Вот он, наш искомый код. Благодаря оператору :: в правой части мы не потеряем начало списка, а рекурсия закончится на предпоследнем элементе списка, создав новый список без бывшего последнего элемента.

Таким образом, для дека мы получаем следующий набор функций:
let addbegin deq el = el :: deq

let rec addend deq el = 
 match deq with
 |[] -> el :: []
 |hd :: tl -> hd :: (addend tl el) 

let  head deq =
 match deq with
 |[] -> None
 |hd :: _ -> Some(hd)

let delbegin deq =
 match deq with
 |[] -> []
 |_ :: tl -> tl

let rec tail deq =
 match deq with
 |[] -> None
 |hd :: [] -> Some(hd)
 |_ :: tl -> tail tl

let rec delend deq =
 match deq with
 |[] -> []
 |hd1 :: hd2 :: [] -> hd1 :: []
 |hd :: tl -> hd :: (delend tl)


Спасибо за внимание! Любой код, написанный в данной статье, может быть проверен в любой среде, допускающей программирование под F#
Tags:
Hubs:
+8
Comments 11
Comments Comments 11

Articles