alexey_rom: (Default)
Возник такой вопрос. Как устроены 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.
alexey_rom: (Default)
Я и не знал, что такое там есть. Из статьи Polymorphic Embedding of DSLs:

trait Regions {
...
type Region
...
}

def program(semantics : Regions) : semantics.Region = ...

Как видно, возвращаемый тип зависит от аргумента. Это, конечно, не полные зависимые типы, но само по себе весьма неслабо. Насколько понимаю, это пока экспериментальная фича...

Profile

alexey_rom: (Default)
alexey_rom

April 2012

S M T W T F S
1 234567
89 1011121314
15161718192021
22232425262728
2930     

Syndicate

RSS Atom

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Sep. 25th, 2017 06:20 am
Powered by Dreamwidth Studios