Stream /Array Isomorphism and natural transformations for javascript

I want to display a practical example of isomorphism, between structures in practice. If we look an example of the Cofree Maybe(that is applying the cofree to the maybe functor) [you can see more about Cofree here ]:

var cofree = coFree(2, some(coFree(3, some(coFree(4, none())))));

look very similar with the array

var list= [2, 3, 4] ;

so there should be two transformations that will move from one structure to the other:

isomorphism between two data structures

if we mange to implement those two functions then we can say that we have an isomorphism.

Cofree ToList

coFree(2, some(coFree(3, some(coFree(4, none())))))  --->  [2, 3, 4]

In order to create the toList function. We will first create a fold a.k.a reduce function for coFree that will go around the nodes and apply a monoid concat action that will accumulate the result. Because Cofree is actually a tree structure that always has one node to the left its “relatively easy” to implement a fold to a list. Because its an algebraic structure.

In order to fold this a recursive product type, we first concat the a element to the accumulation [ 1.mappend(acc, a) ]then we push with map the fold to the inner cofree (cofreeInner) in order to add its childreen to the accumulation [2. cofreeInner.map(cf => cf.fold(acc, mappend))] this map will be inside the functor F [Id in this case] so we have to fold this also .Here is the fold of the identity functor [3. fold(acc, mappend)], and finally we have to fold those two parts one of the cofree [ //4.concat everything]

var CoF = (a, cofreeInner) => ({
  a: a,
  cofreeInner: cofreeInner,
fold: (acc, mappend) =>
  mappend(                              //4.concat everything 
   mappend(acc, a),                     //1.concat a to accumulation
   cofreeInner.map(cf => cf.fold(acc, mappend))  //2.recursive fold
  
  .fold(acc, mappend)                        //3.folds the functor
            )                         
});

[this propably is too complex if you first seeing the concept of map and fold so you can either try to implement the fold for an array then play around with the fold of a tree here and then come back here . CofreeMaybe is a tree]

and we can implement the toList with the help of fold for the Array monoid ([],conact)

toList:()=>CoFree(a,cofreeInner).fold ([],(acc, i) => acc.concat(i))

List toCofree

[2, 3, 4] --->  coFree(2, some(coFree(3, some(coFree(4, none())))))

the other way around is easier we can create an array extension that will recursively build the cofree and then as a terminal case use the none to finalize the structure;

Array.prototype.toCofree = function (f) {
// l is the list 
var g = l => l.length == 0 ? none() : CoFree(l.shift(), f(g(l)));
return g(this);
}

now that we have both ways of transformation we can chech that this works by verifing that both operations negate its other in any order :

[2, 3, 4].toCofree(IdF).toList()===[2, 3, 4]
 
   
 var cofree = CoFree(2,IdF(CoFree(3,IdF(CoFree(4,none())))));
cofree.toList().toCofree(IdF) === cofree

Natural Transformation

If we want to say that the structures are equal up to natural isomorphism, we should also make sure that the map works properly after transformations. This means that this diagram commutes. Both the Red and blue paths give the same result.

Natural Transformation between Cofree and List

Now we could go and try to test if the naturality condition holds by testing that:

var cofree = coFree(2, some(coFree(3, some(coFree(4, none())))));
var f = s=>s * 4;
//those two should be equal for any cofree and f
var transformCofreeToArrayAfterMap = cofree.map(f).toList();
var mapCofreeAndThenTransformToList = cofree.toList().map(f);

Also, the opposite must hold. Since we want to be naturally isomorphic. This means both ways of transformation must hold.

var list  = [2, 3, 4];
//those two should be equal
var transformToCofreeAfterArrayMap =list.map(s =>s* 4)
.toCofree(some);
var mapArrayAfterTransformToCofree = list.toCofree(some)
.map(s => s * 4);
                                                
                                              Run this: Js Fiddle

For us testing just the data structures and making sure that the map implementation is following functor laws we can assume that the naturality conditions hold.

Newsletter