Replicating Numpy's Advanced Indexing/Slicing in Haskell

Question

Numpy has a sophisticated indexing/slicing/stepping functionality in its array access operator. See this: http://docs.scipy.org/doc/numpy/reference/arrays.indexing.html

While experimenting with Haskell, I thought it would educational to try replicating a subset of this indexing functionality. Specifically it's "tuple selection objects" or n-dimensional projection" (https://en.wikipedia.org/wiki/Projection_%28relational_algebra%29).

Basically you can do:

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

And this will give you the first row stepped by 1 containing the first 2 columns stepped by 2 (skipping 1 column).

In order words it can project an original 2 dimensional array into a smaller 2 dimensional array. The result remains as a 2 dimensional array.

So here's what I tried in Haskell.

The type of such a function should be something like:

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

So you could see something like:

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

Where sx, ex, stx are start, end, step respectively.

The example should project the original tensor into a smaller tensor, with the first dimension restricted by s1 to e1, stepping by st1, second dimension restricted by s2 to e2, stepping by st2... etc.

So here's what I got:

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

The above does not work due to a problem of "polymorphic recursion". Basically I cannot infinitely compose the map function, the specific expression that does this is the (projection . map). If this kind of polymorphic recursion were possible, I believe it would work. But I am open to alternative implementations which doesn't involve polymorphic recursion.

I have researched this problem and have still come up short:

• 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

There's already a type for computing new values from existing values - functions. Assuming we have a function that indexes into a structure, we can use it to index the structure by applying it to the structure.

(!!!) = flip ($)

infixr 2 !!!

If we have a function that indexes the structure and another function that indexes any nested structures we can compose them together by fmaping the second function over the structure then applying the outer function.

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

infixr 5 !.

With an example 3d structure

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

We can look up an elaborate slice of it built with your slicing functions slicing and stepping.

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

Which results 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)]]]