How to walk my own implementation of an array

[Francisco Ramos]

Hi guys,

been trying to figure out for a while now how I can solve this problem. I've implemented my own type of array, it's called NdArray. The way it works is as follow:

It has a buffer (an array of something), a shape (list of dimensions), strides (list of steps) and an offset. Imagine we have a NdArray with a buffer of 9 numbers [1, 2, 3, 4, 5, 6, 7, 8, 9], shape [3, 3] (square matrix) and this leads to a list of strides [3, 1]. This last one means, there is a jump of 3 numbers for each of the first dimension. Better visualised:

buffer => [1, 2, 3, 4, 5, 6, 7, 8, 9]

view of this buffer with shape [3, 3] => 

[ 1, 2, 3

, 4, 5, 6

, 7, 8, 9

]

Now, imagine I change the strides to be [2, 2], that means, I'm jumping one per dimension (in this square matrix I'm jumping one column and one row). The result is:

[ 1, 3

, 7, 9

]

I'm jumping one number in the last dimension, and an entire row in the first dimension. Shape is now [2, 2].

So I have all this implemented already here https://github.com/jscriptcoder/elm-ndarray. This is port of ndarray by Mikola Lysenko, https://github.com/scijs/ndarray. But I got stuck how to walk this array. I'm trying to implement map, filter and fold (foldl), and to do so I must be able to walk this array, which is not that trivial (or at least not for me). I have implemented a function "index" which takes a location in the form of list of Int and calculates the index based on shape, strides and offset. So I'm trying to find a way to implement this functionality:

For example, for a [3, 3] shape then

nextLocation [0, 0] => Just [0, 1]
nextLocation [0, 1] => Just [0, 2]

nextLocation [0, 2] => Just [1, 0]

nextLocation [1, 0] => Just [1, 1]

nextLocation [1, 1] => Just [1, 2]

...

 nextLocation [2, 2] => Nothing

By far not an expert in functional programming, maybe someone can help me to figur this one out?

Thanks a lot.

Fran

[Matthieu Pizenberg]

Hi Francisco,
I think there is a confusion here. If you keep the same buffer, your matrice [1 3; 7 9] will be represented by { strides = (6, 2), shape = (2,2) } not strides = (2,2). Because 6 is the jump from one line to the other (1 to 7).
Let me know if I'm mistaking or not clear.

[Francisco Ramos]

Hi Matthieu,

Yes, I made that mistake. As you mentioned, the strides are [6, 2].

Thanks for the correction.

Fran

--
You received this message because you are subscribed to the Google Groups "Elm Discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to elm-discuss...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Matthieu Pizenberg]

Regarding your question, walking the array is not complicated I think. You can just walk the underlying buffer, and use a function like below if I'm not mistaking.

location : Int -> Int -> Strides -> Shape -> Maybe Location
location bufferIndex bufferOffset (stride1, stride2) (height, width) =
    let
        unOffset =
            bufferIndex - bufferOffset
       
        line =
            unOffset // stride1
           
        column =
            unOffset % stride1
    in
    if line < height && column < width then
        Just (line, column)
    else
        Nothing

Generalization would proceed the same, using euclidean division and modulo, dimension after dimension.

On Friday, December 1, 2017 at 11:22:16 PM UTC+8, Francisco Ramos wrote:

[Matthieu Pizenberg]

Oops, not as trivial as I thought ahah. Forget previous answer. It may require just some little adjustment though, I will think about it.

[Matthieu Pizenberg]

I wasn't very far ^^ here is the function:

location : Int -> Int -> ( Int, Int ) -> ( Int, Int ) -> Maybe ( Int, Int )
location bufferIndex offset ( str1, str2 ) ( height, width ) =
    let
        unOffset =
            bufferIndex - offset

        ( line, lineRest ) =
            ( unOffset // str1
            , unOffset % str1
            )

        ( column, columnRest ) =
            ( lineRest // str2
            , lineRest % str2
            )

        locationOk =
            line < height && column < width && columnRest == 0
    in
    if locationOk then
        Just ( line, column )
    else
        Nothing

You can easily verify your example by putting it in a file, and in elm-repl:

import TheFile
import List

List.range 0 8 |> List.map (\id -> TheFile.location id 0 (6,2) (2,2))

[Francisco Ramos]

I had similar idea, walking the entire buffer and somehow check boundaries (dimension size) but I was wondering if there is a better way since we could have a huge buffer (this might be shared across multiple ndarrays), let's say a couple of hundred thousands items, but a ndarray with a small view of this buffer, let's say a thousand items. I wouldn't want to go through hundreds of thousands for just one thousand. That's why I'm trying to come up with a function that have the behavior I described initially, "nextlocation". Along with "index" function I can work out in O(1) the index for the next one

Thanks,
Fran

--

[Francisco Ramos]

I didn't your last message when I answered. Let me have a look at your solution.

Thanks

[Matthieu Pizenberg]

I wouldn't want to go through hundreds of thousands for just one thousand. That's why I'm trying to come up with a function that have the behavior I described initially, "nextlocation". Along with "index" function I can work out in O(1) the index for the next one

Yep sorry, I didn't realize that initially. Then you could do something like:

nextLocation : Location -> Shape -> Maybe Location
nextLocation location shape =
    let
        increment (loc, size) (locationAcc, shouldInc) =
            if shouldInc then
                if loc + 1 < size then
                    ( loc + 1 :: locationAcc, False )
                else
                    ( 0 :: locationAcc, True )
            else
                ( loc :: locationAcc, False )
       
        newLocation =
            List.map2 (,) location shape
                |> List.foldr increment ([],True)
    in
    if Tuple.second newLocation then
        Nothing
    else
        Tuple.first newLocation

[Francisco Ramos]

Hi Matthieu, your function is genius, https://ellie-app.com/4qBxgmzvBa1/0

Thanks a lot. I couldn't come up with a good way to implement this. Not only that, but also I've just learnt something I didn't even know was possible in Elm, the definition of a helper function in the "let" block. Never saw that before. I'm fairly new in Elm. Thanks for that also :-)

Fran