Infinite Data structures in C#

TL;DR. Looking at the dual infinite codata structures, we will create a structure like this :

var stream = (1, (2, (3, (4, ...))));

because we want to generate something infinite we will use (co)recursion to construct it like this :

var StreamRec= n => (n, StreamRec(n + 1));
//but StreamRec(0) is an infinite recursion
 
                                                                                                       
                                              run this: .NetFiddle
                                         wikipedia:See corecursion

so we use laziness

var StreamRec=  = n => (n, ()=> StreamRec(n + 1));
//now StreamRec(0) is ok we get the next in sequence with 
StreamRec(0).Item2().Item2().Item2().Item2() ...
                                                run this: .NetFiddle

Codata Structures

Data structures like Lists, are the favorite data structure of programmers in any programming language. There are also the Opposite/Dual structures, that are not that well known. Usually they are infinite, and not that intuitive. Structures like Observables in Reactive extensions that have gained some traction finally. Lets see some basic ideas around co-data structures.

we will start from our default data structures.We all love the list. List’s Recursive definition is pretty linear :

A list is either an element or a conacatenation of an element and a list

in the above sentence if we replace the word element with a, the either with +, and the concat with * we get the algebraic definition :

List a = a + a *(List a)

if you see closer you will see the plus sign +. This is the logical or also known as Either. The + signifies the fact, that we can always terminate a list by taking [either] a plain a as our last element.

if we remove this option we can get something like this :

Stream a =  a * (Stream a)

[this * is the dual of the + above. Its a product structure that signifies something equivalent to logical And]

A structure can only be an a and a new Stream of a’s. There is no end in this structure. Its like [actually its the same] a recursive function that does not have a terminating condition. Stack-overflow.

Lets see an example of something called Co-free comonad that displays this property. [the Stream data structure above is actually isomorphic to the Cofree of the Identity functor thats why i mentioned it]

It looks like the stream above :

Cofree(F,a) = (a, F(Cofree(F,a)))

an example instance of a cofree-comonad would be this

 comonad = coFree(2, Id(coFree(2, ...)));

What this is saying is: “a cofree is a product of an a and a container (functor) of a cofree” for example if we take as F the identity “object” Id=a=>({a:a})(the simplest container) and as carrier type the integers, we could write an example instance of the associated cofree comonad:

new CofreeF (1, new IdentiyF (new CofreeF(1, new IdentiyF (...));

the thing is that we have to always provide as a second argument something. So this actually does not terminate. Ever. So we possibly cannot even construct it. Well we can use recursion.

this looks too complex you can run the simpler version run this: .NetFiddle

or play with the complex version in this Fiddle . Just be prepared for an exception of stackoverflow.

Laziness

now we will use the lazy operation ()=>_ to delay the execution of the whole recursion:

it’s the same, but it does execute lazily. Only when we ask for a value.

we can get the numbers in the sequence if we use next():

var t = stream.Next().Next().Next() ;

If you reached here congrats. here a recursive cat for you.

Functors

But there is more. In the example above in order to replace it with the identity functor this is a cofree comonad that has a map function that makes it a Functor.

IComonadF<T1> Map<T1>(Func<T, T1> f) =>
                       new CofreeF(f(A), Cof.Map(x => x.Map(f)));
                                          
                                             run this: .NetFiddle

In order to implement map and since it’s a recursive product type, we will return the first element mapped and then we will pass the function to the F(_) functor inside that is the second argument and let it recursively map its children

you can see the running script here Lazy Comonad Stream

we can now write things like :

var t = stream.Next().Map(x => x * 2).Next().Next().Map(x => x * 2);

Infinite Data with IEnumerable and yield

Yield is at its most powerful as a way of consuming data that might never end. Notice that, because this is done lazily, the absolute least amount of work will be done by the CPU to accomplish this task. Obviously, this will start to fail as the number becomes too large to be handled by a long.

if you happen to be interested in Javascript, you can find the Js version of this article below :

A slightly complex Guide to understanding javascript (ES6) generators

Bellow is a Coupon code for the course until 16/02/2020.

Master Functional Programming in C#