Feature request: efficient builtins for drop and rest

[fadado]

I am very happy to see how the development of jq is being revived. I will take advantage to insist on my particular feature request: an efficient implementation for drop and rest builtins. The prototypes I copy at the end are semantically correct, but extremely inefficient!

Thanks and encouragement!

def drop($n; g):
    select($n >= 0) |  # not defined for n < 0 or n >= #g
    if $n == 0
    then g
    else
        foreach g as $item ($n; .-1;  # . will never reach -(infinity), I hope!
            if . < 0 then $item else empty end)
    end
; 
def rest(g):
    foreach g as $item (1; .-1;  # . will never reach -(infinity), I hope!
        if . < 0 then $item else empty end)
;

[nicowilliams]

Nice!

[nicowilliams]

Thanks!

[pkoppstein]

Speaking of which, here is a more direct and efficient version of first/1 than what is currently in builtin.jq:

 def first(g): label $out | foreach g as $item (0; .+1; if . == 2 then break $out else $item end);

[nicowilliams]

@pkoppstein I was thinking of doing something slightly different for first(g) that only evals g once, something like:

def first(g): try g | error({__jq:true,__value:.}) catch if .__jq and has("__value") then .value else error(.) end;

EDIT: Yes, this allocates garbage, however, it does only generate one value from g, which might be slow and involve more allocations anyways, so I think the bit of garbage here is ok.

EDIT: Actually, this:

def first(g): try (g | {__jq:true,__v:.}|error) catch if type=="object" and .__jq and has("__v") then .__v else error(.) end;

(since the error thrown by g might not be an object).

[nicowilliams]

(I noticed the other day that first(g) extracts two values from g. I noticed this when the second value was an error, which ruined everything.)

[nicowilliams]

(Also, this is kind of a shortcoming of foreach. There should be a way to output the first value without having to continue in order to decide that we've produced enough values.

[nicowilliams]

@pkoppstein Ahhh, how about this:

def first(g): label $out | foreach g as $item (null; $item, break $out);

This does no garbage allocations, and does not extract more than one value from g.

[nicowilliams]

Simpler! def first(g): label $out | g | ., break $out;

[pkoppstein]

def first(g): label $out | g | ., break $out;

Now that I think about it, that's the def that's been on the FAQ for some time!

Some time ago, we were were talking about zip2(g;h) where g and h are streams. At present, we can write the elegant but ridiculously inefficient:

def zip2(a;b):
  def isempty(s): [label $go | (s, break $go)] | length == 0;
  def bf(s):
    foreach s as $i (0; .+1; if . > 1 then $i else empty end);

  if isempty(a) or isempty(b) then empty
  else [first(a), first(b)], zip2(bf(a); bf(b))
  end;

What can be done to make an efficient zip2/2 possible?

[nicowilliams]

@pkoppstein Unfortunately there's no way to eval two streams in parallel. We would need co-routines for that. I have been wanting co-routines though!

[fadado]

@pkoppstein Unfortunately there's no way to eval two streams in parallel. We would need co-routines for > that. I have been wanting co-routines though!

And what about rest? Is an efficient rest possible without copying the whole stream?
With first and rest is easy to define zip:

def zip(g1; g2):
  first(g1) as $g1 |  # the first exhausted generator finishes the recursion
  first(g2) as $g2 |
  [$g1, $g2] , zip(rest(g1); rest(g2))
;

With an efficient rest not only zip is available, but also different non-deterministic techniques as presented in http://okmij.org/ftp/Computation/monads.html#LogicT.

JJOR

[nicowilliams]

BTW, zip not only can't have an efficient form without co-routines, but also, as proposed above, can't be safe given non-referentially-transparent functions (e.g., random, when we add it, or inputs now) because it will eval its stream arguments more than once. The latter problem is not too bad: "don't do that" is an obvious answer, but since it can go away with co-routines... ISTM that co-routines is something we really badly need.