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

[alexey_rom]

Возник такой вопрос. Как устроены cons-списки, большей части читающих известно :) А мне сейчас пригодилось бы неизменяемое представление списков в неленивом функциональном языке с хвостовой рекурсией, которое хорошо поддерживает две операции

Comments

[antilamer]

В Окасаки же должно быть что-то такое.

[alexey_rom]

Да, действительно нужно было посмотреть первым делом. Сейчас этим и займусь.

[alexey_rom]

Ну конечно, 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

[alexey_rom]

Нет, не перепутал :) Конечно, сравнительно. Скажем, по сравнению с 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)

[alexey_rom]

Это и есть conc-списки (в представлении через катаморфизм, но это дела, по-моему, не меняет).

[anonymous]

Между прочим, если итерировать conc в CPS стиле, то будет O(n), но без использования стека.

[alexey_rom]

Ну, с использованием пользовательского стека. Переполнения не будет, да.

[zevlg]

да вы чего ребят? стандартный tailq реализуется за 5 минут, удовлетворяет всем требованиям..

[alexey_rom]

Вот этот? Почти всем. Кроме главного -- персистентности :) Если есть неизменяемый вариант с теми же характеристиками, то скажите, куда смотреть :)

[zevlg]

так ли действительно нужен немутабельный вариант? или там интересный алгоритм и неизвестно как будут конструироваться данные?

[alexey_rom]

Да, нужен именно немутабельный. Иначе бы вопроса не было.