Wie kann ich eine Sammlung mit O (1) Indizierung und Mutabilität in Haskell implementieren?

Wenn ich die Vorkommen von Zeichen in einer Zeichenfolge zu zählen, konnte ich dies mit einem Array in einer imperativen Sprache, wie die folgenden leicht implementieren:Wie kann ich eine Sammlung mit O (1) Indizierung und Mutabilität in Haskell implementieren?

char values[256]; char c; 

while (c = readChar()) { 
    values[c] += 1; 
}

ich sehen kann, wie dies in Haskell zu tun mit etwas wie Data.Vector.Mutable, das eine schnelle Implementierung von int-indizierten veränderbaren Arrays bereitstellt.

Aber wie könnte ich dies einfach mit nur Haskell ohne zusätzliche Pakete und/oder Erweiterungen tun? Mit anderen Worten, wie kann ich eine schnelle O (1) Sammlung mit Indizierung und Veränderbarkeit implementieren?

Quelle

2014-11-27 Jakub Arnold

@Lee nicht sicher, ob es nur um den Zugriff auf den Index geht, da die Datenstruktur auch veränderbar sein muss (oder eine Möglichkeit bieten, um die Veränderbarkeit zu umgehen, während das O (1) beibehalten wird) –

Warum möchten Sie es tun ohne zusätzliche Pakete? Wenn Sie ein veränderbares Array haben möchten, ist das genau das, wofür Data.Vector.Mutable steht! –

@TomEllis Nur weil es eine Bibliothek gibt, um etwas zu tun, bedeutet das nicht, dass Sie immer die Bibliothek benutzen sollten. Ich versuche zu verstehen, wie das darunter funktioniert und wie ich es selbst einfach umsetzen kann. Eine Bibliothek neu zu implementieren ist der beste Weg, um zu verstehen, wie es funktioniert. –

Die Implementierung von vector verwendet interne GHC-Funktionen namens Primops. Sie finden sie im Paket ghc-prim, das in GHC fest verdrahtet ist. Es bietet unter anderem die folgenden Array-Funktionen:

newArray# :: Int# -> a -> State# s -> (#State# s, MutableArray# s a#) 
readArray# :: MutableArray# s a -> Int# -> State# s -> (#State# s, a#) 
writeArray# :: MutableArray# s a -> Int# -> a -> State# s -> State# s

Diese Funktionen werden von GHC umgesetzt selbst, aber sie sind wirklich lowlevel. Das Paket primitive bietet schönere Wrapper für diese Funktionen. Für Arrays sind dies:

newArray :: PrimMonad m => Int -> a -> m (MutableArray (PrimState m) a) 
readArray :: PrimMonad m => MutableArray (PrimState m) a -> Int -> m a 
writeArray :: PrimMonad m => MutableArray (PrimState m) a -> Int -> a -> m()

Hier ist ein einfaches Beispiel dafür ist die Verwendung dieser Funktionen direkt (IO ist ein PrimMonad):

import Data.Primitive.Array 
import Control.Monad 

main :: IO() 
main = do 
    arr <- newArray 3 (0 :: Int) 
    writeArray arr 0 1 
    writeArray arr 1 3 
    writeArray arr 2 7 
    forM_ [0..2] $ \i -> putStr (show i ++ ":") >> readArray arr i >>= print

Natürlich in der Praxis würden Sie nur das vector Paket verwenden, die ist viel mehr optimiert (Stream-Fusion, ...) und auch einfacher zu bedienen.

Quelle

2014-11-27 12:31:45 bennofs

Wie kann ich eine Sammlung mit O (1) Indizierung und Mutabilität in Haskell implementieren?

Antwort

Verwandte Themen