Javascript Iterables from Foldables

purpose:

we would like to use for with any structure that contains values and not just Arrays. So we have to generate iterators using reduce /aka fold in any foldable data structure

for(let value of  _ ) {  }

Source Fiddle

Iterators in javascript

In object-oriented programming, the iterator pattern is a design pattern in which an iterator is used to traverse a container and access the container’s elements. Some build in objects like String, Array, TypedArray, Map and Set all have have embeded the iterator pattern. Javascript has specifications on how to provide an iterator for a custom type they are called The iterable protocol and the iterator protocol

Since in Functional Programming Functors are considered “Containers”(most of the time this is a valid metaphor) we could probably provide a generic valid implementation of the Iterator pattern, that will give us access to the contained values. This is also a way to extract values from a monad.

for example for our simple Identity Functor we can implement the iterator protocol easily. Just yield the contained value.

but what if we have a tree how can we get a valid iterator

var node = (left, v, right) => ({

   map: f => node(left.map(f), f(v), right.map(f)),

});


var leaf = v => ({ v: v, map: f => leaf(f(v)), });


var tree = node(leaf(1),3, node(leaf(5), 7, leaf(13)));

One strategy is ti implement a fold/reduce function for the structure for a monoid

Monoid of type m

mempty = Ø : m
mappend = ⊕ : m→ m → m

and then fold over the array monoid ([],concat) to get an Array that we know how to iterate .Fold is easy to implement in most recursive algebraic data structures like trees

//https://medium.com/@dimpapadim3
  var node = (left, value, right) => ({ 
    map: f => node(left.map(f), f(value), right.map(f)),
    fold: (mempty, mappend) =>
    mappend(mappend(mappend(mempty, left.fold(mempty, mappend)), value), right.fold(mempty, mappend))
  });
 
  var leaf = value => ({ 
    map: f => leaf(f(value)),
    fold: (acc, mappend) => mappend(acc, value)
  });

symbolically the fold equation is for a tree

fold(leaf(a)) =  Ø ⊕ a  
fold(node(l,x,r)) = ⟨ fold(r) ⊕ (x) ⊕ fold(r)⟩

What this means is

1. for leafs we get a type m of the monoid .for example [2 ] if leaf (2) .
2. And for a node we get the concatenation of left fold then we append the value and then we fold and append the right side. for example [1] .concat([2]).concate([3]) if node ( leaf(1), 2, leaf(3))

traversing the nodes and accumulating nodes into an array.Different order of concat give different algorithms of traversal

If we fold any structure with the array monoid ([], concat)

var content = self.fold([],(acc,e)=>acc.concat( e ))

then we get an array and we can create an extension method to attach an iterator on the foldable. With the defintion below we can get an iterator on the fly if we have defined fold

Object.prototype.getIterator = function () {
    var self = this;
    return {
      *[Symbol.iterator]() {
        {
          var content = self.fold([],(acc,e)=>acc.concat( e ) )
          for (var element of content) yield element;
        }
      }
    }
  }

Lets Fold Something more Composite

Lets say we have defined a compose operation that allows for the composition of foldables

var composeF = FG => ({
 unComp: FG,
 map: fab => composeF(FG.map(x => x.map(fab))),
 traverse: (TyperRep, f) => FG.traverse(TyperRep, x => x.traverse(TyperRep, f)),
});

then its possible to get an iterator of an Array of trees or a tree of arrays without adding anything new. Take a look at the following example:

Functional Programming in Javascript with Categories

functional programming in Javascript in Amazon

References:

• Applicative Programming with Effects, by Conor McBride and Ross Paterson, online at http://www.soi.city.ac.uk/~ross/papers/Applicative.html.
• The Essence of the Iterator Pattern, by Jeremy Gibbons and Bruno Oliveira, in Mathematically-Structured Functional Programming, 2006, and online at http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/#iterator.