Replizieren von Numpys Advanced Indexing/Slicing in Haskell

Question

Numpy verfügt in seinem Array-Zugriffsoperator über eine ausgefeilte Indizierung/Slicing/Stepping-Funktionalität. Siehe auch: http://docs.scipy.org/doc/numpy/reference/arrays.indexing.html

Während ich mit Haskell experimentierte, dachte ich, es wäre lehrreich, eine Teilmenge dieser Indizierungsfunktionalität zu replizieren. Insbesondere ist es „Tupel Auswahlobjekte“ oder n-dimensionale Projektion“(https://en.wikipedia.org/wiki/Projection_%28relational_algebra%29)

Grundsätzlich können Sie tun:.

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

Und dies wird Ihnen die erste Zeile trat um 1 die ersten 2 Spalten mit abgestuften von 2 (Überspringen 1 Spalte).

mit anderen Worten kann es einen originellen 2-dimensionalen Array in einen kleineren 2-dimensionalen Array projiziert. Das Ergebnis bleibt als 2-dimensionales Array.

Also hier ist, was habe ich versucht, in Haskell

Die Art einer solchen Funktion sollte so etwas wie:

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

So sehen Sie könnte so etwas wie:

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

Wo sx, ex, STX Start sind, Ende, Schritt sind.

Das Beispiel sollte die ursprüngliche Tensor in einen kleineren Tensor, mit der ersten Dimension von s1 to e1, stepping by st1, zweiter Dimension von s2 to e2, stepping by st2 beschränkt beschränkt Projekt ... usw.

Also hier ist, was ich habe:

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 

Das obige funktioniert aufgrund eines Problems der "polymorphen Rekursion" nicht. Grundsätzlich kann ich nicht unendlich die map Funktion verfassen, der spezifische Ausdruck, der das tut, ist das (projection . map). Wenn diese Art von polymorpher Rekursion möglich wäre, glaube ich, dass es funktionieren würde. Aber ich bin offen für alternative Implementierungen, die keine polymorphe Rekursion beinhalten.

Ich habe dieses Problem untersucht und haben immer noch zu kurz kommt:

• 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

Es gibt bereits eine Art für aus bestehenden Werten neue Werte Computing - Funktionen . Angenommen, wir haben eine Funktion, die in eine Struktur indiziert, können wir sie verwenden, um die Struktur zu indexieren, indem wir sie auf die Struktur anwenden.

(!!!) = flip ($) 

infixr 2 !!! 

Wenn wir eine Funktion, die Indizes der Struktur und eine andere Funktion haben, die Indizes alle verschachtelten Strukturen wir sie zusammen durch fmap ing die zweite Funktion über die Struktur zusammensetzen kann dann die äußere Funktion anwenden.

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

infixr 5 !. 

mit einem Beispiel 3D-Struktur

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

Wir können eine aufwendige Scheibe sehen es mit Ihren Slicing-Funktionen gebaut slicing und stepping.

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

was dazu führt,

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