2012-11-26 20 views
7

In GNU Octave questo codice -Haskell repa - come ridurre l'array e l'indice di ritorno?

[e, ix] = min(X); 

tornerà elemento minimo e la sua posizione. Come si fa in questo repa per la funzione binaria arbitraria?

Questo è quello che si avvicinò con:

min x = z $ foldl' f (e,0,0) es 
    where 
    (e:es) = toList x 
    f (a,ix,r) b = let ix' = ix+1 in if a < b then (a,ix',r) else (b,ix',ix') 
    z (a,ix,r) = (a,r) 

Nell'esempio sopra convertire repa matrice 1D elencare e utilizzare foldl'(da Data.List) con due accumulatori - uno per il conteggio iterazioni (ix) e altro per salvare la posizione dell'elemento min (r). Ma l'intero punto di utilizzo di repa è usare matrici, non liste!

In repa ci sono due pieghe per tipo Array (foldS e foldP) - ma possono solo prendere la funzione di tipo (a -> a -> a) - cioè, non posso passare tupla con accumulatori ad esso. C'è anche traversata, che può, in linea di principio, a ridurre serie 1D a un array scalare:

min x = traverse x to0D min 
    where 
    to0D (Z:.i) = Z 
    min f (Z) = ??? -- how to get elements for comparison? 

La prima cosa che viene in mente è

[f (Z:.i) | i <- [1..n]], where n = (\(Z:.i) -> i) $ extent x 

ma questo sarà anche convertire allineamento alla lista, invece di fare calcoli sull'array.

+2

Non hai familiarità con repa, ma non puoi semplicemente mappare ogni elemento in una tupla prima di usare 'foldP?'. Ad esempio, è possibile descrivere un sottoarray usando una tupla dell'elemento minimo, l'indice del minimo e la lunghezza del sottoarray. Quindi mappate ogni elemento 'x' a' (x, 0, 1) 'e quindi piegate parallelamente usando' f (x, i, n) (y, j, m) = se x hammar

+0

Siamo spiacenti, questo dovrebbe essere "maxBound". – hammar

+0

Per usare foldP con una tupla dovrai avere array con quelle tuple. Può essere fatto, ma questo è uno spreco per l'elaborazione delle immagini (milioni di elementi). – EvgenijM86

risposta

3

Non sono esperto di Repa, ma sembra funzionare per gli array 1-D. Probabilmente può essere adattato per altre dimensioni.

import Data.Array.Repa 

indexed arr = traverse arr id (\src [email protected](Z :. i) -> (src idx, i)) 

minimize arr = foldP f h t 
    where 
    (Z :. n) = extent arr 
    arr' = indexed arr 
    h = arr' ! (Z :. 0) 
    t = extract (Z :. 1) (Z :. (n-1)) arr' 
    f [email protected](valMin, iMin) [email protected](val, i) | val < valMin = x 
            | otherwise = min 
+0

Sto affrontando lo stesso problema e non ho trovato altra soluzione. – olek

0

A rischio di far rivivere un post zombie, ecco una soluzione dimensione arbitraria ho lavorato fuori (che, rivedere i commenti, è esattamente ciò che @hammar suggerito). A causa della strana natura di foldAllP, che utilizzo come elemento di identità quando si uniscono tuple, è necessario fornire anche un limite superiore per il minimo dell'array che si sta cercando di trovare.

import Data.Array.Repa 
import Data.Array.Repa.Eval 
import Data.Array.Repa.Repr.Unboxed 

minimize :: (Shape sh, Source r a, Elt a, Unbox a, Monad m, Ord a) => Array r sh a -> a -> m (a,sh) 
minimize arr upperBound = do 
     -- Zip the array with its (Int representation of) indices 
     let zippedWithIndex = Data.Array.Repa.traverse arr id (\f idx -> (f idx, toIndex (extent arr) idx)) 

     -- Define a function that compares two tuple of (a,Int) on the value of the first entry 
     let minimumIndex [email protected](v,_) t'@(v',_) = if v < v' then t else t' 

     -- Do a parallel fold of all elements in the array 
     (min,idx) <- foldAllP minimumIndex (upperBound, error "Empty array") zippedWithIndex 

     -- convert the indice back from its Int representation 
     return (min, fromIndex (extent arr) idx) 

Naturalmente, se la matrice contiene un tipo che ha un'istanza di Bounded, è possibile effettuare la funzione più conveniente

minimize' arr = minimize arr maxBound 

Alcuni test che si possono fare al prompt:

λ> let x = fromListUnboxed (ix2 2 2) [20, 30, 10, 40] :: Array U DIM2 Int 
λ> minimize' x 
(10,(Z :. 1) :. 0)