CODEWITHSUNDEEP
iteratornim-lang
Zecong Hu
Zecong Hu

Reputation: 3224

Implementing map & min that takes the tables.keys iterator as argument in Nim

I would like to define overloads of map and min/max (as originally defined in sequtils) that works for tables.keys. Specifically, I want to be able to write something like the following:

import sequtils, sugar, tables

# A mapping from coordinates (x, y) to values.
var locations = initTable[(int, int), int]()
# Put in some random values.
locations[(1, 2)] = 1
locations[(2, 1)] = 2
locations[(-2, 5)] = 3

# Get the minimum X coordinate.
let minX = locations.keys.map(xy => xy[0]).min
echo minX

Now this fails with:

/usercode/in.nim(12, 24) Error: type mismatch: got <iterable[lent (int, int)], proc (xy: GenericParam): untyped>
but expected one of:
proc map[T, S](s: openArray[T]; op: proc (x: T): S {.closure.}): seq[S]
  first type mismatch at position: 1
  required type for s: openArray[T]
  but expression 'keys(locations)' is of type: iterable[lent (int, int)]

expression: map(keys(locations), proc (xy: auto): auto = xy[0])

Below are my three attempts at writing a map that works (code on Nim playground: https://play.nim-lang.org/#ix=3Heq). Attempts 1 & 2 failed and attempt 3 succeeded. Similarly, I implemented min using both attempt 1 & attempt 2, and attempt 1 failed while attempt 2 succeeded.

However, I'm confused as to why the previous attempts fail, and what the best practice is:

Attempt 1: Function that takes an iterable[T].

Since the Nim manual seems to imply that the result type of calling an iterator is iterable[T], I tried defining map for iterable[T] like this:

iterator map[A, B](iter: iterable[A], fn: A -> B): B =
  for x in iter:
    yield fn(x)

But it failed with a pretty long and confusing message:

/usercode/in.nim(16, 24) template/generic instantiation of `map` from here
/usercode/in.nim(11, 12) Error: type mismatch: got <iterable[(int, int)]>
but expected one of:
iterator items(a: cstring): char
  first type mismatch at position: 1
  required type for a: cstring
  but expression 'iter' is of type: iterable[(int, int)]
... (more output like this)

From my understanding it seems to say that items is not defined for iterable[T], which seems weird to me because I think items is exactly what's need for an object to be iterable?

Attempt 2: Function that returns an iterator.

I basically copied the implementation in def-/nim-itertools and defined a map function that takes an iterator and returns a new closure iterator:

type Iterable[T] = (iterator: T)

func map[A, B](iter: Iterable[A], fn: A -> B): iterator: B =
  (iterator: B =
    for x in iter():
      yield fn(x))

but this failed with:

/usercode/in.nim(25, 24) Error: type mismatch: got <iterable[lent (int, int)], proc (xy: GenericParam): untyped>
but expected one of:
func map[A, B](iter: Iterable[A]; fn: A -> B): B
  first type mismatch at position: 1
  required type for iter: Iterable[map.A]
  but expression 'keys(locations)' is of type: iterable[lent (int, int)]
proc map[T, S](s: openArray[T]; op: proc (x: T): S {.closure.}): seq[S]
  first type mismatch at position: 1
  required type for s: openArray[T]
  but expression 'keys(locations)' is of type: iterable[lent (int, int)]

expression: map(keys(locations), proc (xy: auto): auto = xy[0])

which hints that maybe tables.keys doesn't return an iterator?

Attempt 3: Rewrite keys using attempt 2.

This replaces tables.keys using a custom myKeys that's implemented in a similar fashion to the version of map in attempt 2. Combined with map in attempt 2, this works:

func myKeys[K, V](table: Table[K, V]): iterator: K =
  (iterator: K =
    for x in table.keys:
      yield x)

Upvotes: 5

Views: 707

Answers (1)

Dimitri Lesnoff
Dimitri Lesnoff

Reputation: 382

Explanation of errors in first attempts

which hints that maybe tables.keys doesn't return an iterator

You are right. It does not return an iterator, it is an iterator that returns elements of the type of your Table keys. Unlike in python3, there seems to be no difference between type(locations.keys) and type(locations.keys()). They both return (int, int).

Here is keys prototype:

iterator keys[A, B](t: Table[A, B]): lent A

The lent keyword avoids copies from the Table elements.

Hence you get a type mismatch for your first and second attempt: locations.keys.map(xy => xy[0]) has an incorrect first parameter, since you get a (int, int) element where you expect a iterable[A].

Proposals

  1. As for a solution, you can either first convert your keys to a sequence (which is heavy), like hola suggested.
  2. You can directly rewrite a procedure for your specific application, mixing both the copy in the sequence and your operation, gaining a bit in performance.
import tables

# A mapping from coordinates (x, y) to values.
var locations = initTable[(int, int), int]()

# Put in some random values.
locations[(1, 2)] = 1
locations[(2, 1)] = 2
locations[(-2, 5)] = 3

func firstCoordinate[X, Y, V](table: Table[(X, Y), V]): seq[X] =
  result = @[]
  for x in table.keys:
    result.add(x[0])

let minX = locations.firstCoordinate.min
echo minX

This is not strictly adhering your API, but should be more efficient.

Upvotes: 0

Related Questions