O(1) búfer circular en haskell?

functional-programming circular-buffer

Question

Estoy trabajando en un pequeño proyecto conceptual en Haskell que requiere un búfer circular. Me las arreglé para crear un búfer utilizando matrices que tienen una rotación O (1), pero, por supuesto, requiere O (N) para la inserción / eliminación. He encontrado una implementación que usa listas que parecen tomar O (1) para la inserción y eliminación, pero como mantiene una lista a la izquierda y a la derecha, cruzar un borde determinado al girar tomará O (N) tiempo. En un lenguaje imperativo, podría implementar un búfer circular doblemente enlazado con inserción, eliminación y rotación O (1). Estoy pensando que esto no es posible en un lenguaje puramente funcional como Haskell, pero me encantaría saber si estoy equivocado.

Answer 1

Parece que es posible que necesites algo un poco más complicado que esto (ya que mencionaste listas con doble enlace), pero tal vez esto ayude. Esta función actúa como un map sobre una lista cíclica mutable:

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

Utilizar como

*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...]

Y aquí hay uno que actúa como mapAccumL:

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

De todos modos, si le interesa elaborar aún más en qué es exactamente lo que su estructura de datos necesita para poder "hacer", estaría realmente interesado en saberlo.

EDITAR : como mencionó camccann, puede usar la Data.Sequence de Data.Sequence para esto, que de acuerdo con los documentos debería darle una complejidad de tiempo O1 (¿existe el tiempo amortizado O1?) Para ver o agregar elementos en los lados izquierdo y derecho de la secuencia, así como la modificación de los extremos a lo largo del camino. Si esto tendrá el rendimiento que necesita, no estoy seguro.

Puede tratar la "ubicación actual" como el extremo izquierdo de la secuencia. Aquí nos desplazamos de ida y vuelta a lo largo de una secuencia, produciendo una lista infinita de valores. Lo siento si no se compila, no tengo GHC en este momento:

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''

Answer 2

Si puede lidiar con las operaciones O (1) amortizadas , probablemente podría usar Data.Sequence del paquete de contenedores o Data.Dequeue del paquete de Data.Dequeue de cola. El primero utiliza árboles de dedos , mientras que el segundo utiliza la "Cola de salida del banquero" de las Estructuras de datos puramente funcionales de Okasaki (una versión anterior en línea here ).

Answer 3

La mónada ST permite describir y ejecutar algoritmos imperativos en Haskell. Puede usar STRefs para los punteros mutables de su lista doblemente enlazada.

Los algoritmos autocontenidos descritos utilizando ST se ejecutan utilizando runST . Las runST ejecuciones de runST no pueden compartir estructuras de datos ST ( STRef , STArray , ..).

Si el algoritmo no es "autocontenido" y se requiere que la estructura de datos se mantenga con las operaciones de IO realizadas entre sus usos, puede usar stToIO para acceder a él en la mónada de IO .

Respecto a si esto es puramente funcional o no, supongo que no lo es.