O (1) tampão circular na Haskell?

Question

Eu estou trabalhando em um projeto de conceito pequeno em Haskell que requer um buffer circular. Eu consegui criar um tampão utilizando matrizes que contém o (1) de rotação, mas é claro que requer O (N) para a inserção / deleção. Eu encontrei uma implementação usando listas que aparece para tomar O (1) para a inserção e exclusão, mas uma vez que mantém uma lista à esquerda e à direita, atravessando uma certa fronteira ao rodar vai levar tempo O (N). Em uma linguagem imperativo, que poderia implementar um tampão circular duplamente ligado com o (1) de inserção, deleção, e rotação. Eu estou pensando que isso não é possível em uma linguagem puramente funcional como Haskell, mas eu gostaria de saber se eu estiver errado.

Answer 1

O ST mônada permite descrever e executar algoritmos imperativas em Haskell. Você pode usar STRefs para o ponteiros mutáveis ??de sua lista duplamente ligada.

algoritmos de auto-contido descrito usando ST executados usando runST. Diferentes execuções runST não podem compartilhar estruturas de dados ST (STRef, STArray, ..).

Se o algoritmo não é "auto-contido" e a estrutura de dados é necessário para ser mantida com operações de IO realizados entre seus usos, você pode usar stToIO para acessá-lo na mônada IO.

No que diz respeito se isso é puramente funcional ou não? - Eu acho que não é

Answer 2

Se você pode lidar com amortizado O (1) operações, você provavelmente poderia usar Data.Sequence do pacote de recipientes, ou Data.Dequeue do pacote dequeue. As antigas utilizações árvores dedo , enquanto o segundo usa o "banqueiro Dequeue" de Okasaki de Estruturas de dados puramente funcional (a versão anterior em linha aqui ).

Answer 3

Parece que você pode precisar de algo um pouco mais complicado do que isso (desde que você mencionou listas duplamente ligadas), mas talvez isso ajude. Esta função age como map sobre uma lista cíclica mutável:

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

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

E aqui está um que age como mapAccumL:

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

De qualquer forma, se o cuidado de elaborar ainda mais sobre o que exatamente suas necessidades de estrutura de dados para ser capaz de "fazer" eu estaria realmente interessado em ouvir sobre isso.

Editar : como camccann mencionado, você pode usar Data.Sequence para este, que de acordo com os documentos devem dar-lhe O1 complexidade de tempo (existe tal coisa como O1 amortizados tempo?) Para visualização ou adicionar elementos, tanto para os lados esquerdo e direito da sequência, assim como modificar as extremidades ao longo do caminho. Se isso vai ter o desempenho que você precisa, eu não tenho certeza.

Você pode tratar a "localização atual" como o fim esquerdo da seqüência. Aqui nós shuttle e para trás ao longo de uma sequência, produzindo uma lista infinita de valores. Desculpe se não compilar, eu não tenho GHC no 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'