You are viewing alexey_rom

Представление списков в ФП

Возник такой вопрос. Как устроены cons-списки, большей части читающих известно :) А мне сейчас пригодилось бы неизменяемое представление списков в неленивом функциональном языке с хвостовой рекурсией, которое хорошо поддерживает две операции:
1) Конкатенацию (и как частный случай добавление элементов в начало и конец списка). Желательно хотя бы амортизированное O(1), O(log N) тоже сойдёт.
2) Итерацию от начала к концу. Без переполнения стека, независимо от того, как строился список.

Вот из-за второго условия простые conc-списки меня не устраивают, нужно какое-то балансирование. И чем проще, тем лучше.

Благодаря наличию хвостовой рекурсии направо деревья могут расти спокойно, главное, чтобы не росли налево.

Известные мне варианты:
1) Vector в Clojure и Scala. Хорошо добавляет элементы в конец, плохо в начало.
2) 2-3 finger tree (например, Data.Sequence в Haskell). Сложная схема балансирования и, как результат, великоваты постоянные множители у асимптотик (хотя жить можно).

UPDATE: Simple Confluently Persistent Catenable Lists и Purely Functional, Real-Time Deques with Catenation.

Comments

В Окасаки же должно быть что-то такое.
Да, действительно нужно было посмотреть первым делом. Сейчас этим и займусь.
Ну конечно, 10.2.1 Lists with efficient catenation.

(Anonymous)

Сложная схема балансирования?! Вы ни с чем не перепутали? Перечитайте-ка на всякий случай "Finger Trees: A Simple General-purpose Data Structure" by Ralf Hinze and Ross Paterson http://www.soi.city.ac.uk/~ross/papers/FingerTree.pdf
Нет, не перепутал :) Конечно, сравнительно. Скажем, по сравнению с general balanced trees она сложная.

(Anonymous)

{-# LANGUAGE RankNTypes #-}
module Main where
import Prelude hiding(iterate)

type Cat a = forall s. (a -> s -> s) -> s -> s

singleton :: a -> Cat a
catenate :: Cat a -> Cat a -> Cat a
iterate :: (a -> s -> s) -> s -> Cat a -> s

singleton a f s = f a s
catenate a b f s = a f (b f s)
iterate f s a = a f s

main = putStrLn (show test)
    where
    test = iterate (:) [] list
    list = singleton 1 `catenate` singleton 2 `catenate` singleton (3::Int)
Это и есть conc-списки (в представлении через катаморфизм, но это дела, по-моему, не меняет).

(Anonymous)

Между прочим, если итерировать conc в CPS стиле, то будет O(n), но без использования стека.
Ну, с использованием пользовательского стека. Переполнения не будет, да.
да вы чего ребят? стандартный tailq реализуется за 5 минут, удовлетворяет всем требованиям..
Вот этот? Почти всем. Кроме главного -- персистентности :) Если есть неизменяемый вариант с теми же характеристиками, то скажите, куда смотреть :)
так ли действительно нужен немутабельный вариант? или там интересный алгоритм и неизвестно как будут конструироваться данные?
Да, нужен именно немутабельный. Иначе бы вопроса не было.
У меня возникла мысль занести этот пост в "Избранное", чтобы иногда перечитывать в воспитательных целях, если я воображу, что обладаю внушительным запасом знаний.

Фразу "Благодаря наличию хвостовой рекурсии, направо деревья могут расти спокойно" возьму на вооружение. ))
Ну хоть кому-то пригодился :) А мне нужно занести в "Избранное", чтобы запомнить: если вопрос по функциональным структурам данных, первым делом нужно открывать книгу Окасаки :)