[elm-discuss] How to walk my own implementation of an array

Discussion:

Francisco Ramos

2017-12-01 15:22:16 UTC

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

--
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

2017-12-04 06:40:32 UTC

Permalink

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.

Post by 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
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
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
[ 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
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

Francisco Ramos

2017-12-04 07:31:29 UTC

Permalink

Hi Matthieu,

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

Thanks for the correction.

Fran

Post by 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.

--
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
For more options, visit https://groups.google.com/d/optout.

Matthieu Pizenberg

2017-12-04 07:49:23 UTC

Permalink

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.

Matthieu Pizenberg

2017-12-04 07:53:23 UTC

Permalink

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

Post by 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.

Matthieu Pizenberg

2017-12-04 08:17:56 UTC

Permalink

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

2017-12-04 08:19:17 UTC

Permalink

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

Post by 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.

Post by 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.

Post by 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
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
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
[ 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
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

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
For more options, visit https://groups.google.com/d/optout.

Francisco Ramos

2017-12-04 08:22:45 UTC

Permalink

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

Thanks

Post by 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
On Mon, Dec 4, 2017, 08:53 Matthieu Pizenberg <

Post by 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.

Post by 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.

Post by 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
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
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
[ 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
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

2017-12-04 09:02:00 UTC

Permalink

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

2017-12-04 15:13:31 UTC

Permalink

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

On Mon, Dec 4, 2017 at 10:02 AM 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
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
--
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
For more options, visit https://groups.google.com/d/optout.