code review 156079: add Take, TakeWhile, Drop, DropWhile to exp/iterable

add Take, TakeWhile, Drop, DropWhile to exp/iterable

[sigpipe, 2009-11-18 17:41:38]

Hello golang-dev@golang.org, r, rsc,

I'd like you to review the following change.

[rsc, 2009-11-18 17:51:10]

A few comments.  David Symonds is the right reviewer.

http://codereview.appspot.com/156079/diff/6/1001
File src/pkg/exp/iterable/iterable.go (right):

http://codereview.appspot.com/156079/diff/6/1001#newcode146
src/pkg/exp/iterable/iterable.go:146: return t.ch;
Please test the case where you call Iter() multiple
times on the same Iterable.  You should get the 
same data back, and you won't with this code:
you need to allocate a new channel each time.

It sounds like you want something more like

type iterFunc func(ch chan<- interface{})

func (f iterFunc) Iter() <-chan interface{} {
    ch := make(chan interface{});
    go f(ch);
    return ch;
}

which makes the bug much harder.

In fact that might be good enough to replace
the mappedIterable and filteredIterable types
above too.

http://codereview.appspot.com/156079/diff/6/1001#newcode153
src/pkg/exp/iterable/iterable.go:153: if n > 0 {
Another place where there is shared state between
different instances: n.  Probably want to do m := n
here and then change all the n below to m.
(You could write n := n but that's a bit confusing.)

http://codereview.appspot.com/156079/diff/6/1001#newcode167
src/pkg/exp/iterable/iterable.go:167: // Take(iter, f) returns an Iterable that
contains the first N elements
Doc comment describes Take not TakeWhile.

http://codereview.appspot.com/156079/diff/6/1001#newcode187
src/pkg/exp/iterable/iterable.go:187: for ; n > 0; n-- {
Same comment about n.

http://codereview.appspot.com/156079/diff/6/1001#newcode198
src/pkg/exp/iterable/iterable.go:198: // Drop(iter, f) removes elements from the
head of the iterator for which the function returns true
Doc comment describes Drop not DropWhile.

[sigpipe, 2009-11-18 18:23:01]

Thanks, Russ.  I've addressed your comments and uploaded a new version.  I
missed the fact that the "n" in the closure would be shared among instances.

[sigpipe, 2009-11-18 18:24:33]

PTAL: updated with comments from rsc

[dsymonds, 2009-11-18 20:59:34]

LGTM

I probably would have named Take/TakeWhile as First/FirstWhile, but that's fine.
Looks good over all.

http://codereview.appspot.com/156079/diff/10/1005
File src/pkg/exp/iterable/iterable.go (right):

http://codereview.appspot.com/156079/diff/10/1005#newcode165
src/pkg/exp/iterable/iterable.go:165: // TakeWhile(iter, f) returns an Iterable
that contains elements from the head of iter until `f` returns false.
// TakeWhile returns an Iterable that contains elements from iter while f is
true.

http://codereview.appspot.com/156079/diff/10/1005#newcode196
src/pkg/exp/iterable/iterable.go:196: func DropWhile(iter Iterable, f
func(interface{}) bool) Iterable {
Can you implement the inner loop as a composition of TakeWhile and not(f)
instead, a la Any?

http://codereview.appspot.com/156079/diff/10/1006
File src/pkg/exp/iterable/iterable_test.go (right):

http://codereview.appspot.com/156079/diff/10/1006#newcode129
src/pkg/exp/iterable/iterable_test.go:129: assertArraysAreEqual(t, Data(res),
[]int{1, 2});	//second test to ensure that .Iter() returns a new channel
nit: use a space after //.

[sigpipe, 2009-11-18 21:27:22]

On 2009/11/18 20:59:34, dsymonds1 wrote:
> LGTM
> 
> I probably would have named Take/TakeWhile as First/FirstWhile, but that's
fine.

Both Haskell and Python use those names, so I used them for consistency.  If it
makes sense to rename them, I won't object.

[sigpipe, 2009-11-18 21:43:44]

On 2009/11/18 20:59:34, dsymonds1 wrote:
> http://codereview.appspot.com/156079/diff/10/1005#newcode196
> src/pkg/exp/iterable/iterable.go:196: func DropWhile(iter Iterable, f
> func(interface{}) bool) Iterable {
> Can you implement the inner loop as a composition of TakeWhile and not(f)
> instead, a la Any?

I don't see an obvious solution since Take returns the head of the list, and
drop returns the tail.  I could use Take and TakeWhile to discard the elements
at the head of the list in Drop/DropWhile instead of duplicating code, I
suppose.

[sigpipe, 2009-11-18 22:13:26]

PTAL: updated with comments from dysmonds1

[dsymonds, 2009-11-18 23:01:00]

LGTM

Just adjustments to the documentation. Russ, feel free to commit this after
these changes (or equivalents that you'd prefer).

http://codereview.appspot.com/156079/diff/1011/16
File src/pkg/exp/iterable/iterable.go (right):

http://codereview.appspot.com/156079/diff/1011/16#newcode147
src/pkg/exp/iterable/iterable.go:147: // Take(iter, N) returns an Iterable that
contains only the first N elements.
// Take returns an Iterable that contains the first n elements of iter.

(match the function arguments, but don't mention them at the start; Partition is
somewhat exceptional)

http://codereview.appspot.com/156079/diff/1011/16#newcode165
src/pkg/exp/iterable/iterable.go:165: // TakeWhile(iter, f) returns an Iterable
that contains elements from iter while f is true.
s/(iter, f)//

http://codereview.appspot.com/156079/diff/1011/16#newcode179
src/pkg/exp/iterable/iterable.go:179: // Drop(iter, N) removes the first N
elements from the Iterable and returns the remainder.
It doesn't so much "remove" the first n elements as return a new Iterable that
skips them. It leaves the original intact.

// Drop returns an Iterable that returns each element of iter after the first n
elements.

http://codereview.appspot.com/156079/diff/1011/16#newcode195
src/pkg/exp/iterable/iterable.go:195: // DropWhile(iter, f) removes elements
from the head of the iterator for which `f` returns true.
// DropWhile returns an Iterable that returns each element of iter after the
initial sequence for which f returns true.

[rsc, 2009-11-18 23:03:18]

http://codereview.appspot.com/156079/diff/1011/16
File src/pkg/exp/iterable/iterable.go (right):

http://codereview.appspot.com/156079/diff/1011/16#newcode184
src/pkg/exp/iterable/iterable.go:184: for ; m > 0; m-- {
This will repeatedly read from a closed channel if it closes
before you're ready for it.

for v := range it {
    if m > 0 {
        m--;
        continue;
    }
    ch <- v;
}

http://codereview.appspot.com/156079/diff/1011/16#newcode197
src/pkg/exp/iterable/iterable.go:197: return iterFunc(func(ch chan interface{})
{
same comment about two ranges

[sigpipe, 2009-11-18 23:24:11]

Updated doc comments with suggestions from dsymonds1.

Added check for closed channel in Drop and DropWhile.

Added unit tests for Drop and DropWhile to check for cases where all items are
dropped.

[rsc, 2009-11-18 23:52:34]

http://codereview.appspot.com/156079/diff/18/1018
File src/pkg/exp/iterable/iterable.go (right):

http://codereview.appspot.com/156079/diff/18/1018#newcode185
src/pkg/exp/iterable/iterable.go:185: if <-it == nil {
This is not right.  It's valid for the interface to get nil normally.
The loop I suggested before handles all these subtleties.

http://codereview.appspot.com/156079/diff/18/1018#newcode202
src/pkg/exp/iterable/iterable.go:202: for v := range it {
Same issue: just use one loop.

drop := true;
for v := range it {
    if drop {
        if f(v) {
            continue;
        }
        drop = false;
    }
    ch <- v;
}

[sigpipe, 2009-11-19 00:11:38]

On 2009/11/18 23:52:34, rsc wrote:
> http://codereview.appspot.com/156079/diff/18/1018
> File src/pkg/exp/iterable/iterable.go (right):
> 
> http://codereview.appspot.com/156079/diff/18/1018#newcode185
> src/pkg/exp/iterable/iterable.go:185: if <-it == nil {
> This is not right.  It's valid for the interface to get nil normally.
> The loop I suggested before handles all these subtleties.
> 
> http://codereview.appspot.com/156079/diff/18/1018#newcode202
> src/pkg/exp/iterable/iterable.go:202: for v := range it {
> Same issue: just use one loop.
> 
> drop := true;
> for v := range it {
>     if drop {
>         if f(v) {
>             continue;
>         }
>         drop = false;
>     }
>     ch <- v;
> }

Sorry, for some reason I thought that was a quote of the existing code.  Now I
understand what you were saying.

I'm curious though, what are you supposed to do in goroutines where you don't
use range?  if !closed(it)  ?

[sigpipe, 2009-11-19 00:51:17]

fixed code to use loop rsc suggested to properly handle input channel closing
prematurely.

[rsc, 2009-11-20 04:20:22]

david, one last look?

[dsymonds, 2009-11-20 04:27:20]

http://codereview.appspot.com/156079/diff/1022/22
File src/pkg/exp/iterable/iterable.go (right):

http://codereview.appspot.com/156079/diff/1022/22#newcode150
src/pkg/exp/iterable/iterable.go:150: m := n;
You could flatten this a bit:

  defer close(ch);
  if (n <= 0) { return }
  m := n;
  for v := range iter.Iter() {
    ...
  }

either is fine with me.

http://codereview.appspot.com/156079/diff/1022/22#newcode161
src/pkg/exp/iterable/iterable.go:161: return;
This "return;" doesn't do anything.

http://codereview.appspot.com/156079/diff/1022/22#newcode175
src/pkg/exp/iterable/iterable.go:175: return;
another useless return

http://codereview.appspot.com/156079/diff/1022/22#newcode191
src/pkg/exp/iterable/iterable.go:191: return;
ditto

http://codereview.appspot.com/156079/diff/1022/22#newcode209
src/pkg/exp/iterable/iterable.go:209: return;
ditto

http://codereview.appspot.com/156079/diff/1022/23
File src/pkg/exp/iterable/iterable_test.go (right):

http://codereview.appspot.com/156079/diff/1022/23#newcode155
src/pkg/exp/iterable/iterable_test.go:155: func TestDropWhile(t *testing.T) {
Can you add a test case where the predicate function is always false, testing
that none are dropped?

[sigpipe, 2009-11-20 17:13:27]

Remove unnecessary return statements.

Flatten code in Take as suggested.

Add additional unit tests for better coverage.

[rsc, 2009-11-20 19:40:35]

LGTM

 will submit with your other change

[rsc, 2009-11-20 19:40:57]

sorry, wrong CL.
still waiting for a final LGTM from dsymonds here

[dsymonds, 2009-11-20 23:02:27]

LGTM

Thanks!

[rsc, 2009-11-24 19:31:17]

*** Submitted as http://code.google.com/p/go/source/detail?r=949a68cffc96 ***

add Take, TakeWhile, Drop, DropWhile to exp/iterable

R=dsymonds1, rsc
http://codereview.appspot.com/156079

Committer: Russ Cox <rsc@golang.org>