[elm-discuss] Array map with start and end

[Francisco Ramos]

Hi there,

Was wondering how I can map over an array with a start and end indexes. I
know I could slice the array and then map, but performance is a concern and
slicing is O(N) where N = end - start, plus the actual mapping, another
O(N).

Maybe there is another way where I just loop once over the array?

Thanks a lot,
Fran

['Rupert Smith' via Elm Discuss]

Post by Francisco Ramos
Hi there,
Was wondering how I can map over an array with a start and end indexes. I
know I could slice the array and then map, but performance is a concern and
slicing is O(N) where N = end - start, plus the actual mapping, another
O(N).
Maybe there is another way where I just loop once over the array?

You could write your own using Array.get. But I can see that will be a
PITA, as it returns a Maybe, so you might also end up having to supply a
default value for the case where get gives you a Nothing, but in practice
that default will never be used. Or have your custom map function also
return a Maybe, and output Nothing if the indexes are out of bounds and
Array.get returns Nothing?

[Robin Heggelund Hansen]

Slicing isn't O(N).

In the current implementation in core, slicing is O(log32n) i believe. In
the next version of Elm, slicing is O(log32n) when start = 0; I'm uncertain
what the big-o notation is once start > 0 though.

Post by Francisco Ramos
Hi there,
Was wondering how I can map over an array with a start and end indexes. I
know I could slice the array and then map, but performance is a concern and
slicing is O(N) where N = end - start, plus the actual mapping, another
O(N).
Maybe there is another way where I just loop once over the array?
Thanks a lot,
Fran

[Francisco Ramos]

That was a good observation, Rupert. Well, it doesn't return Nothing if the
indexes are out of the bounds, but if start < 0 then start = 0, and end >=
length then end = length -1... I could actually use Array.get and implement
my own map like you mention.

Thanks Robin for that correction. I thought Array.slice is using under the
hood Array.prototype.slice, which as far as I know, the C++ implementation,
it's O(N). If there is a new implementation with such complexity, then
happy days.

Was just curious to know what ideas there are out there about this problem.
I'm aware of the fact that 2 * O(N) is still O(N), but my arrays might be
dealing with millions of entries. Imagine a 5000px by 5000px by 3 color
channels. That's 75 millions. So performance is very important. That's why
I'm asking.

Thanks guys

Post by Robin Heggelund Hansen
Slicing isn't O(N).
In the current implementation in core, slicing is O(log32n) i believe. In
the next version of Elm, slicing is O(log32n) when start = 0; I'm uncertain
what the big-o notation is once start > 0 though.

Post by Francisco Ramos
Hi there,
Was wondering how I can map over an array with a start and end indexes. I
know I could slice the array and then map, but performance is a concern and
slicing is O(N) where N = end - start, plus the actual mapping, another
O(N).
Maybe there is another way where I just loop once over the array?
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.

[Robin Heggelund Hansen]

It using Array.prototype.slice under the hood, but the way Arrays in Elm is
implemented is by using trees. I suggest you watch my talk from Elm Europe,
where I explain how the different data structures work in detail =)

Post by Francisco Ramos
That was a good observation, Rupert. Well, it doesn't return Nothing if
the indexes are out of the bounds, but if start < 0 then start = 0, and end

= length then end = length -1... I could actually use Array.get and

implement my own map like you mention.
Thanks Robin for that correction. I thought Array.slice is using under the
hood Array.prototype.slice, which as far as I know, the C++ implementation,
it's O(N). If there is a new implementation with such complexity, then
happy days.
Was just curious to know what ideas there are out there about this
problem. I'm aware of the fact that 2 * O(N) is still O(N), but my arrays
might be dealing with millions of entries. Imagine a 5000px by 5000px by 3
color channels. That's 75 millions. So performance is very important.
That's why I'm asking.
Thanks guys

Slicing isn't O(N).
In the current implementation in core, slicing is O(log32n) i believe. In
the next version of Elm, slicing is O(log32n) when start = 0; I'm uncertain
what the big-o notation is once start > 0 though.

Post by Francisco Ramos
Hi there,
Was wondering how I can map over an array with a start and end indexes.
I know I could slice the array and then map, but performance is a concern
and slicing is O(N) where N = end - start, plus the actual mapping, another
O(N).
Maybe there is another way where I just loop once over the array?
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.

[Rémi Lefèvre]

Hi,

Does using Array.indexedMap suit you?

import Array exposing (Array)

submap : Int -> Int -> (a -> a) -> Array a -> Array a
submap start end func =
Array.indexedMap (\i -> if i >= start && i < end then func else
identity)

Of course the result must be of the same type in this case.

Post by Francisco Ramos
Hi there,
Was wondering how I can map over an array with a start and end indexes. I
know I could slice the array and then map, but performance is a concern and
slicing is O(N) where N = end - start, plus the actual mapping, another
O(N).
Maybe there is another way where I just loop once over the array?
Thanks a lot,
Fran

[Matthieu Pizenberg]

Hi Francisco, just a few words about arrays and image manipulation.

I've been doing some work along this way and encountered multiple issues.
One of them was with slicing. If I'm not wrong Robin's work will be merged
in 0.19 but meanwhile, you should be aware that there are few issues with
the current arrays, especially large ones [1]. You can already use his
library as a drop-in replacement though.

I was also about to mention the numelm project but I think you know about
it ^^. Regarding those kind of operations (slicing, transposing, ...) I
think a generic image (/tensor) type would benefit a lot from having lazy
"views" [2] and expressions of matrices as explained in the xtensor [3]
project I mentionned in your numelm post.

Cheers and good luck for this amazing project!

[1] elm 0.18 array issues : https://github.com/elm-lang/core/issues/649
[2] lazy views at 12:30 :

[3] https://github.com/QuantStack/xtensor

[Francisco Ramos]

Hi Matthieu,

Thanks for those links!!. Those lazy views look like what I'm trying to
achieve. I'm actually working on a multidimensional container of items,
elm-ndarray,
https://github.com/jscriptcoder/elm-ndarray/blob/master/src/NdArray.elm. Still
some work to do. I need to re-write *map* and *fold* since they're not
correct and implement *step*. This is based on the work of Mikola Lysenko,
https://github.com/scijs/ndarray, which in turn is based on Python ndarray,
https://docs.scipy.org/doc/numpy-1.13.0/reference/arrays.ndarray.html,
where operations such as slicing, indexing, transposing, reshaping, etc..
are all O(1). I'm missing though the possibility of using TypedArrays.

Fran

On Mon, Nov 20, 2017 at 8:01 AM Matthieu Pizenberg <

Post by Matthieu Pizenberg
Hi Francisco, just a few words about arrays and image manipulation.
I've been doing some work along this way and encountered multiple issues.
One of them was with slicing. If I'm not wrong Robin's work will be merged
in 0.19 but meanwhile, you should be aware that there are few issues with
the current arrays, especially large ones [1]. You can already use his
library as a drop-in replacement though.
I was also about to mention the numelm project but I think you know about
it ^^. Regarding those kind of operations (slicing, transposing, ...) I
think a generic image (/tensor) type would benefit a lot from having lazy
"views" [2] and expressions of matrices as explained in the xtensor [3]
project I mentionned in your numelm post.
Cheers and good luck for this amazing project!
[1] elm 0.18 array issues : https://github.com/elm-lang/core/issues/649
[2] lazy views at 12:30 : http://youtu.be/mwIQUgigjbE
[3] https://github.com/QuantStack/xtensor
--
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]

Hi again,

So out of curiosity, I just spend a couple hours looking for variations of:
"(immutable/persistent) (tensor/multidimentional array/multidimentional
data structure) implementation"
and my conclusion is that I did not easily find examples of implementations
of data structures tailored for such specific needs as tensor manipulation.
It must not be the right way to search for this.

What I found however was many references to Okasaki's work on immutable
data structures. This question [1] with it's answer provide good starting
points in my opinion. Okasaki's book seems to focus on how to
design/implement fuctional data structures so it could give good insights
for the raw data structure at the base of your ndarray type.

Maybe the first thing to do would be to clearly define all the operations
you want to have for your ndarray in some document. Then design a data
structure considering trade-off for all the operations supported.
Apparently, there is a paper for the numpy arrays listed on scipy website
[2]. These are not immutable however so I don't know if it is usefull.

In hope that it may help,
Cheers,
Matthieu

[1] interesting question: https://cs.stackexchange.com/a/25953/34063
[2] scipy citations: https://www.scipy.org/citing.html

[Francisco Ramos]

Hi guys,

Thanks for your answers. Robin, that was a great talk. I actually was in
that very same room when you gave the presentation :-). Very interesting
and educative. Hope to see you again in the next Elm Europe.

Matthieu, thanks for the info. I didn't know about Okasaki's work on
immutable data structures. Have to admit I didn't google much about the
subject. Got some references and I'll go through them. I already have a
good idea about the API I'd like to implement for the ndarray. Once I get
it done (time is not something I have plenty) I'll write some benchmarks.

Ultimately, I'd like to rewrite NumElm using the elm-ndarray. Not sure how
I'm gonna do this without writing kernel code. Linear algebra operations
such as Inverse, Pseudo-inverse, Singular value decomposition, Eigenvalues
and eigenvectors, etc... I simply have no idea how I'm gonna implement
this. Need to have a look at solutions in Haskell for inspiration.

Cheers,

Fran


On Mon, Nov 20, 2017 at 4:09 PM Matthieu Pizenberg <

Post by Matthieu Pizenberg
Hi again,
"(immutable/persistent) (tensor/multidimentional array/multidimentional
data structure) implementation"
and my conclusion is that I did not easily find examples of
implementations of data structures tailored for such specific needs as
tensor manipulation. It must not be the right way to search for this.
What I found however was many references to Okasaki's work on immutable
data structures. This question [1] with it's answer provide good starting
points in my opinion. Okasaki's book seems to focus on how to
design/implement fuctional data structures so it could give good insights
for the raw data structure at the base of your ndarray type.
Maybe the first thing to do would be to clearly define all the operations
you want to have for your ndarray in some document. Then design a data
structure considering trade-off for all the operations supported.
Apparently, there is a paper for the numpy arrays listed on scipy website
[2]. These are not immutable however so I don't know if it is usefull.
In hope that it may help,
Cheers,
Matthieu
[1] interesting question: https://cs.stackexchange.com/a/25953/34063
[2] scipy citations: https://www.scipy.org/citing.html
--
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.

['Rupert Smith' via Elm Discuss]

Post by Francisco Ramos
Ultimately, I'd like to rewrite NumElm using the elm-ndarray. Not sure how
I'm gonna do this without writing kernel code. Linear algebra operations
such as Inverse, Pseudo-inverse, Singular value decomposition, Eigenvalues
and eigenvectors, etc... I simply have no idea how I'm gonna implement
this. Need to have a look at solutions in Haskell for inspiration.

I suspect you are up against a tough impedance mismatch between immutable
arrays for functional languages, and fast flat arrays for pure number
crunching.

The tree structured arrays for functional languages are designed to allow a
new version to be created from an existing array, without copying the
entire array. Well, a balance between copying the least amount whilst
keeping the tree fairly shallow for fast access.

Arrays of floats for number crunching ideally just want to be stored flat
in RAM, so you can point an optimized for-loop at them or your GPU.

You could also look at Java nio.Buffer for some inspiration? These allow
off-heap 'direct' buffers to be created, but have an interface on the Java
language side to manipulate them. You can for example take a 'slice' of
such a buffer, and it give you a so-called flyweight object as the result,
that is, a start offset and length into the original buffer, but sharing
the same data. 'slice' therefore is a very efficient operation.

This scheme won't translate into immutable functional data structures
without modification. For example, to modify such a buffer in an immutable
way, would mean copying the entire thing. I just mention it as a possible
source of inspiration to help you think about your design.

Perhaps this is already what you have in mind for ndarray? A structure that
is more efficient for your use case, but that is wrapped in an immutable
functional API to make it play nicely with the host language.

[Robin Heggelund Hansen]

Something
like https://github.com/Skinney/core/blob/master/src/Elm/JsArray.elm ? It's
what is used as the basis for Arrays in 0.19. It is not planned to be
opened for use outside of elm-lang/core, but if it fits your usecase
better, I'm sure Evan would be interested in hearing about it.

(JsArray is a thin wrapper over javascript arrays. Any operation that
modifies the underlying structure causes a complete copy, but get and folds
are very fast. Slicing when start === 0 is still going to be faster using
Elm Arrays as it is a tree structure. On the other hand, it should be
fairly easy to create a "view" instead of slicing, but that might give you
problems with space leaks.)

Post by 'Rupert Smith' via Elm Discuss

Post by Francisco Ramos
Ultimately, I'd like to rewrite NumElm using the elm-ndarray. Not sure
how I'm gonna do this without writing kernel code. Linear algebra
operations such as Inverse, Pseudo-inverse, Singular value
decomposition, Eigenvalues and eigenvectors, etc... I simply have no idea
how I'm gonna implement this. Need to have a look at solutions in
Haskell for inspiration.

I suspect you are up against a tough impedance mismatch between immutable
arrays for functional languages, and fast flat arrays for pure number
crunching.
The tree structured arrays for functional languages are designed to allow
a new version to be created from an existing array, without copying the
entire array. Well, a balance between copying the least amount whilst
keeping the tree fairly shallow for fast access.
Arrays of floats for number crunching ideally just want to be stored flat
in RAM, so you can point an optimized for-loop at them or your GPU.
You could also look at Java nio.Buffer for some inspiration? These allow
off-heap 'direct' buffers to be created, but have an interface on the Java
language side to manipulate them. You can for example take a 'slice' of
such a buffer, and it give you a so-called flyweight object as the result,
that is, a start offset and length into the original buffer, but sharing
the same data. 'slice' therefore is a very efficient operation.
This scheme won't translate into immutable functional data structures
without modification. For example, to modify such a buffer in an immutable
way, would mean copying the entire thing. I just mention it as a possible
source of inspiration to help you think about your design.
Perhaps this is already what you have in mind for ndarray? A structure
that is more efficient for your use case, but that is wrapped in an
immutable functional API to make it play nicely with the host language.

['Rupert Smith' via Elm Discuss]

On Tuesday, November 21, 2017 at 10:47:02 AM UTC, Robin Heggelund Hansen

Something like
https://github.com/Skinney/core/blob/master/src/Elm/JsArray.elm ? It's
what is used as the basis for Arrays in 0.19. It is not planned to be
opened for use outside of elm-lang/core, but if it fits your usecase
better, I'm sure Evan would be interested in hearing about it.
(JsArray is a thin wrapper over javascript arrays. Any operation that
modifies the underlying structure causes a complete copy, but get and folds
are very fast. Slicing when start === 0 is still going to be faster using
Elm Arrays as it is a tree structure. On the other hand, it should be
fairly easy to create a "view" instead of slicing, but that might give you
problems with space leaks.)

Yes.

Something I forgot to mention about Java nio.Buffers is that they are byte
array buffers. There is mechanism by which int and float (and short, char,
lond and double) are overlayed as views onto byte buffers.

The reason I mention this is that as yet Elm does not have any support for
binary buffers, and it might also be worth thinking about that issue at the
same time.

Could JsArray.elm by made to work with JavaScript typed
arrays? https://developer.mozilla.org/en-US/docs/Web/JavaScript/Typed_arrays

[Matthieu Pizenberg]

This post might be inappropriate. Click to display it.

['Rupert Smith' via Elm Discuss]

This post might be inappropriate. Click to display it.

[Matthieu Pizenberg]

Post by 'Rupert Smith' via Elm Discuss
Do you need to rebuild the compiler for this?

I'm not familiar with so called "native" elm 0.18 code. So I wanted to use
the example given by Robin with `Elm/JsArray.elm` and
`Elm/Kernel/JsArray.js` from elm master branch to try the same thing with
`JsArrayBuffer.[elm/js]`. Since this is code in the master branch only,
which is 0.19 syntax (`elm.json`, "kernel" js code, ...), I cannot compile
it with elm-make from 0.18 branch.

But it's ok, this need no rush, will try when I have a little more time.

[Robin Heggelund Hansen]

Using native code in Elm isn't particularly hard (though, you cannot
publish such code as an elm package).

My original, and still working, array implementation uses native code (it's
a "blessed" library). It's better to use that as a template for any
experimentation you might want to
do: https://github.com/Skinney/elm-array-exploration

Post by 'Rupert Smith' via Elm Discuss
Do you need to rebuild the compiler for this?
I'm not familiar with so called "native" elm 0.18 code. So I wanted to use
the example given by Robin with `Elm/JsArray.elm` and
`Elm/Kernel/JsArray.js` from elm master branch to try the same thing with
`JsArrayBuffer.[elm/js]`. Since this is code in the master branch only,
which is 0.19 syntax (`elm.json`, "kernel" js code, ...), I cannot compile
it with elm-make from 0.18 branch.
But it's ok, this need no rush, will try when I have a little more time.

[Francisco Ramos]

I can confirm that. You just need to use elm-github-package, which allows
you to install Elm packages from the official repository and github. That's
exactly what I'm going in NumElm to be able to write Kernel code,
https://github.com/jscriptcoder/numelm...

I'm really running into lots of walls on this subject. I'd be super happy
if we had TypedArray views in Kernel code.

Currently I'm trying to figure out how to walk a strided Array. Imagine we
have a buffer like this: [1, 2, 3, 4, 5, 6, 7, 8, 9], with shape [3, 3],
square matrix. Strides for this is [3, 1] --> [1, 2, 3 | 4, 5, 6 | 7, 8,
9]. If I change the stride to [2, 2], then I get [1, 3 | 7, 9] --> 2x2
matrix. I need to implement map and fold functions, and to be able to do
that I need to walk the Array: 1 -> 3 -> 7 -> 9... My functional
programming skills are being challenged here ;-)

Fran



On Thu, Nov 23, 2017 at 11:26 AM 'Rupert Smith' via Elm Discuss <

Post by 'Rupert Smith' via Elm Discuss

Could JsArray.elm by made to work with JavaScript typed arrays?

Post by 'Rupert Smith' via Elm Discuss
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Typed_arrays

That was exactly what I was wondering. I peaked at the elm and kernel
code and wanted to try to hack something to wrap ArrayBuffer. I got stopped
at the step of compiling the elm plateform at master ^^, my system ghc
beeing 8.2 and I don't have enough haskell-fu yet to manage multiple
haskell versions :)

Do you need to rebuild the compiler for this?
I may be wrong, but kernel hacking can be done by using
elm-github-install, by putting a substitution for elm-lang/core in your
"dependency-sources": {
"elm-lang/core": "../my-hacked-core"
}
Then you can try out kernel modifications without needing to rebuild the
whole Elm distribution?

As a side note, I just went to a NixOS [1] meetup yesterday evening,
really cool stuff. I think this nix package manager [2] will help me deal
with those dependencies issues!

I really want to try NixOS, but it will have to wait until I have a good
amount of time on my hands to play around with it.
--
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]

Following your advice, I came back to elm 0.18 and just started a
repository to try to wrap JS typed arrays in elm. I've moved the discussion
to a new post [1] since we were drifting from the original post here.
Cheers

[1] JS typed array implementation for elm:
https://groups.google.com/d/topic/elm-discuss/ZfdV85yq9jU/discussion