trasferimento di un ciclo continuo imperativo in haskell idiomatico

Question

Ho alcune difficoltà nel trasferire algoritmi imperativi in ​​uno stile funzionale. Il concetto principale che non riesco a comprendere è come riempire le sequenze di valori in base alla loro posizione nella sequenza. Come sarebbe una soluzione idiomatica per il seguente algoritmo in Haskell?

A = unsigned char[256] 
idx <- 1 
for(i = 0 to 255) 
    if (some_condition(i)) 
     A[i] <- idx 
     idx++ 
    else 
     A[i] = 0; 

L'algoritmo in pratica crea una tabella di ricerca per la funzione di mappatura di un istogramma.

Conosci qualche risorsa che potrebbe aiutarmi a capire meglio questo tipo di problema?

Answer 1

Una delle idee fondamentali di programmazione funzionale è esprimere algoritmi come dati trasformazioni. In un linguaggio pigro come Haskell, possiamo anche fare un passo avanti e pensare a strutture dati pigre come calcoli reificati. In un senso molto reale, gli elenchi di Haskell sono più simili agli anelli delle normali liste concatenate: possono essere calcolati in modo incrementale e non devono necessariamente esistere in memoria tutti in una volta. Allo stesso tempo, otteniamo ancora molti dei vantaggi di avere un tipo di dati come tale capacità di passarlo e controllarlo con la corrispondenza dei modelli.

Con questo in mente, il "trucco" per esprimere un ciclo for con un indice è creare un elenco di tutti i valori che può assumere. Il vostro esempio è probabilmente il caso più semplice: i prende tutti i valori da 0 a 255, in modo che possiamo usare la notazione built-in di Haskell per campi:

[0..255] 

Ad alto livello, questo è equivalente di Haskell di for (i = 0 to 255); possiamo quindi eseguire la logica effettiva nel ciclo attraversando questa lista tramite una funzione ricorsiva o una funzione di ordine superiore dalla libreria standard. (La seconda opzione è altamente preferita.)

Questa particolare logica è adatta per uno fold. Una piega ci consente di prendere in esame una lista per elemento e creare un risultato di qualche tipo. Ad ogni passo, otteniamo una voce di elenco e il valore del nostro risultato accumulato finora. In questo caso particolare, vogliamo elaborare l'elenco da sinistra a destra mentre incrementiamo un indice, quindi possiamo usare foldl; l'unica parte difficile è che produrrà la lista all'indietro.

Ecco il tipo di foldl:

foldl :: (b -> a -> b) -> b -> [a] -> b 

Quindi la nostra funzione assume nel nostro valore intermedio ed un elemento di lista e produce un valore intermedio aggiornato. Dato che stiamo costruendo un elenco e teniamo traccia di un indice, il nostro valore intermedio sarà una coppia che contiene entrambi. Poi, una volta che abbiamo il risultato finale, si può ignorare il valore idx e invertire la lista finale otteniamo:

a = let (result, _) = foldl step ([], 1) [0..255] in reverse result 
    where step (a, idx) i 
      | someCondition i = (idx:a, idx + 1) 
      | otherwise  = (0:a, idx) 

Infatti, lo schema di trasformare un elenco tenendo traccia di uno stato intermedio (idx in questo caso) è abbastanza comune in modo che abbia una sua funzione in termini di tipo State. L'astrazione principale è un po 'più coinvolta (leggi attraverso ["Potresti aver inventato le Monade"] [tu] per un'ottima introduzione), ma il codice risultante è in realtà piuttosto piacevole da leggere (ad eccezione delle importazioni, immagino: P) :

import Control.Applicative 
import Control.Monad 
import Control.Monad.State 

a = evalState (mapM step [0..255]) 1 
    where step i 
      | someCondition i = get <* modify (+ 1) 
      | otherwise  = return 0 

l'idea è che si mappa su [0..255] tenendo traccia di qualche stato (il valore di idx) nei precedenti. evalState è come mettiamo insieme tutti gli impianti idraulici e otteniamo il nostro risultato finale. La funzione step viene applicata a ciascun elemento dell'elenco di input e può anche accedere o modificare lo stato.

Il primo caso della funzione step è interessante. L'operatore <* gli dice di fare prima la cosa a sinistra, la cosa sulla seconda destra ma restituisce il valore a sinistra. Ciò ci consente di ottenere lo stato corrente, di incrementarlo ma di restituire il valore che abbiamo prima dello che è stato incrementato. Il fatto che la nostra nozione di stato sia un'entità di prima classe e che possiamo avere funzioni di libreria come <* è molto potente: ho trovato questo particolare idioma davvero utile per attraversare gli alberi, e altri idiomi simili sono stati abbastanza utili per altri codici.

Answer 2

I loop possono solitamente essere espressi utilizzando diverse funzioni fold. Ecco una soluzione che utilizza foldl (è possibile passare alla foldl' se si esegue in un errore di StackOverflow):

f :: (Num a) => (b -> Bool) -> a -> [b] -> [a] 
f pred startVal = reverse . fst . foldl step ([], startVal) 
    where    
     step (xs, curVal) x 
      | pred x = (curVal:xs, curVal + 1) 
      | otherwise = (0:xs, curVal) 

Come si usa? Questa funzione richiede un predicato (someCondition nel codice), il valore iniziale di un indice e un elenco di elementi da iterare. Cioè, puoi chiamare f someCondition 1 [0..255] per ottenere il risultato dell'esempio dalla tua domanda.

Answer 3

Ci sono diversi modi per affrontare questo problema a seconda della struttura dati che si desidera utilizzare. Quello più semplice sarebbe probabilmente con le liste e le funzioni di base disponibili in Prelude:

a = go 1 [] [0..255] 
    where 
     go idx out [] = out 
     go idx out (i:is) = 
      if condition i 
       then go (idx + 1) (out ++ [idx]) is 
       else go idx (out ++ [0]) is 

Questo utilizza il modello di lavoratore con due accumulatori, idx e out, e attraversa giù l'ultimo parametro fino a quando non più elementi sono lasciati, quindi restituisce out. Questo potrebbe certamente essere convertito in un tipo fold, ma in ogni caso non sarà molto efficiente, l'aggiunta di voci a un elenco con ++ è molto inefficiente. Potresti renderlo migliore usando idx : out e 0 : out, quindi utilizzando reverse sull'output di go, ma non è ancora una soluzione ideale.

Un'altra soluzione potrebbe essere quella di utilizzare il State monade:

a = flip runState 1 $ forM [0..255] $ \i -> do 
     idx <- get 
     if condition i 
      then do 
       put $ idx + 1 -- idx++ 
       return idx  -- A[i] = idx 
      else return 0 

che certamente sembra molto più imperativo. Lo 1 in flip runState 1 indica che lo stato iniziale è idx = 1, quindi si utilizza forM (che sembra un ciclo for, ma in realtà non lo è) su [0..255], la variabile di ciclo è i e quindi si tratta solo di implementare il resto di la logica.

Se si desidera andare molto più avanzato, è possibile utilizzare le monadi StateT e ST per disporre di un array mutabile con uno stato allo stesso tempo. La spiegazione di come funziona è ben oltre la portata di questa risposta, però:

import Control.Monad.State 
import Control.Monad.ST 
import qualified Data.Vector as V 
import qualified Data.Vector.Mutable as MV 


a :: V.Vector Int 
a = runST $ (V.freeze =<<) $ flip evalStateT (1 :: Int) $ do 
    a' <- lift $ MV.new 256 
    lift $ MV.set a' 0 
    forM_ [0..255] $ \i -> do 
     when (condition i) $ do 
      idx <- get 
      lift $ MV.write a' i idx 
      put $ idx + 1 
    return a' 

ho semplificato un po 'in modo che ogni elemento è impostato su 0 fin dall'inizio, si comincia con uno stato iniziale di idx = 1, loop over [0..255], se l'indice corrente i soddisfa la condizione quindi ottenere l'attuale idx, scriverlo all'indice corrente, quindi incrementare idx. Esegui come operazione stateful, quindi congela il vettore e infine esegui il lato monade ST.Ciò consente di un vettore mutabile reale nascosto in modo sicuro all'interno della monade ST in modo che il mondo esterno non sappia che per calcolare a devi fare alcune cose piuttosto strane.

Answer 4

ricorsione esplicita:

a = go 0 1 
    where go 256 _ = [] 
     go i idx | someCondition i = idx : go (i+1) (idx+1) 
        | otherwise  = 0 : go (i+1) idx 

Apertura: (variante della ricorsione esplicita sopra)

a = unfoldr f (0,1) 
    where f (256,_) = Nothing 
      f (i,idx) | someCondition i = Just (idx,(i+1,idx+1)) 
        | otherwise  = Just (0 ,(i+1,idx ))