O (1) круговой буфер в haskell?

Я работаю над небольшим концептуальным проектом в Haskell, который требует круговой буфер. Мне удалось создать буфер с использованием массивов, у которых есть O (1) вращение, но, конечно, для вывода/удаления требуется O (N). Я нашел реализацию, используя списки, которые, как представляется, принимают O (1) для вставки и удаления, но поскольку он поддерживает левый и правый список, пересечение определенной границы при вращении займет время O (N). На императивном языке я мог бы реализовать двусвязный круговой буфер с установкой, удалением и вращением O (1). Я думаю, что это невозможно на чисто функциональном языке, таком как Haskell, но я бы хотел узнать, не ошибаюсь ли я.

Ответ 1

ST Монада позволяет описывать и выполнять императивные алгоритмы в Haskell. Вы можете использовать STRef s для изменяемых указателей вашего дважды связанного списка.

Автономные алгоритмы, описанные с использованием ST, выполняются с помощью runST. Различные runST исполнения могут не разделять структуры данных ST (STRef, STArray,..).

Если алгоритм не является "автономным", и структура данных требуется поддерживать с помощью операций ввода-вывода, выполняемых между его использованием, вы можете использовать stToIO для доступа к нему в монаде IO.

Относительно того, является ли это чисто функциональным или нет, я полагаю, что это не так?

Ответ 2

Если вы можете справиться с амортизированными операциями O (1), вы, вероятно, можете использовать либо Data.Sequence из пакета контейнеров, либо Data.Dequeue из пакета dequeue. Первый использует деревья пальцев, в то время как последний использует "Banker Dequeue" из Okasaki Чисто функциональные структуры данных (предварительная версия онлайн здесь).

Ответ 3

Похоже, вам может понадобиться нечто более сложное, чем это (поскольку вы упомянули двусвязные списки), но, возможно, это поможет. Эта функция действует как map по изменяемому циклическому списку:

mapOnCycling f = concat . tail . iterate (map f)

Используйте как:

*Main> (+1) `mapOnCycling` [3,2,1]

[4,3,2,5,4,3,6,5,4,7,6,5,8,7,6,9,8,7,10,9...]

И вот тот, который действует как mapAccumL:

mapAccumLOnCycling f acc xs = 
    let (acc', xs') =  mapAccumL f acc xs
     in xs' ++ mapAccumLOnCycling f acc' xs'

В любом случае, если вы хотите уточнить, что именно ваша структура данных должна "делать", мне было бы очень интересно услышать об этом.

РЕДАКТИРОВАТЬ: как упоминалось в Camcann, вы можете использовать Data.Sequence для этого, который согласно документам должен дать вам сложность времени O1 (есть ли такая вещь, как O1, амортизированное время?) для просмотра или добавление элементов как к левой, так и к правой сторонам последовательности, а также к модификации концов по пути. Будет ли это иметь производительность, в которой вы нуждаетесь, я не уверен.

Вы можете рассматривать "текущее местоположение" как левый конец последовательности. Здесь мы перемещаемся вперед и назад вдоль последовательности, создавая бесконечный список значений. Извините, если он не компилируется, у меня нет GHC на данный момент:

shuttle (viewl-> a <: as) = a : shuttle $ rotate (a+1 <| as)
    where rotate | even a    = rotateForward
                 | otherwise = rotateBack
          rotateBack (viewr-> as' :> a')    = a' <| as'
          rotateForward (viewl-> a' <: as') = as' |> a'