Come posso implementare una raccolta con indicizzazione O (1) e mutabilità in Haskell?

Se sto contando i occorrenze di caratteri di una stringa, ho potuto facilmente implementare questo utilizzando una matrice in un linguaggio imperativo, come il seguente:Come posso implementare una raccolta con indicizzazione O (1) e mutabilità in Haskell?

char values[256]; char c; 

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

posso vedere come fare questo in Haskell utilizzando qualcosa come Data.Vector.Mutable, che fornisce un'implementazione veloce di matrici int-index mutable.

Ma come potrei farlo facilmente utilizzando Haskell senza pacchetti e/o estensioni aggiuntivi? In altre parole, come posso implementare una raccolta O (1) veloce con indicizzazione e mutabilità?

fonte

2014-11-27 Jakub Arnold

@Lee non sono sicuro se si tratta solo di accedere all'indice, poiché anche la struttura dei dati deve essere mutabile (o fornire un modo per aggirare la mutabilità altrimenti mantenendo O (1)) –

Perché vuoi farlo senza pacchetti aggiuntivi? Se vuoi un array mutabile è esattamente ciò che è "Data.Vector.Mutable"! –

@TomEllis Solo perché c'è una libreria per fare qualcosa, non significa che si dovrebbe sempre usare la libreria. Sto cercando di capire come funziona sotto e come posso implementarlo in modo semplice. Re-implementare una libreria è il modo migliore per capire come funziona. –

L'implementazione di vector utilizza le funzioni GHC interne chiamate primops. Li potete trovare nel pacchetto ghc-prim che è cablato in GHC. Esso prevede, tra le altre, le seguenti funzioni di matrice:

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

Queste funzioni sono implementate da GHC sé, ma sono veramente basso livello. Il pacchetto primitive fornisce wrapper più eleganti di queste funzioni. Per gli array, questi sono:

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()

Ecco un semplice esempio utilizzando direttamente queste funzioni (IO è un 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

Naturalmente, in pratica, si sarebbe solo usare il pacchetto vector, che è molto più ottimizzato (stream fusion, ...) e anche più facile da usare.

fonte

2014-11-27 12:31:45 bennofs

Come posso implementare una raccolta con indicizzazione O (1) e mutabilità in Haskell?

risposta

Problemi correlati