Loops on loops on loops

It's about Iterables and Iterators


Garrett Dawson

@killtheliterate

Loops Are Programming

  • Loops are a fundamental
  • Without them... there is no program
  • You need loops and variables to be a programming language

The First Iteration

Ada Lovelace and the Analytical Engine

Ada Lovelace.jpg

Primordial Software


  ****** Algol 60 ******
  FOR i:=1 UNTIL 5 DO
     FOR j:=1 UNTIL i DO
        OUTTEXT("*");
     OUTLINE

Primordial Software


  * COBOL
  IDENTIFICATION DIVISION.
         PROGRAM-ID. Display-Triangle.
   
         DATA DIVISION.
         WORKING-STORAGE SECTION.
         01  Outer-Counter PIC 9.
         01  Inner-Counter PIC 9. 
   
         PROCEDURE DIVISION.
         PERFORM VARYING Outer-Counter FROM 1 BY 1 UNTIL 5 < Outer-Counter
   
             PERFORM VARYING Inner-Counter FROM 1 BY 1
                     UNTIL Outer-Counter < Inner-Counter
                 DISPLAY "*" NO ADVANCING
             END-PERFORM
   
             DISPLAY "" *> Output a newline
         END-PERFORM
   
         GOBACK
         .

Primordial Software


  'Visual Basic
  Public OutConsole As Scripting.TextStream
  For i = 0 To 4
      For j = 0 To i
          OutConsole.Write "*"
      Next j 
      OutConsole.WriteLine
  Next i

It's at least 1995

  • ...and you're probably a JS Developer
  • ...some of the time
  • ...so what do we already know?

The Ancient

for


  // loopable
  const theThing = ['hello', 'humans', 'in', 'this', 'room']

  // the loop
  for(let i = 0; i < theThing.length; i = i + 1) {
    console.log(theThing[i]) // hello, humans...
  }

Goodish Ideas

for-in


  // loopable
  const otherThing = ['hello', 'humans', 'in', 'this', 'room']

  // the loop
  for(let i in otherThing) {
    console.log(otherThing[i]) // hello, humans...
  }

Badish Ideas

...iterate on all enumerable properties


  // loopable
  const theCollection = ['hello', 'humans', 'in', 'this', 'room']

  // shwhoops
  theCollection.alsoEnumerable = 'enumerated'

  // the loop
  for(let i in otherThing) {
    console.log(otherThing[i]) // hello, humans... enumerated
  }

Better Ideas

Array#applicatives


  // loopable
  const say = ['hello', 'humans', 'in', 'this', 'room']

  // weird...
  say.justLeavingThisHere = 'boo'

  // the loop
  otherThing.forEach(el => console.log(el)) // hello, humans...

Extract the Patterns...

  • A list of things (Iterable)
  • A thing that steps through the list (Iterator)

Extract the Patterns


  // loopable
  const theIterable = [1,2,3]

  // the loop
  theIterable.forEach(el => console.log(el)) // 1, 2, 3

Thus Spoke TC39

Builtin Iterators

  • for-of
  • ...spread
  • {destructuring, assignment}

for-of


  // an iterable
  const theIterable = 'a string is a list of characters'

  // an iterator
  // access the member directly
  // instead of by index
  for(let char of theIterable) {
    console.log(char)
  }

...spread


  // an iterable
  const theIterable = ['an', 'array', 'is', 'iterable'] 

  // an iterator
  const newArray = [...theIterable]

  // arguments is iterable
  const fn = (...args) => { args.forEach(el => console.log(el)) }

  fn(1, 2, 3)

{destructuring, assignment}


  // an iterable
  const theCollection = ['hello', 'humans', 'in', 'this', 'room']

  // an iterator
  let [these, are, pieces, ...iterable] = theCollection

  console.log(these) // 'hello'
  console.log(iterable) // ['this', 'room']

Comprehensions

The future is in the future


  // array comprehension
  const newArray = [for (i of [ 1, 2, 3 ]) i * i ]
  console.log(newArray) // 1, 4, 9

  // generator comprehension
  const newGen = (for (i of [ 1, 2, 3 ]) i * i )
  console.log(newGen.next()) // {value: 1, done: false}
  console.log(newGen.next()) // {value: 4, done: false}

Thus Spoke TC39

Builtin Iterables

  • String
  • Array
  • Set
  • Map
  • Generators

Strings


  // an iterable
  const theIterable = 'this is iterable'

  // an iterator
  for(let char of theIterable) {
    console.log(char) // each char
  }

  // an iterator
  const chars = [...theIterable]

  console.log(chars) // ['t','h','i','s',' '...]

Arrays


  // an iterable
  const theIterable = ['this', 'is', 'iterable']

  // an iterator
  for(let words of theIterable) {
    console.log(words) // 'this' 'is'...
  }

  // an iterator
  const sentence = [...theIterable]
  console.log(sentence) // ['this', 'is', 'iterable']

Sets

The Set object lets you store unique values of any type, whether primitive values or object references.

Sets


  // an iterable
  const theIterable = new Set()
  theIterable.add(1)
  theIterable.add(3)
  theIterable.add(2)
  theIterable.add(2)

  // an iterator
  for(let num of theIterable) {
    console.log(num) // 1, 3, 2
  }

  // an iterator
  const numbers = [...theIterable]
  console.log(numbers) // [1,3,2]

Maps

The Map object is a simple key/value map. Any value (both objects and primitive values) may be used as either a key or a value.

Maps


  // an iterable
  const theIterable = new Map()
  theIterable.set('one', 1)
  theIterable.set('three', 3)
  theIterable.set('two', 2)

  // an iterator
  for(let numTuple of theIterable) {
    console.log(numTuple) // ['one', 1]...
  }

  // an iterator
  const tuples = [...theIterable]
  console.log(tuples) // [['one', 1]...]

Generators

Generators are functions which can be exited and later re-entered. Their context (variable bindings) will be saved across re-entrances.

Generators


  // an iterable
  const maker = function* () {
    yield 1
    yield 2
    yield 3
  }

  const theIterable = maker() // this gives us back a generator object
  const first = theIterable.next() // which we can step through
  console.log(first) // {value: 1, done: false}

Generators


  // an iterable
  const maker = function* () {
    let index = 0 // the mutated state will be persisted

    while(index < 3) {
      yield index++
    }
  }

  const theIterable = maker() // this gives us back a generator object

  // which we can operate on with an iterator
  // this works because the generator is finite
  const nums = [...theIterable] // [0,1,2]

Generators


  const maker = function* () {
    let first = yield
    let second = yield first
    let third = yield second
    yield
  }

  const echo = maker()

  console.log(echo.next(1))// {value: null, done: false}
  console.log(echo.next(500)) // {value: 500, done: false}
  console.log(echo.next('sup')) // {value: 'sup', done: false}

Think in Iterables


  const anIterable = 'I am iterable'
  const also = ['so', 'am', 'i']

  for(i of anIterable) {
    console.log(i)
  }

  for(i of also) {
    console.log(i)
  }

Protocol is the word

  • AKA an interface
  • ...I'm going with typeclass

Iterator Protocol

{ }.next()

An object is an iterator when it knows how to access items from a collection one at a time, while keeping track of its current position within that sequence

Let's Make an Iterator

...for a linked list

http://bit.ly/1OVllSX


  // this is what a linked list looks like
  {val: 1, rest: {val: 2, rest: {val: 3, rest: {val: 4, rest: null}}}}

  // basically an array
  [1, 2, 3, 4]

Iterable Protocol

[Symbol.iterator]

The iterable protocol allows JavaScript objects to define or customize their iteration behavior, such as what values are looped over in a for..of construct.

Let's make an Iterable

...still a linked list

http://bit.ly/1MVVXxN


  // give our type an iteration protocol
  const iterable = LinkedList()[Symbol.iterator] = () => // etc

Lazy Lists

possible infinity

http://bit.ly/1DzRyhL

Lazy Lists

What does it do?

  • Event streams
  • Websockets
  • ...essentially, unknown lengths

Loops on loops on loops

It's about Iterables and Iterators


Garrett Dawson

@killtheliterate