Replicare l'indicizzazione/segmentazione avanzata di Numpy in Haskell

Question

Numpy ha una sofisticata funzionalità di indicizzazione/slicing/stepping nel proprio operatore di accesso agli array. Vedi questo: http://docs.scipy.org/doc/numpy/reference/arrays.indexing.html

Durante gli esperimenti con Haskell, ho pensato che sarebbe stato educativo provare a replicare un sottoinsieme di questa funzionalità di indicizzazione. Specificamente è "Oggetti scelta tupla" o n-dimensionale proiezione"(https://en.wikipedia.org/wiki/Projection_%28relational_algebra%29)

Fondamentalmente si può fare.

two_d_array[0:1:1, 0:4:2] 

E questo vi darà la prima fila gradini da 1 contenente le prime 2 colonne intensificati da 2 (saltando 1 colonna).

in altri termini si può proiettare un originale 2 matrice bidimensionale in un più piccolo 2 matrice bidimensionale. Il risultato rimane come una matrice bidimensionale 2.

Così qui è quello che ho provato in Haskell

Il tipo di tale funzione dovrebbe essere qualcosa di simile:

(!!!) :: (Functor f) => f a -> [(Int, Int, Int)] -> f a 

così si poteva vedere qualcosa di simile:

three_d_tensor !!! [(s1,e1,st1), (s2,e2,st2), (s3,e3,st3)] 

Dove sx, ex, STX sono inizio, fine, passo, rispettivamente.

L'esempio dovrebbe proiettare il tensore originale in un tensore più piccola, con la prima dimensione limitata da s1 to e1, stepping by st1, seconda dimensione limitata da s2 to e2, stepping by st2 ... ecc

Quindi, ecco quello che ho ottenuto:

slicing from to xs = take (to - from + 1) (drop from xs) 

stepping n = map head . takeWhile (not . null) . iterate (drop n) 

(!!!) tensor ((start, end, step):tail) = 
    project (stepSlice start end step tensor) tail map 
    where 
     project tensor ((start, end, step):tail) projection = 
      project (projection (stepSlice start end step) tensor) tail (projection . map) 
     project tensor [] _ = 
      tensor 
     stepSlice start end step tensor = 
      ((stepping step) . (slicing start end)) tensor 

Quanto sopra non funziona a causa di un problema di "ricorsione polimorfica". Fondamentalmente non riesco a comporre infinitamente la funzione map, l'espressione specifica che fa questo è (projection . map). Se fosse possibile questo tipo di ricorsione polimorfica, credo che funzionerebbe. Ma sono aperto a implementazioni alternative che non implicano la ricorsione polimorfica.

Ho studiato questo problema e sono ancora venuto a breve:

• https://byorgey.wordpress.com/2007/08/16/mapping-over-a-nested-functor/
• http://okmij.org/ftp/Haskell/typecast.html#deepest-functor
• Haskell Polymorphic Recursion with Composed Maps causes Infinite Type Error

Answer 1

C'è già un tipo per calcolare i nuovi valori da valori esistenti - funzioni . Supponendo che abbiamo una funzione che indicizza in una struttura, possiamo usarla per indicizzare la struttura applicandola alla struttura.

(!!!) = flip ($) 

infixr 2 !!! 

Se abbiamo una funzione che indicizza la struttura e un'altra funzione che gli indici eventuali strutture annidate possiamo comporre insieme dal fmap ing la seconda funzione sulla struttura poi applicando la funzione esterna.

(!.) :: Functor f => (f b -> g c) -> (a -> b) -> f a -> g c 
t !. f = t . fmap f 

infixr 5 !. 

con un esempio 3d struttura

three_d_tensor :: [[[(Int,Int,Int)]]] 
three_d_tensor = [[[(x, y, z) | z <- [0..4]] | y <- [0..3]] | x <- [0..2]] 

Possiamo cercare un fetta elaborato di essa costruita con le funzioni di affettare slicing e stepping.

example = three_d_tensor !!! slicing 1 2 !. stepping 2 !. stepping 2 . slicing 1 3 

che si traduce in

[[[(1,0,1),(1,0,3)],[(1,2,1),(1,2,3)]],[[(2,0,1),(2,0,3)],[(2,2,1),(2,2,3)]]]