map runSTArray su un elenco di STArray?

Question

Ho una funzione che crea in modo ricorsivo una lista appiattita di matrici da un albero che deve essere mutabile poiché i loro elementi vengono aggiornati spesso durante la loro creazione. Finora sono venuto su con una soluzione ricorsiva che ha la firma:

doAll :: .. -> [ST s (STArray s (Int, Int) Int)] 

Il motivo per cui non ritorno il [UArray (Int,Int) Int] direttamente è perché doAll si chiama in modo ricorsivo, modifica elementi delle matrici in lista e aggiunge nuove matrici . Non voglio congelare e scongelare inutilmente le matrici.

Fin qui tutto bene. Posso ispezionare il n matrice -esimo (di tipo Array (Int, Int) Int) in ghci

runSTArray (matrices !! 0) 
runSTArray (matrices !! 1) 

e in effetti io ottenere i risultati corretti per il mio algoritmo. Tuttavia, non ho trovato un modo per mappare runSTUArray sopra la lista che viene restituito dal doAll:

map (runSTArray) matrices 

Couldn't match expected type `forall s. ST s (STArray s i0 e0)' 
      with actual type `ST s0 (STArray s0 (Int, Int) Int)' 

Lo stesso problema si verifica se provo a valutare in modo ricorsivo oltre l'elenco o cercare di valutare i singoli elementi avvolti in un funzione

Qualcuno potrebbe spiegare cosa sta succedendo (non ho veramente capito le implicazioni della parola chiave forall) e come è stato possibile valutare gli array nell'elenco?

Answer 1

Questa è una sfortunata conseguenza del tipo di trucco che rende ST sicura. Per prima cosa, devi sapere come funziona la ST. L'unico modo per passare dalla monade ST a codice puro è con la funzione runST o altre funzioni su di essa come runSTArray. Questi sono tutti nella forma forall s.. Ciò significa che, al fine di costruire una matrice da uno STArray, il compilatore deve essere in grado di determinare che può sostituire qualsiasi tipo a cui piace per la variabile di tipo s all'interno di runST.

Considerare ora la funzione map :: (a -> b) -> [a] -> [b]. Questo mostra che ogni elemento nell'elenco deve avere esattamente lo stesso tipo (a), e quindi anche lo stesso s. Ma questo vincolo extra viola il tipo di runSTArray, che dichiara che il compilatore deve essere in grado di sostituire liberamente altri valori per s.

È possibile aggirare questo definendo una nuova funzione di congelare prima le matrici all'interno della monade ST, quindi eseguire l'azione risultante ST:

runSTArrays :: Ix ix => (forall s. [ST s (STArray s ix a)]) -> [Array ix a] 
runSTArrays arrayList = runST $ (sequence arrayList >>= mapM freeze) 

Annotare il forall occorre estendere RankNTypes.

Answer 2

Hai appena rimbalzato contro i limiti del sistema di tipi.

Il runSTArray ha un tipo di classifica più elevato. Devi passargli un'azione ST la cui variabile di stato è unica. Tuttavia, in Haskell normalmente non è possibile avere tali valori nelle liste.

Il tutto è uno schema intelligente per garantire che i valori che si producono in un'azione ST non possano sfuggire da lì. Il che significa che sembra che il tuo design sia in qualche modo rotto.

Un suggerimento: non è in grado di elaborare i valori in un'altra azione ST, come

sequence [ ... your ST s (STArray s x) ...] >>= processing 
    where 
    processing :: [STArray s x] -> ST s (your results)