Do we need `range()`?

[larsga]

It seems like this is something that keeps coming up in more algorithmic code: a need to be able to generate a sequence of integers n..m. Thoughts?

There is a workaround, but it's not hugely fast:

def range(n)
  if ($n < 0)
    []
  else if (n==0)
    [0]
  else
    range($n-1) + [$n]

[larsga]

A comment was added on this issue that seems to have disappeared. I guess the author deleted it. I thought it was worth bringing up, so I'll repeat the comment, but leave out the author's identity, since presumably they did not want to be associated with this proposal.

The suggestion was to add a new language construct:

{ repeat(n) . : . }  // == { for ([1,2,...,n]) . : . }
[ repeat(n) . ]     // == [ for ([1,2,...,n]) . ]

or

{ range(n,m) . : . }  // == { for([n,...,m]) . : . }
[ range(n,m)  . ]      // == [ for([n,...,m]) . ]

It would be possible to do this, but I'm not convinced this is important enough to become part of the language syntax. A function seems just as user-friendly to me?

[umessi]

Hi @larsga Thank you for bringing it up. My only concern, if we go with the function, was an unnecessary list being created in case the user doesn't want to use the list (e.g. if the user just wants to repeat a task a few number of times). But I figured it isn't probably that big an issue and we will probably have to create a java object anyways to implement the construct. So, I removed my comment, sorry about that.

[larsga]

Oh, I see. The literal .. syntax would be turned into an array literal at compile time if the numbers are given as intervals. If they're not you do need to create the array every time, anyway.

The function will not create a literal, although I have been planning a @Functional annotation for functions that would let the optimizer turn them into literals when all the parameters are constant. If I do that performance in the two cases will be the same.

[umessi]

I noticed that * operator works with strings too. e.g. "a"*5 = "aaaaa" Was it not intended? (I'm not able to find it in the documentation). However it doesn't work with arrays (Should probably add support for it) Anyways, I just wanted to share a faster alternative to range function using this operator.

// [n,m)
def range(n,m)
  [for(zip-with-index([for(split("0"*($m - $n), "")) $n])) .index + .value ]

[larsga]

Having * work with strings was deliberate. It's even used in the built-in example in the playground. :)

But if it doesn't work with arrays we should fix that, agreed. Could you make an issue for it?

Is that function really faster than the recursive version? Did you benchmark it? If so, interesting.

[umessi]

Having * work with strings was deliberate. It's even used in the built-in example in the playground. :)

How did I miss that 😶

But if it doesn't work with arrays we should fix that, agreed. Could you make an issue for it?

Sure!

Is that function really faster than the recursive version? Did you benchmark it? If so, interesting.

I've only tested it in the playground. The recursive function works okay till ~1e3 but it takes virtually forever for 1e4. The code that I suggested above works okay till 1e7. The problem with the recursive function is that time complexity of addition of arrays would at least be of the order of size of lists. For now, let's assume that it is O(n)

range($n-1) + [$n]      // It probably takes O(n) time

which makes the overall complexity to be O(n^2). We can achieve O(n lg n) using divide and conquer:

def multiply(value, n)
  if($n > 0)
   if(mod($n,2)) $value + multiply($value, $n - 1)
   else 
     let m = multiply($value, floor($n/2))
     $m + $m
  else []

def range(n,m)
  [ for (zip-with-index(multiply([$n], $m - $n))) .index + .value ]

It works okay till 1e6 but the difference is visible in playground at 1e7. I'm not familiar with the internal implementations of the functions used but I think the non-recursive code works in O(n).