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

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

Давайте попробуем реализовать основные типы данных: стек, очередь и дек — на языке 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#
Поделиться публикацией

Комментарии 11

    0
    Спасибо за статью, у меня вопрос немного не по теме. Подскажите пожалуйста как на F# реализовать утиную типизацию? На Scala это все выглядит очень просто:

    def inTheForest(duck: { def quack; def feathers }) = {
      duck.quack
      duck.feathers
    }
    


    Заранее спасибо.
      0
      Вот так можно:
      let inline getLen arg =
              (^a : (member Count: int) arg)
       
          let ra = ResizeArray<string>()
          let rl = Dictionary<string, string>()
      
          printfn "%i" (getLen ra)
          printfn "%i" (getLen rl)
      
        +1
        Накосячил с отступами, корректный вариант такой:

        let inline getLen arg =
            (^a : (member Count: int) arg)
         
        let ra = ResizeArray<string>()
        let rl = Dictionary<string, string>()
        
        printfn "%i" (getLen ra)
        printfn "%i" (getLen rl)
        
          0
          Спасибо,

          А вы не подскажете для чего в конце (^a : (member Count: int) arg) стоит arg? Мне не совсем ясна семантика. До него все понятно, это как в scala, тип ^a, у которого есть свойство Count типа int, но вот зачем тут arg? Заранее вам благодарен.
            +1
            Здесь
            ^a : (member Count: int)
            

            мы как-бы получаем поле в виде метода, а затем передаём ему «аргумент» — конкретный экземпляр.

            Здесь между Scala и F# существенное различие: в Scala будет произведена лишь проверка во время компиляции, во время выполнения же вызовы будут осуществляться через рефлексию, в F# же для каждого конкретного типа будет сгенерирована перегрузка.
              0
              Все понял, спасибо за пояснение.
                0
                Пожалуйста)
      0
      Вы пытаетесь писать на функциональном языке как на императивном — используя наиболее низкоуровневые концепции языка. Имхо — это стандартная ошибка новичков. Если так хочется сделать все через список (а не ввести свой тип данных на котором эти операции будут действительно работать оптимально), то лучше использовать высокоуровневые примитивы типа fold для этих задач. Там как минимум будет оптимизация tail call будет. Вообще написание своих собственных рекурсивных функций на стандартные типы данных — это антипаттерн для функциональных языков.
      Да кстати стандартный pop (вытаскивание элемента из стека или очереди) вполне решается вот такой функцией:

      let pop stk =
       match stk with
       |[] -> (None, [])
       |hd :: tail -> (Some(hd), tail)
      


      и использовать ее можно вот так:

      let (res, rest) = pop stk
      
        0
        Иммутабельный список — не самая удачная структура данных для очереди и дека. Очевидно, что или запись, или изъятие (а то и запись, и изъятие) происходят через полное копирование. Это и O(n) памяти, и O(n) времени.

        Предлагаю заглянуть в книгу Криса Окасаки, который посвятил функциональным структурам данных свою диссертацию.
        www.cs.cmu.edu/~rwh/theses/okasaki.pdf
        Тем более, что он пишет на другом диалекте ML — а именно, SML, так что перепереть на F# труда не составит.

        Заворачивать head и pop в монаду мейби (она же эмэлевская option) — на вкус и цвет. При наличии обычных функций проверки — необязательно; точнее, пусть оно кидает ошибки.
          0
          Не совсем понятно, зачем понадобилось делать стек, ибо большинство стандартных функций для работы со списками уже подходят.

          Что касается Дека и очереди — ваша реализация — это операции O(n) — а значит, совершенно не подходят.
          К счастью, есть структура, которая может работать O(1) с добавлением и в начало и в конец структуры — это пальчиковые деревья (Finger_tree)
          Вот, например, её реализация на Хаскеле:
          Data-Sequence
          Ну, а далее реализация дека (да и очереди) проще простого:

          import Data.Sequence
          
          type Deq = Seq
          
          pushDBegin :: Deq a -> a -> Deq a
          pushDBegin deq el = el  <| deq
          
          pushDEnd   deq el = deq |> el
          
          popDBegin :: Deq a -> (Maybe a,  Deq a)
          popDBegin = hd . viewr
            where
              hd EmptyR    = (Nothing, empty)
              hd (tl :> a) = (Just a,  tl)
          
          popDEnd = hd . viewl
            where
              hd EmptyL    = (Nothing, empty)
              hd (a :< tl) = (Just a,  tl)
          
          
          
          type Que = Seq
          
          pushQ :: Que a -> a -> Que a
          pushQ = pushDEnd
          
          popQ :: Que a -> (Maybe a, Que a)
          popQ = popDBegin
          
            0
            Я преследовал своей целью попытку реализовать функции самостоятельно, без использования готовых решений. Я прекрасно понимал, что изобретаю велосипед, и я не думал об оптимизации.
            Да и подключать встроенные модули мне тоже не хотелось.

          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.