<p>I call them <em>nonstrict arrays</em>.</p>

<p>They're not only not completely useless, but very useful and interesting. Operating on them is also not the worst in time efficiency, but can be asymptotically equivalent if done correctly. Further, if an array is just a lambda with a shape attached to it, then like transformations, pointwise operations are also not much more than function composition.</p>

<p>For a good start, look here:</p>

<p><a href="http://research.microsoft.com/en-us/um/people/simonpj/papers/ndp/RArrays.pdf" rel="nofollow">Regular, shape-polymorphic, parallel arrays in Haskell, Gabriele Keller, Manuel Chakravarty, Roman Leshchinskiy, Simon Peyton Jones, and Ben Lippmeier. ICFP 2010.</a></p>

<p>The authors present a multidimensional version of the arrays you're asking about, which are like NumPy's multidimensional arrays but in Haskell style. Arrays are just a lambda and a shape, and they don't cache computed elements for faster retrieval in the future. But at any time, a user can force one to compute and cache all of its elements.</p>

<p>These arrays force users to think in terms of whole-array operations. I consider that a plus, as it encourages a more declarative style of coding than writing loops that micromanage elements. I liked this style better when I was using NumPy as well. Others have different opinions.</p>

<p>The upside is automatic fusion of array operations, which reduces the memory cost of whole-array operations. It also helps immensely with parallelizing sequences of operations. Allocating space for intermediate arrays is a synchronization point. But if intermediate arrays are nonstrict, their elements don't require space, so that synchronization point disappears. Further, this "loop fusion" happens <em>even when operations are in different functions</em>, which would be very difficult, if not impossible, for a static optimizer to do.</p>

<p>One downside is that it's harder to reason about the performance of operations on nonstrict arrays. Another is that users have to decide which arrays to force to be strict. There are some simple rules of thumb, but they can't reduce the mental overhead to zero.</p>

<p>If you want to play with implementations, check out Haskell's <a href="http://hackage.haskell.org/package/repa" rel="nofollow">Repa</a> and Racket's <a href="http://docs.racket-lang.org/math/array.html?q=math/array" rel="nofollow">math/array</a>. (For the latter, you'll have to set a parameter to make the results of array operations nonstrict. The default is to return strict arrays because of the mental overhead problem.)</p>

CC BY-SA 3.0
2014-01-04T17:52:47.527Z
That is awesome and made my day. For some reason I had not seem it before. Thank you very much.
MaiaVictor
CC BY-SA 3.0
2013-09-30T12:28:44.460Z
2013-09-30T12:36:11.117Z
2013-09-30T12:36:11.117Z
Neil Toronto
<p>This is not completely useless, and this sort of thing does indeed see a few niche uses, for instance when we want to access an array backwards it's faster to loop over <code>array[n-i-1]</code> rather than calling <code>reverse(array)</code> followed by a loop over <code>array[i]</code>.</p>

<p>The flaw I'm seeing here is that this sort of thing will cause access times to scale with the number of times the data in the list have been fiddled with. After $k$ modifications to the data, you'll naturally take at least $O(k)$ time to access the data. If I want to perform $O(n^2)$ non-lookup list transformations I'm not going to be happy unless you flatten it back down to an array first. Changing the data from a function representation, proposed by you, to an array representation takes one access per element, so $O(nk)$ time.</p>

<p>How frequently should we change the representation back? If we rebuild the array after every $l$ operations on it, we need to spend $O(nl)$ time to rebuild every $l$ operations, so the amortised complexity of each operation becomes $O(n)$. The complexity of a lookup becomes $O(l)$ in the worst case. This is worse than an array representation in general.</p>

CC BY-SA 3.0
2013-09-29T16:18:58.170Z
Thanks for clarifying exactly why this is really not O(1) pet operation. It wasn't so clear from the original question.
David Eppstein
CC BY-SA 3.0
2013-09-29T21:09:12.937Z
I don't see how this is worse than an array representation. Your worst cases cases for this representation are the best cases of an array, O(n) per operation and O(1) lookup...
MaiaVictor
CC BY-SA 3.0
2013-09-29T22:13:25.953Z
I specified $O(n)$ per operation and $O(l)$ lookup. If you choose $l = 1$, then the situation is almost completely identical to a standard array - you don't defer list operations at all. If you choose an $l$ that does not increase with $n$, that is $l \in O(1)$, then you have $O(1)$ lookups, but the $O$-notation generally hides larger constants than before. If you choose, for example, $l = n$, so we rebuild an array of $n$ elements when $n$ operations are performed, we will spend, in the worst case, $n-1 \in O(n)$ time on a lookup, making it worse.
ymbirtt
CC BY-SA 3.0
2013-09-30T10:46:42.173Z
@ymbirtt: Maybe there is a normal form addressing formula that can be maintained after every operation. For example, store a lowest index $l$, highest index $h$ and step-size $a$ and use polynomial $l + ai$ to access the data-store, where $i$ is the requested index. --- The `reverse()` operation could then consist of $(l, h, a) := (h, l, -a)$. The `slice(x..y)` operation could be $(l, h, a) := (l+x, l+y, a)$. Increasing stride by $s$ would be something like $(l, h, a) := (l, l+s\lfloor\frac{h-l}{s}\rfloor, sa)$. But the normal form needs to be tailored to the operations you want to support.
mhelvens
CC BY-SA 3.0
2013-09-28T23:10:30.893Z
2013-09-28T23:10:30.893Z
ymbirtt
<p>The issue is that you are not computing anything, <strong>you are simply postponing them for the time that the array items need to be accessed</strong>. </p>

<p>This is worst in general (regarding the time efficiency of the operations) because every time we need to perform an access operation we need to perform all of these computations again. Even if we are performing the access operation only once on each item, it can be more efficient to perform all similar operations at once.</p>

<p>It would only be useful if you are going to access very few elements of the array over time, in which case there is probably no point to perform these operations on the whole array. We can simply compute the index and access it directly. If you are not using the intermediate arrays in whole then don't compute them, only compute those which you need to access a considerable number of times.</p>

<p>ps: many pure functional programming language do not have environment so there is simply no way of storing the resulting values. However even there you can do either <a href="http://en.wikipedia.org/wiki/Lazy_evaluation" rel="nofollow">lazy evaluation</a> or <a href="http://en.wikipedia.org/wiki/Eager_evaluation" rel="nofollow">eager evaluation</a> (or other evaluation strategies) and what you are describing seems to be similar to the lazy evaluation: not evaluating until we really need the value.</p>

CC BY-SA 3.0
2013-09-29T22:32:02.030Z
Hopefully some programming language expert would also answer the question.
Kaveh
CC BY-SA 3.0
2013-09-29T22:51:14.907Z
I'm not sure it is actually the same thing as postponing computation / lazy evaluation, as some operations would still be much faster this way. For example, `print . reverse . (slice 0 2)`, to get the last 2 elements and print them. Even a lazy language would need to transverse the whole array. This wouldn't. I'm not sure though.

Thanks for the inputs!
MaiaVictor
CC BY-SA 3.0
2013-09-30T10:18:08.830Z
@Viclib: If you compare your approach to the most naive alternative possible, you're bound to end up on top. But no programmer would `reverse` and `slice` an array just to print the last two elements. They'd probably do something like `print(-1, -2)`. My point is: if you want to advance your argument, try to find a use-case where your approach is superior to all alternatives and try to be critical of your own ideas. Perhaps you'll find out they aren't as practical as you thought. On the other hand, perhaps you'll find an ingenious use-case; in which case, please let us know. :-)
mhelvens
CC BY-SA 3.0
2013-09-30T11:09:11.547Z
Haskell and functional programming mantra in general says: `express what you want in a clear way that is intuitive for you, don't worry about performance because the compiler will take care of that`. `reverse . (slice 0 2)` could be intuitive for someone.
MaiaVictor
CC BY-SA 3.0
2013-09-30T12:28:32.927Z
**(1)** Unless you personally know that 'someone', come up with a more convincing use-case. **(2)** I know how tempting it is to invoke the [sufficiently smart compiler](http://c2.com/cgi/wiki?SufficientlySmartCompiler) argument, but there is no such compiler. Unless you can show me one, or personally develop and prove the necessary optimization algorithm. Then publish it. :-) **(3)** You're not being critical about your own ideas, you're still trying to defend them. You'll be much more convincing once you can show that you're aware of the (possible) arguments against your approach.
mhelvens
CC BY-SA 3.0
2013-09-30T12:41:27.403Z
@Kevah: request granted. The trick is to offer users a way to make such an array strict any time they think they will retrieve most of its elements more than once or twice.
Neil Toronto
CC BY-SA 3.0
2014-01-04T17:54:52.787Z
@mhelvens user Neil Toronto provides great arguments above, much better than I did.
MaiaVictor
CC BY-SA 3.0
2013-09-29T22:17:23.983Z
2013-09-29T22:36:17.283Z
2013-09-29T22:36:17.283Z
Kaveh
<p>Many operations on arrays have $O(n)$ complexity. </p>

<p>If we represent arrays as <a href="http://en.wikipedia.org/wiki/Accessor_method" rel="nofollow">accessors methods</a>, many of them could be done in $O(1)$. For example, the $i$th item in the reverse of an array $A$ of size $n$ is given by $reverse(A).i = A[n-1-i]$. So we can define reverse as:</p>

<p>$$reverse := \lambda A:array \ \lambda i:int. \ A[n-1-i]$$</p>

<p>and similarly for other operations like 
slicing, zipping, concatenation, and so on.
This technique allows us to implement these complicated operations in constant time without touching the original memory at all.</p>

<ol>
<li><p>What is the formal name of this structure? </p></li>
<li><p>What are the negative aspects of using this structure compared to the standard structure?</p></li>
</ol>

CC BY-SA 3.0
2013-09-28T12:32:59.107Z
Without knowing whether or not this is actually being done already: One consideration is that you're sacrificing random access speed for this. I'm guessing there aren't many applications for which this is worth the gain, as random access is used far more frequently, sometimes in deeply nested loops. --- Also, programmers expect to receive a copy when using an operation that returns a result, and you're passing references. This will cause unexpected behavior when the data is altered. Unless you implement copy-on-write, I suppose.
mhelvens
CC BY-SA 3.0
2013-09-29T09:34:18.633Z
The operations in your proposal do not compose because they all operate on a fixed array and so they are just a flat interface. To make them useful you should write them so that we can easily compute, for example, the reverse of a slice of reverse of two concatenated arrays. For that sort of thing you will end up nesting lots of $\lambda$'s inside each other, and that means the cost of operations will depend on the number of array transformations performed.
Andrej Bauer
CC BY-SA 3.0
2013-09-29T09:37:38.980Z
Downvoters, please explain.
David Richerby
CC BY-SA 3.0
2013-09-29T20:42:39.307Z
@David, down-voters are not required to explain their votes, and we should not _demand_ that they explain their votes, see [this](http://meta.cstheory.stackexchange.com/q/1395/) and [this](http://meta.cstheory.stackexchange.com/q/2722/).
Kaveh
CC BY-SA 3.0
2013-09-29T20:45:34.070Z
ps: my guess would be that the down-votes are probably about formatting and readability issues, 20+ line of code is not readable. The OP should make the question more concise and readable.
Kaveh
CC BY-SA 3.0
2013-09-29T21:07:14.723Z
I don't see how it is not readable at all? It is 20+ line of code because I explained each single line with some detail. Also if you don't understand something you should ask. I'm not able to guess.
MaiaVictor
CC BY-SA 3.0
2013-09-29T21:30:14.447Z
@Kaveh It was intended as a request, rather than a demand but I agree the terseness may have sent the wrong tone.
David Richerby
CC BY-SA 3.0
2013-09-29T21:42:34.143Z
@Viclib, as I understand it you need 0 lines of code to state the question clearly.
Kaveh
CC BY-SA 3.0
2013-09-29T21:47:45.973Z
So please, help me out. I've added the code to make the explanation easier to understand in a clear and non ambiguous way, rather than explaining something abstract with words. User Ymbirtt seems to have understood perfectly what I meant without having to ask anything. I don't know how I could've achieved that without code.
MaiaVictor
CC BY-SA 3.0
2013-09-29T22:38:21.060Z
My downvote was based less on the confusing writeup with code in place of English (although it was indeed confusing) and more on the misleading question: It is not true that the most common operations in this structure are all $O(1)$. In particular array accesses become $\Theta($nesting level of transformations$)$.
David Eppstein
CC BY-SA 3.0
2013-09-29T22:42:04.810Z
This is valid. Could've been an answer/comment instead of a plain downvote, though. But again, I believe there is not much point in downvoting a question, so...
MaiaVictor
CC BY-SA 3.0
2013-09-29T22:43:25.487Z
@Kaveh great edit, thanks. I wish I was able to express myself this way.
MaiaVictor
<ds.data-structures><pl.programming-languages><functional-programming>
Is there an array structure that allows for O(1) complexity for reverse, zip, slice etc operations?
MaiaVictor
# Is there an array structure that allows for O(1) complexity for reverse, zip, slice etc operations?

(Asked by: username_0 on 2013-09-28)

Many operations on arrays have $O(n)$ complexity.

If we represent arrays as [accessors methods](http://en.wikipedia.org/wiki/Accessor_method), many of them could be done in $O(1)$. For example, the $i$th item in the reverse of an array $A$ of size $n$ is given by $reverse(A).i = A[n-1-i]$. So we can define reverse as:

$$reverse := \lambda A:array \ \lambda i:int. \ A[n-1-i]$$

and similarly for other operations like
slicing, zipping, concatenation, and so on.
This technique allows us to implement these complicated operations in constant time without touching the original memory at all.

1. What is the formal name of this structure?
2. What are the negative aspects of using this structure compared to the standard structure?

**Tags:** ds.data-structures, pl.programming-languages, functional-programming
> **Comments:**
> **username_1**: Without knowing whether or not this is actually being done already: One consideration is that you're sacrificing random access speed for this. I'm guessing there aren't many applications for which this is worth the gain, as random access is used far more frequently, sometimes in deeply nested loops. --- Also, programmers expect to receive a copy when using an operation that returns a result, and you're passing references. This will cause unexpected behavior when the data is altered. Unless you implement copy-on-write, I suppose.  
> **username_2**: The operations in your proposal do not compose because they all operate on a fixed array and so they are just a flat interface. To make them useful you should write them so that we can easily compute, for example, the reverse of a slice of reverse of two concatenated arrays. For that sort of thing you will end up nesting lots of $\lambda$'s inside each other, and that means the cost of operations will depend on the number of array transformations performed.  
> **username_3**: Downvoters, please explain.  
> **username_4**: @David, down-voters are not required to explain their votes, and we should not _demand_ that they explain their votes, see [this](http://meta.cstheory.stackexchange.com/q/1395/) and [this](http://meta.cstheory.stackexchange.com/q/2722/).  
> **username_4**: ps: my guess would be that the down-votes are probably about formatting and readability issues, 20+ line of code is not readable. The OP should make the question more concise and readable.  
> **username_0**: I don't see how it is not readable at all? It is 20+ line of code because I explained each single line with some detail. Also if you don't understand something you should ask. I'm not able to guess.  
> **username_3**: @Kaveh It was intended as a request, rather than a demand but I agree the terseness may have sent the wrong tone.  
> **username_4**: @Viclib, as I understand it you need 0 lines of code to state the question clearly.  
> **username_0**: So please, help me out. I've added the code to make the explanation easier to understand in a clear and non ambiguous way, rather than explaining something abstract with words. User Ymbirtt seems to have understood perfectly what I meant without having to ask anything. I don't know how I could've achieved that without code.  
> **username_5**: My downvote was based less on the confusing writeup with code in place of English (although it was indeed confusing) and more on the misleading question: It is not true that the most common operations in this structure are all $O(1)$. In particular array accesses become $\Theta($nesting level of transformations$)$.  
> **username_0**: This is valid. Could've been an answer/comment instead of a plain downvote, though. But again, I believe there is not much point in downvoting a question, so...  
> **username_0**: @Kaveh great edit, thanks. I wish I was able to express myself this way.  

---

## 3 answers

### Answer by username_6 on 2013-09-30. Score: 4 | Accepted answer

I call them *nonstrict arrays*.

They're not only not completely useless, but very useful and interesting. Operating on them is also not the worst in time efficiency, but can be asymptotically equivalent if done correctly. Further, if an array is just a lambda with a shape attached to it, then like transformations, pointwise operations are also not much more than function composition.

For a good start, look here:

[Regular, shape-polymorphic, parallel arrays in Haskell, Gabriele Keller, Manuel Chakravarty, Roman Leshchinskiy, Simon Peyton Jones, and Ben Lippmeier. ICFP 2010.](http://research.microsoft.com/en-us/um/people/simonpj/papers/ndp/RArrays.pdf)

The authors present a multidimensional version of the arrays you're asking about, which are like NumPy's multidimensional arrays but in Haskell style. Arrays are just a lambda and a shape, and they don't cache computed elements for faster retrieval in the future. But at any time, a user can force one to compute and cache all of its elements.

These arrays force users to think in terms of whole-array operations. I consider that a plus, as it encourages a more declarative style of coding than writing loops that micromanage elements. I liked this style better when I was using NumPy as well. Others have different opinions.

The upside is automatic fusion of array operations, which reduces the memory cost of whole-array operations. It also helps immensely with parallelizing sequences of operations. Allocating space for intermediate arrays is a synchronization point. But if intermediate arrays are nonstrict, their elements don't require space, so that synchronization point disappears. Further, this "loop fusion" happens *even when operations are in different functions*, which would be very difficult, if not impossible, for a static optimizer to do.

One downside is that it's harder to reason about the performance of operations on nonstrict arrays. Another is that users have to decide which arrays to force to be strict. There are some simple rules of thumb, but they can't reduce the mental overhead to zero.

If you want to play with implementations, check out Haskell's [Repa](http://hackage.haskell.org/package/repa) and Racket's [math/array](http://docs.racket-lang.org/math/array.html?q=math/array). (For the latter, you'll have to set a parameter to make the results of array operations nonstrict. The default is to return strict arrays because of the mental overhead problem.)

> **Comments:**
> **username_0**: That is awesome and made my day. For some reason I had not seem it before. Thank you very much.  

---

### Answer by username_7 on 2013-09-28. Score: 6

This is not completely useless, and this sort of thing does indeed see a few niche uses, for instance when we want to access an array backwards it's faster to loop over `array[n-i-1]` rather than calling `reverse(array)` followed by a loop over `array[i]`.

The flaw I'm seeing here is that this sort of thing will cause access times to scale with the number of times the data in the list have been fiddled with. After $k$ modifications to the data, you'll naturally take at least $O(k)$ time to access the data. If I want to perform $O(n^2)$ non-lookup list transformations I'm not going to be happy unless you flatten it back down to an array first. Changing the data from a function representation, proposed by you, to an array representation takes one access per element, so $O(nk)$ time.

How frequently should we change the representation back? If we rebuild the array after every $l$ operations on it, we need to spend $O(nl)$ time to rebuild every $l$ operations, so the amortised complexity of each operation becomes $O(n)$. The complexity of a lookup becomes $O(l)$ in the worst case. This is worse than an array representation in general.

> **Comments:**
> **username_5**: Thanks for clarifying exactly why this is really not O(1) pet operation. It wasn't so clear from the original question.  
> **username_0**: I don't see how this is worse than an array representation. Your worst cases cases for this representation are the best cases of an array, O(n) per operation and O(1) lookup...  
> **username_7**: I specified $O(n)$ per operation and $O(l)$ lookup. If you choose $l = 1$, then the situation is almost completely identical to a standard array - you don't defer list operations at all. If you choose an $l$ that does not increase with $n$, that is $l \in O(1)$, then you have $O(1)$ lookups, but the $O$-notation generally hides larger constants than before. If you choose, for example, $l = n$, so we rebuild an array of $n$ elements when $n$ operations are performed, we will spend, in the worst case, $n-1 \in O(n)$ time on a lookup, making it worse.  
> **username_1**: @ymbirtt: Maybe there is a normal form addressing formula that can be maintained after every operation. For example, store a lowest index $l$, highest index $h$ and step-size $a$ and use polynomial $l + ai$ to access the data-store, where $i$ is the requested index. --- The `reverse()` operation could then consist of $(l, h, a) := (h, l, -a)$. The `slice(x..y)` operation could be $(l, h, a) := (l+x, l+y, a)$. Increasing stride by $s$ would be something like $(l, h, a) := (l, l+s\lfloor\frac{h-l}{s}\rfloor, sa)$. But the normal form needs to be tailored to the operations you want to support.  

---

### Answer by username_4 on 2013-09-29. Score: 2

The issue is that you are not computing anything, **you are simply postponing them for the time that the array items need to be accessed**.

This is worst in general (regarding the time efficiency of the operations) because every time we need to perform an access operation we need to perform all of these computations again. Even if we are performing the access operation only once on each item, it can be more efficient to perform all similar operations at once.

It would only be useful if you are going to access very few elements of the array over time, in which case there is probably no point to perform these operations on the whole array. We can simply compute the index and access it directly. If you are not using the intermediate arrays in whole then don't compute them, only compute those which you need to access a considerable number of times.

ps: many pure functional programming language do not have environment so there is simply no way of storing the resulting values. However even there you can do either [lazy evaluation](http://en.wikipedia.org/wiki/Lazy_evaluation) or [eager evaluation](http://en.wikipedia.org/wiki/Eager_evaluation) (or other evaluation strategies) and what you are describing seems to be similar to the lazy evaluation: not evaluating until we really need the value.

> **Comments:**
> **username_4**: Hopefully some programming language expert would also answer the question.  
> **username_0**: I'm not sure it is actually the same thing as postponing computation / lazy evaluation, as some operations would still be much faster this way. For example, `print . reverse . (slice 0 2)`, to get the last 2 elements and print them. Even a lazy language would need to transverse the whole array. This wouldn't. I'm not sure though.  Thanks for the inputs!  
> **username_1**: @Viclib: If you compare your approach to the most naive alternative possible, you're bound to end up on top. But no programmer would `reverse` and `slice` an array just to print the last two elements. They'd probably do something like `print(-1, -2)`. My point is: if you want to advance your argument, try to find a use-case where your approach is superior to all alternatives and try to be critical of your own ideas. Perhaps you'll find out they aren't as practical as you thought. On the other hand, perhaps you'll find an ingenious use-case; in which case, please let us know. :-)  
> **username_0**: Haskell and functional programming mantra in general says: `express what you want in a clear way that is intuitive for you, don't worry about performance because the compiler will take care of that`. `reverse . (slice 0 2)` could be intuitive for someone.  
> **username_1**: **(1)** Unless you personally know that 'someone', come up with a more convincing use-case. **(2)** I know how tempting it is to invoke the [sufficiently smart compiler](http://c2.com/cgi/wiki?SufficientlySmartCompiler) argument, but there is no such compiler. Unless you can show me one, or personally develop and prove the necessary optimization algorithm. Then publish it. :-) **(3)** You're not being critical about your own ideas, you're still trying to defend them. You'll be much more convincing once you can show that you're aware of the (possible) arguments against your approach.  
> **username_6**: @Kevah: request granted. The trick is to offer users a way to make such an array strict any time they think they will retrieve most of its elements more than once or twice.  
> **username_0**: @mhelvens user Neil Toronto provides great arguments above, much better than I did.  

---

