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 }
}
4
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.
1
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.
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
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.
1