Nim: How to wrap/derive an iterator from another iterator?

Question

Let's assume we have some existingIterator which iterates over elements of an arbitrary type T. What I now want to achieve is to derive a new iterator from existingIterator with a modified behavior. Think of examples like:

• Limiting the length of the original iterator, e.g., existingIterator.take(n).
• Mapping over the elements, e.g., existingIterator.map(modifier)
• Filtering certain elements, e.g., existingIterator.filter(predicate).

In all these cases I simply want to produce yet another iterator so that I can do something like that:

for x in existingIterator.filter(something)
                         .map(modifier)
                         .take(10):
  ...

My general problem is: How can I write a generic iterator or template which takes an existing iterator and returns a modified iterator?

A follow-up question would be why such essential functionality is not in the standard library -- maybe I'm missing something?

---

Here is what I have tried:

Attempt 1

Let's take the take(n) functionality as an example. My first approach was to use a regular generic iterator:

iterator infinite(): int {.closure.} =
  var i = 0
  while true:
    yield i
    inc i

iterator take[T](it: iterator (): T, numToTake: int): T {.closure.} =
  var i = 0
  for x in it():
    if i < numToTake:
      yield x
    inc i

for x in infinite.take(10):
  echo x

This compiles, but unfortunately, it does not really work: (1) the elements are not properly iterated (they are all just zero, maybe a bug?), (2) it looks like my program is stuck in an endless loop, and (3) it only works for closure iterators, which means that I cannot wrap arbitrary iterators.

Attempt 2

The limitation to closure iterators suggests that this problem actually requires a template solution.

template take[T](it: iterator(): T, numToTake: int): expr {.immediate.} =
  var i = 0
  iterator tmp(): type(it()) =
    for item in it:
      if i < numToTake:
        yield item
        inc i
  tmp

This almost seem to work (i.e., the template compiles). However, if I now call for x in infinite.take(10) I get:

`Error: type mismatch: got (iterator (): int{.closure, gcsafe, locks: 0.})`

I tried to append a () to actually "call" the iterator, but it still doesn't work. So it comes down to the question: How should I construct/return an iterator from a template?

Answer 1

The problem lies in

for x in infinite.take(10):
  echo x

Or, more specifically, the call infinite.take(10), which we can also write as take(infinite, 10). Unlike Sather, Nim doesn't have once arguments for its iterators, so there isn't a way to distinguish between arguments that should be evaluated once per loop and arguments that should be evaluated once per loop iteration.

In the case of passing a closure iterator as an argument to another closure iterator, that means that a new instance of the infinite iterator with a new environment is created each time you go through the loop. This will make infinite start at zero again and again.

Inline iterators will normally evaluate their arguments only once per loop (and this is the expected behavior in most cases). Closure iterators have to undergo a transformation of their body into a state machine, which changes how they are being called. They also can be used differently: in particular, closure iterators can have multiple call sites, unlike inline iterators; e.g. let iter = ...; iter(someArgument); iter(someOtherArgument). As a result, I am not sure if we are looking at a bug or at intended behavior here.

You can fix this by not passing infinite to take directly, but using let first. There's also a bug in your take code in that the loop does not terminate, which you need to also fix. The resulting code would be something like:

iterator infinite(): int {.closure.} =
  var i = 0
  while true:
    yield i
    inc i

iterator take[T](it: iterator (): T, numToTake: int): T {.closure.} =
  var i = 0
  for x in it():
    if i >= numToTake:
      break
    yield x
    inc i

let inf = infinite
for x in inf.take(10):
  echo x

If you wish to parameterize infinite, this can be done by wrapping the iterator in a template or proc, e.g.:

template infiniteFrom(x: int): (iterator (): int) =
  (iterator (): int =
    var i = x
    while true:
      yield i
      inc i)

...

let inf = infiniteFrom(1)
for x in inf.take(10):
  echo x

Answer 2

I've also tried to add functional methods to Nim, and I've ended up wrapping everything in functions. Please take a look at http://forum.nim-lang.org/t/1230 This way you can assign the iterator to a variable before looping over it with for.