3

What do you call an iterator that given a list [a, b, c], returns an object of the form { prev, curr, next } for each iteration?

e.g, (? === undefined)

{ prev: ?, curr: a, next: b }
{ prev: a, curr: b, next: c }
{ prev: b, curr: c, next: ? }

I thought tuples, but I am used to think that a tuple is usually a 2-item list so I am undecided.


EDIT: Triples could work, but I was also wondering if there is any mention of this type of structures in the literature. I am familiar with linked lists, but this is different.

EDIT 2: Here is the generator implementation in JavaScript.

  /**
    @syntax
    Parsec.prototype.tuples([a, b, c])
      { prev: ?, curr: a, next: b }
      { prev: a, curr: b, next: c }
      { prev: b, curr: c, next: ? }
    @param {Array|String} list List to iterate.
    @param {Object} [last] Define to use as the last value.
    @param {Object} [prev] Define to use as the first prev value.
    @param {Object} [curr] Define to use as the first curr value.
  */
  function* tuples(list, last, prev, curr) {
    for (let next of list) {
      if (curr !== undefined) yield { prev, curr, next /* add last here? */}
      prev = curr
      curr = next
    }
    yield { prev, curr, last }
  }

closed as primarily opinion-based by gnat, Bart van Ingen Schenau, GlenH7, user22815, durron597 May 13 '15 at 3:20

Many good questions generate some degree of opinion based on expert experience, but answers to this question will tend to be almost entirely based on opinions, rather than facts, references, or specific expertise. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    tuple doesn't mean two items specifically; it can be any number. A two-item tuple is a pair. – Russell Borogove May 12 '15 at 18:51
  • @RussellBorogove True, but it's often used to refer to two items, but in the end you can see I went with tuples anyway. – Jorge Bucaran May 12 '15 at 19:32
  • @RussellBorogove I don't know whether this is correct (probably isn't), but I believe tuple would be better written as t-uple where the t references the number of elements. At least, this is what we (Italians) do when using them in maths. We say n-upla to mean a "tuple" (ordered finite sequence) of n elements. The term may have been born like that where, for some reason, the name of the parameter was often t. So, no, tuples are definitely not only (nor most often) used for 2 elements. – Bakuriu May 12 '15 at 20:19
  • 2
    Recommended reading: On the troubles of naming and terminology. – user22815 May 12 '15 at 22:21
18

Apart from triple (which only means "we have three values") and node (which has been suggested by manlio), I can suggest the following alternatives:

Sliding window

It looks like you always have a window of three consecutives elements in the list. This is the most appropriate name IMHO according to your situation.

That structure does not allow to easily navigate the list in terms of prev, next pointers, however (maybe it is intentional). If you want to navigate the data-structure, you might want to call it a node (like in doubly-linked lists, as manlio said) or a cursor, which is a slightly better name that conveys the iterative capabilities of the object.

Cursor

Iterators in Ada are built upon a so-called Cursor type, which encapsulates the position of an iterator inside a structure, along with Next and Previous operations.

See for example Gem #127 or the Rationale for Ada 2005.

Zipper

You question originally reminded me of Zippers which are construct usually found with purely functional data-structures. They allow to iterate over a structure while keeping enough context to navigate it.

For example, a list zipper would contain the reversed list of previous elements (Prefix), Current element and the usual Tail list:

(Prefix,Current,Tail)

It is easy to build a zipper for the next element in constant time:

(cons(Current,Prefix),head(Tail),tail(Tail))

Or, a zipper for the previous element in constant time:

(tail(Prefix),head(Prefix),cons(Current,Tail))

Of course, the cost of this approach is that you are manipulating two lists instead of one (during the lifetime of the iterator/zipper). Contrary to doubly-linked lists, you don't have to mutate your data-structures.

Your structure is clearly not a zipper, but it shared enough similarities with them that I thought it would be interesting to write about them.

  • 3
    'Sliding window' have traits to 'convolution' which is related to 'fold' in the functional programming world. Whats funny though is the term convolution is a french translation from the word 'faltung' used by german mathematicians...faltung, fold, the array is folding on himself like the convolutions of the Amazon river. But that are mostly etymology convolutions. ;) – matovitch May 12 '15 at 12:09
9

In Scala, this is called a sliding window:

Seq(1, 2, 3, 4, 5).sliding(2).foreach(println)
// List(1, 2)
// List(2, 3)
// List(3, 4)
// List(4, 5)

As opposed to grouped when the elements don't overlap:

Seq(1, 2, 3, 4, 5).grouped(2).foreach(println)
// List(1, 2)
// List(3, 4)
// List(5)

In Ruby, it is called cons:

[1, 2, 3, 4, 5].each_cons(2).to_a
# => [[1, 2], [2, 3], [3, 4], [4, 5]]

and the other one is called slice:

[1, 2, 3, 4, 5].each_slice(2).to_a
# => [[1, 2], [3, 4], [5]]

Note: in your case, the window starts before the first element and ends after the last, whereas in Ruby and Scala it starts at the first element and ends at the last, but that's just an arbitrary API design choice, and probably shouldn't affect the name.

I think "cons" (for "consecutive") is an unfortunate choice of name, because it clashes with the well-established term "cons" for "construct", as in Lisp and other functional languages. I like "sliding window" or "sliding view" much better.

5

A tuple is a finite sequence (ordered list) of elements. It's true in mathematics, relational databases and many languages (e.g. C++, Prolog, Python...).

So tuple could be a good name.

node is an alternative since an object of the form {prev, curr, next} remembers of a node of a doubly linked list.

  • +1 for node, which is most likely the intended usage of this data-structure. – coredump May 12 '15 at 7:58
-3

Well this seems like a theory question on algorithms and datastructures.
As for the datastructure, if you want to return the three results at once, of course you need to put them into one datastructure, and of course that would make it a triple. Without a given syntax it's hard to give an answer and the question seems not properly stated, I feel the question is also how to calculate previous and next, and for this I would say something like:

curry = this;
prev = this;
next = this;
prev —-;
next++;

if(pre <0) prev = undefined;
if (next >= length) next = undefined;

As for the name of this kind of itertor, well as you already did I would call it triple or triplet, as it needs to store 3 values.

  • 6
    I think OP is asking for the name of this type of iterator, not how to implement one. – Ixrec May 12 '15 at 6:52

Not the answer you're looking for? Browse other questions tagged or ask your own question.