Неизменяемая очередь на F#

    Введение


    Прочитав недавно статью про список на 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”
    • +18
    • 6,7k
    • 4
    Поделиться публикацией

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

      +3
      Сложность извлечения в худшем случае равна сложности разворота списка O(N)
      Добавлю: но в среднем она составляет O(1). Более того, амортизированное время извлечения записи равно O(1) даже в худшем случае. Это связано с тем, что любой элемент участвует в операции «разворачивания» только один раз, и перед этим участием должен быть вставлен в очередь.
        0
        Это я хотел приберечь для следующей статьи.
        +2
        Я бы хотел заострить внимание читателей на книге Криса Окасаки, про которую вы упомянули в конце. Так вот. Вещь — уникальная. Читается как роман. Если вы хотите разобраться как в функциональном мире работают классические структуры данных — это то, что вам нужно.

        Книга является переизданием диссертации Криса, которую он готовил к получению степени Ph.D в 1996 году. Сама же книга была издана двумя годами позже с добавлением первых двух (или трех) глав. Крис, писал в своем блоге, что его жена, каждый раз удивляется, когда они получают чек от продажи книги, говоря при этом: «О, кто-то это еще покупает».

        Книга интересна тем, что там впервые мире функционального программирования описаны некоторые техники. Например, Крис первым придумал полностью функциональную реализацию красно-черного дерева, которая теперь используется и в Haskell и в Scala и в других популярных вещах. Или например, там можно найти идеи по конкатенации двух связных списков за O(1), при этом сохраняя персистентность структур.

        К слову, я сам читая книгу, пытаюсь реализовать разобранные структуры на Scala. Вот проект на GitHub: github.com/vkostyukov/scalacaster
          0
          Добавлю, что готовится перевод книги на русский язык.

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