introduction

before reaching the catharsis in the “more linq with system.interactive” series over here, i wanted to ensure a solid understanding of the essence of linq in my reader base. often people forget the true essence of a technology due to the large number of auxiliary frameworks and extensions that are being provided. or worse, sometimes a sense for the essence never materialized.

searching for essence is nothing other than a “group by” operation, partitioning the world in fundamentals and derived portions. one succeeds in this mission if the former group is much smaller than the latter. in this post, we’ll try to reach that point for the ienumerable<t> and iobservable<t> linq implementations, illustrating both are fundamentally similar (and dare i say, dual?). you can already guess much of the essence lies in the concept of monads . by the end of the post, we’ll have distilled the core of linq, which i refer to as minlinq since small is beautiful .

interfaces are overrated?

while loved by object-oriented practitioners, interfaces are essentially nothing but records of functions . and functions, as we all know, are the fundamental pillars of functional programming languages. this trivial observation is illustrated below. i’ll leave it to the reader to think about various implications of the use of a (covariant) irecord representation for objects:

class program
{
    static void main()
    {
        for (var c = new counter(); c.get() < 10; c.inc(1))
            console.writeline(c.get());
    }
}

interface irecord<out t1, out t2>
{
    t1 first { get; }
    t2 second { get; }
}

class counter : irecord<func<int>, action<int>>
{
    // data
    private int _value;

    // code - explicit implementation to hide first, second
    func<int> irecord<func<int>, action<int>>.first { get { return () => _value; } }
    action<int> irecord<func<int>, action<int>>.second { get { return i => _value += i; } }

    // code - friendly "interface"
    public func<int> get { get { return ((irecord<func<int>, action<int>>)this).first; } }
    public action<int> inc { get { return ((irecord<func<int>, action<int>>)this).second; } }
}

why do we care? well, it turns out that ienumerable<t> and iobservable<t> tend to obscure the true meaning of the objects a bit by having many different methods to facilitate the task of enumeration and observation, respectively. the source of this apparent bloating is irrelevant (and in fact follows design guidelines of an object-oriented inspired framework); what matters more is to see how the two mentioned interfaces can be boiled down to their essence.

minimalistic as we are, we’re going to drop the notion of error cases that manifest themselves through movenext throwing an exception and onerror getting called, respectively on ienumerator<t> and iobserver<t>. for similar reasons of simplification, we’ll also not concern ourselves with the disposal of enumerators or subscriptions. the resulting picture looks as follows:

to consolidate things a bit further, we’ll collapse movenext/current on the left, and onnext/oncompleted on the right. how so? well, either getting or receiving the next element can provide a value or a termination signal. this is nothing but a pair of an optional value and a boolean. turns out we have such a thing in the framework, called nullable<t> but since one can’t nest those guys or use them on reference types, it doesn’t help much. instead, we’ll represent the presence or absence of a value using an option<t> type:

public abstract class option<t>
{
    public abstract bool hasvalue { get; }
    public abstract t value { get; }

    public sealed class none : option<t>
    {
        public override bool hasvalue
        {
            get { return false; }
        }

        public override t value
        {
            get { throw new invalidoperationexception(); }
        }

        public override string tostring()
        {
            return "none<" + typeof(t).name + ">()";
        }
    }

    public sealed class some : option<t>
    {
        private t _value;

        public some(t value)
        {
            _value = value;
        }

        public override bool hasvalue
        {
            get { return true; }
        }

        public override t value
        {
            get { return _value; }
        }

        public override string tostring()
        {
            return "some<" + typeof(t).name + ">(" + (_value == null ? "null" : _value.tostring()) + ")";
        }
    }
}

the subtypes none and some are optional though convenient, hence i’ll leave them in. with this, ienumerator<t> would boil down to an interface with a single method retrieving an option<t>. when it returns a some object, there was a next element and we got it; when it returns none, we’ve reached the end of the enumeration. similar for iobserver<t>, onnext and oncompleted are merged into a single method receiving an option<t>. interfaces with a single method have a name: they’re delegates. so both those types can be abbreviated to:

iobserver<t>  –>  action<option<t>>
ienumerator<t>  –>  func<option<t>>

a quick recap: an observer is something you can give a value or tell it has reached the end of the observable object, hence it takes in an option<t>; an enumerator is something you can get a value from but it can also signal the end of the enumerable object, hence it produces an option<t>. in a more functional notation, one could write:

option<t> –> ()
() –> option<t>

here the arrow indicates “goes to”, just as in lambda expressions, with the argument on the left and the return type on the right. all that has happened is reverting the arrows to go from an observer to an enumerator and vice versa. that’s the essence of dualization .

but we’re not done yet. look one level up at the ienumerable<t> and iobserver<t> interfaces. those are single-method ones too, hence we can play the same trick as we did before. the ienumerable<t> interface’s single method returns an ienumerator<t>, which we already collapsed into a simple function above. and in a dual manner, iobservable<t>’s single method takes in an iobserver<t>, which we also collapsed above. the yields the following result:

iobservable<t>  –>  action<action<option<t>>>
ienumerable<t>  –>  func<func<option<t>>> 

if that isn’t a simplification, i don’t know what would be. an observable is nothing other than an action taking in an action taking in an observed value, while an enumerable is nothing other than a function returning a function returning a yielded value. or, in concise functional notation:

(option<t> –> ()) –> ()
() –> (() –> option<t>)

again, to go from one world to the other, it suffices to reverse the arrows to reach the dual form. in summary, have a look at the following figure:

flat functions – fenumerable and fobservable

since we’ve flattened imperative interfaces into flat functions we’re going to provide several operators over those, we need to have a name for the type to stick those items in. though we’re not going to make things purely functional on the inside (as we’ll rely on side-effects to implement various operators), i still like to call it function-style enumerable and observable, hence the names fenumerable and fobservable (not meant to be pronounceable), where f stands for function as opposed to i for interface. in addition, ex additions will materialize to realize some layering as discussed below. the result, including fenumerableex2 that’s left as an exercise, is shown below:

five essential operators, or maybe even less

to continue on our merry way towards the essence of linq, we’ll be providing five essential operators as the building blocks to construct most other operators out of. needless to say so, those operators will use the above flat function “interfaces” to do their work on. let’s start with a couple of easy ones: empty and return.

empty

the empty operator is very straightforward and never deals with option<t>.some values, just signaling an option<t>.none immediately to signal completion. hence the produced collection is empty. how do we realize this operator in the enumerable and observable case? not surprisingly, the implementation is straightforward in both cases:

public static class fenumerable
{
    public static func<func<option<t>>> empty<t>()
    {
        return () => () => new option<t>.none();
    }

first, the fenumerable one. all it does is simply returning a function that returns an end-of-sequence none signal in return to getting called. notice the two levels of nesting needed to be conform with the signature. the outer function is the one retrieving the enumerator, while the inner is the equivalent to movenext and current. for absolute clarity:

one the fobservable side of things, we find a similar implementation shuffled around a little bit, as shown below:

    public static class fobservable
    {
        public static action<action<option<t>>> empty<t>()
        {
            return o => o(new option<t>.none());
        }

what used to be output now becomes input: the none constructor call no long appears in an output position but has moved to an input position. similar for the observer, indicated with o, which has moved to an input position. upon giving the observable object (the whole thing) an observer (o), the latter gets simply called with a none object indicating the end of the sequence. the inner call is equivalent to oncompleted, while the whole lambda expression is equivalent to subscribe.

the careful reader may spot an apparent difference in the multiplicity of the involved operations. where one enumerable can be used to get multiple enumerators, it seems that one observable cannot be used with multiple observers. this is only how it looks, as duality comes to the rescue to explain this again. the statement for enumerables goes as follows: “ multiple calls to getenumerator each return one ienumerator”. the dual of that becomes “a single call to subscribe can take in multiple iobservers”. while that’s not exactly the case in the real iobserver land, where you either wrap all of your observers in a single iobserver to achieve this effect, or make multiple calls to subscribe (assuming – and that’s where the minlinq approach differs slightly – a call to subscribe doesn’t block), it’s incredibly true in fobservable. how so? well, one can combine delegates using the + operator to achieve the effect of subscribing multiple observers at the same time:

action<option<int>> observer1 = x => console.writeline("1 <- " + x);
action<option<int>> observer2 = x => console.writeline("2 <- " + x);

var xs = fobservable.return(1);
xs(observer1 + observer2);

the above will print some(1) and none() twice, since both observers are getting it (in invocation order, coinciding with lexical order).

return

the previous sample brings us seamlessly to the next operator: return, which realizes a singleton enumerable or observable collection. though this one seems easy as well, it’s getting a bit more complex in the enumerable case as we need to maintain state across calls to “movenext”. moreover, we need to do so on a per-enumerator basis as they all need to have their own view on the sequence. in our observable case, for the reasons mentioned above, things are slightly simpler as we can just “fire and forget” all data upon receiving a call to subscribe. (exercise: how would you make subscribe asynchronous with respect to the sequence producing its values? when is this useful and when is it harmful?)

let’s first look at the return operator realization in fenumerable:

public static func<func<option<t>>> return<t>(t value)
{
    return () =>
    {
        int i = 0;
        return () =>
            i++ == 0
            ? (option<t>)new option<t>.some(value)
            : (option<t>)new option<t>.none();
    };
} 

the state local to the “enumerator block” contains a counter that keeps track of the number of movenext calls that have been made. the first time, we return a some(value) object, and the second (and subsequent) time(s) we answer with none. notice this has the implicit contract of considering a none value as a terminal in the grammar. if you want to enforce this policy, an exception could be raised if i reaches 2.

in the fobservable world, things are quite easy. upon a subscription call, we signal a some and none message on the onnext function, like this:

public static action<action<option<t>>> return<t>(t value)
{
    return o =>
    {
        o(new option<t>.some(value));
        o(new option<t>.none());
    };
}

bind

why says return and knows about monads immediately thinks about bind (>>= in haskell). the bind operator, known as selectmany in linq, provides an essential combinator allowing to compose objects in the monad. in our case, those monads are ienumerable<t> and iobservable<t>. in a previous episode of my more linq series, i’ve explained the basic idea of monadic composition a bit further, as summarized in the figure below:

in the above, m<.> has to be substituted for either func<func<.>> or action<action<.>> to yield the signature for both fenumerable’s and fobservable’s bind operators. the implementation of the operator in the latter case is the more straightforward one of both:

public static action<action<option<r>>> bind<t, r>(this action<action<option<t>>> source, func<t, action<action<option<r>>>> selector)
{
    return o => source(x =>
    {
        if (x is option<t>.none)
        {
            o(new option<r>.none());
        }
        else
        {
            selector(x.value)(y =>
            {
                if (y is option<r>.some)
                    o(y);
            });
        }
    });
}

here, upon subscribing to an observable using observer “o”, the operator itself subscribes to the source observable that was fed in to the function. it does so by providing an observer that takes in the received element as “x”. inside the observer’s body, which gets called for every element raised by the source, “x” is analyzed to see whether or not the source has terminated. if not, bind does its combining work by calling the selector function for the received element, getting back a new observable source “f(x.value)”. the goal of bind is to surface the values raised on this source to the surface of the operator call. hence, we subscribe to this computed source “f(x.value)” by providing an observer that takes in the received value as “y” and raises that to the surface by calling “o” (the external observer). again we assume none is terminating the sequence, which could be enforced by keeping a bit of state (left as an exercise). we’ll see examples of operator usage later on.

(exercise: what if we want the subscribe method to return immediately, running the bind in the background. how would you do so?)

in the fenumerable case, things get more complex as we need to keep track of where we are in the source and projected sequences across different calls to “movenext”. while we could realize this using a state machine (just like iterators would do), i’ve taken on the challenge to write a state-keeping set of loops by hand. it may well be optimized or tweaked but it seems to do its job. important situations to keep in mind include encountering empty inner sequences (signaled by none), requiring us to loop till we eventually find an object to yield . it’s also important to properly return a option<r>.none object when we reach the end of the outer source. one of the most essential parts of the code below is the storage of state outside the inner lambda, hence keeping per-enumerator state. besides cursors into the outer and current inner sequences, we also keep the inner enumerator (recall the signature corresponding to ienumerator<t>) in “innere”.

public static func<func<option<r>>> bind<t, r>(this func<func<option<t>>> source, func<t, func<func<option<r>>>> f)
{
    return () =>
    {
        var e = source();

        option<t> lastouter = new option<t>.none();
        option<r> lastinner = new option<r>.none();
        func<option<r>> innere = null;

        return () =>
        {
            do
            {
                while (lastinner is option<r>.none)
                {
                    lastouter = e();

                    if (lastouter is option<t>.none)
                    {
                        return new option<r>.none();
                    }
                    else
                    {
                        innere = f(lastouter.value)();
                    }

                    lastinner = innere();
                    if (lastinner is option<r>.some)
                    {
                        return lastinner;
                    }
                }

                lastinner = innere();
            } while (lastinner is option<r>.none);

            return lastinner;
        };
    };
}

the reader is invited to make sense of the above at his or her own pace, keeping in mind the regular linq to objects implementation is the following much more comprehensible code:

public static ienumerable<r> selectmany<t, r>(this ienumerable<t> source, func<t, ienumerable<r>> f)
{
    foreach (var item in source)
        foreach (var result in f(item))
            yield return result;
}

the interesting thing about the selectmany implementation is that the types in the signature exactly tell you what to do: the main operation on an ienumerable is to enumerate using foreach. the only parameter you can do that on is source, but you can’t yield those elements as the output expects elements of type r and we got elements of type t. however, the function “f” accepts a t and produces an ienumerable<r>, so if we call that one an enumerate the results, we got what we can yield. simple.

this operator is essential to linq (and monads) in that it allows many other operators to be written in terms of it. where and select and two that pop to mind immediately, and we’ll come to those when we talk about fenumerableex (and fobservable) later.

ana

an anamorphism is the fancy word for an operator that produces an m<t> out of something outside m<.>, by use of unfolding. given some seed value and an iterator function, one can produce a potentially infinite sequence of elements. implementation of this operator is straightforward in both cases, again with the enumerable case requiring some state:

public static func<func<option<t>>> ana<t>(t seed, func<t, bool> condition, func<t, t> next)
{
    return () =>
    {
        option<t> value = new option<t>.none();
        return () =>
            condition((value = new option<t>.some(
                value is option<t>.none
                ? seed
                : next(value.value))).value)
            ? (option<t>)new option<t>.some(value.value)
            : (option<t>)new option<t>.none();
    };
}

for fun and giggles i wrote this one using conditional operator expressions only, with an assignment side-effect nicely interwoven. it’s left to the reader to write it in a more imperative style. again, we’re assuming the enumerator function is not called after a none object has been received. the basic principle of the operator is clear and implementation would look like this in regular c# with iterators:

public static ienumerable<t> ana<t>(t seed, func<t, bool> condition, func<t, t> next)
{
    for (t t = seed; condition(t); t = next(t))
        yield return t;
}

on the fobservable side, things are simpler again (the main reason being that fenumerable is hard because of its lazy nature and because we can’t use iterators):

public static action<action<option<t>>> ana<t>(t seed, func<t, bool> condition, func<t, t> next)
{
    return o =>
    {
        for (t t = seed; condition(t); t = next(t))
            o(new option<t>.some(t));
        o(new option<t>.none());
    };
}

again, the reader is invited to think about what i’d take to have this sequence getting generated on the background, as opposed to blocking the caller.

as an additional exercise, can you rewrite return and empty in terms of ana, therefore making those two operators no longer primitives? doing so will bring down the total of essentials to three: ana, cata and bind:

cata

the opposite of an anamorphism is a catamorphism, also known as aggregate in linq. its goal is to fold a m<t> into something outside m<.>, e.g. computing the sum of a sequence of numbers. since this is a greedy operation, we can do it on the spot for both the fenumerable and fobservable cases as shown below:

public static r cata<t, r>(this func<func<option<t>>> source, r seed, func<r, t, r> f)
{
    var e = source();

    option<t>.some value;
    r result = seed;
    while ((value = e() as option<t>.some) != null)
    {
        result = f(result, value.value);
    }

    return result;
}

first for the enumerable case, we simply run till we get a none object, continuously calling the aggregation function, starting with the seed value. in the observable case, things are equally simple:

public static r cata<t, r>(this action<action<option<t>>> source, r seed, func<r, t, r> f)
{
    r result = seed;

    bool end = false;
    source(x =>
    {
        if (x is option<t>.some && !end)
            result = f(result, x.value);
        else
            end = true; // or break using exception
    });

    return result;
}

this time we have to hook up an observer with the source and analyze what we got back. notice the code above shows one approach to break out of or immunize an observer after a none message has been received. notice though that if all constructor functions can be trusted (which is not the case with an action of func), such protections wouldn’t be required as we’re defining a closed world of constructors and combinators. if the former group never emits sequences that don’t follow the described protocol and the latter never combines existing sequences into an invalid one (i.e. preserving the protocol properties), it shouldn’t be possible to fall off a cliff.

bridging the brave new world with the old-school one

before getting into more operators layered on top of the essential ones provided above, we should spend a few minutes looking at ways to convert back and forth between the new functionally inspired “flat” world and the familiar interface-centric “bombastic” world of linq. in particular, can we establish the following conversions?

• ienumerable<t> to func<func<option<t>>>
• func<func<option<t>>> to ienumerable<t>
• iobservable<t> to action<action<option<t>>>
• action<action<option<t>>> to iobservable<t>

obviously the answer is we can. let’s focus on the first two as a starter. it’s clear that in order to go from an ienumerable<t> to our new world of fenumerable we should iterate the specified sequence. we should do so in a lazy manner such that upon every call to fenumerable’s inner function (playing the enumerator’s role) we fetch an element out of the source ienumerator<t>, but no earlier. in other words, we have to keep the iteration state which is represented by an ienumerator<t> as the local state to the enumerator function:

public static func<func<option<t>>> asfenumerable<t>(this ienumerable<t> source)
{
    return () =>
    {
        var e = source.getenumerator();
        return () => e.movenext()
            ? (option<t>)new option<t>.some(e.current)
            : (option<t>)new option<t>.none();
    };
}

this should be fairly straightforward code to grasp, ensuring we properly terminate a (finite) sequence with a none object to signal completion. the opposite operation is easy as well, now calling a fenumerable’s enumerator function, providing results to the caller in a lazy fashion by means of a typical c# iterator:

public static ienumerable<t> asenumerable<t>(this func<func<option<t>>> source)
{
    var e = source();
    option<t>.some value;
    while ((value = e() as option<t>.some) != null)
    {
        yield return value.value;
    }
}

as soon as we encounter a none object, we’ll break out of the loop causing the consuming enumerator to terminate. using the operators above, we can readily verify the back and forth conversions easily:

// ienumerable -> fenumerable
var xs = enumerable.range(0, 10).asfenumerable();
{
    var xse = xs();
    option<int> x;
    while ((x = xse() as option<int>.some) != null)
        console.writeline(x.value);
}

// fenumerable -> ienumerable
var ys = xs.asenumerable();
{
    foreach (var y in ys)
        console.writeline(y);
}

this is very convenient as we’ll be able to treat arrays and other enumerable collections as fenumerable functions in a blink of the eye. now we can start to mix and match typical linq to objects operators with our own academic playground.

on to the dual world, we can also provide conversions for iobservable<t> to fobservable<t> back and forth. both are relatively easy to realize as well but lets starts with old to new:

    public static iobservable<t> asobservable<t>(this action<action<option<t>>> source)
    {
        return observable.create<t>(o =>
        {
            source(x =>
            {
                if (x is option<t>.some)
                    o.onnext(x.value);
                else
                    o.oncompleted();
            });
            return () => { };
        });
    }

here i’m using rx’s observable.create operator to simplify the creation of an iobservable<t>, passing in an observer’s code body. lambda parameter “o” is an iobserver<t>, so all we got to do is subscribe to our source (by means of just calling it, passing in a fobserver function) and forward received objects “x” to the external observer. as we don’t have a notion to run asynchronous in our little world, we simply return the no-op action delegate from the observer function. since all execution happens synchronously upon a subscribe call to the produced iobservable<t>, there’s little for us to do in a reaction to an unsubscribe invocation.

in the other direction, things are even simpler. we simply use an rx extension method for iobservable<t> to subscribe given an onnext and oncompleted delegate:

public static action<action<option<t>>> asfobservable<t>(this iobservable<t> source)
{
    return o =>
    {
        source.subscribe(x => o(new option<t>.some(x)), () => o(new option<t>.none()));
    };
}

again we can test this easily, this time using observable.range. since that one runs asynchronously, we have to do a bit of synchronization to see the results printed nicely:

// iobservable -> fobservable
var evt = new manualresetevent(false);
var xs = observable.range(0, 10).asfobservable();
{
    xs(x =>
    {
        if (x is option<int>.some)
            console.writeline(x.value);
        else
            evt.set();
    });
}
evt.waitone();

// fobservable -> iobservable
var ys = xs.asobservable();
{
    // we got this one synchronous inside.
    ys.subscribe(console.writeline);
}

the result of all this plumbing is summarized in the following diagram. the direct conversion between a fenumerable and fobservable (and vice versa) is left to the reader as an interesting exercise:

where and select for monadic dummies

while we leave the implementation of operators like snoc (cons in reverse, to construct sequences out of a single element and a sequence) and concat (concatenating arbitrary sequences to one another) to the reader, we should focus on a few operators that can be realized using the essential building blocks provided before. in particular, we’ll implement where and select in terms of bind, empty and return.

recall what bind does: it combines a sequence with sequences generated from a function call, collecting the elements all sequences that result from those function calls. in a concrete sample: given a list of products and a way to get all the suppliers for each product we can return a sequence of all suppliers across all products. or with function arrows: ie<product> –> (product –> ie<supplier>) –> ie<supplier>. this is exactly the signature of bind or selectmany.

how can we use this to create a filter like where? the answer is pretty simple, by controlling the “selector” function passed to bind and make it analyze each element that’s passed in, deciding whether or not to return it to bind. the “whether or not” part can be realized using a conditional either returning return(element) or empty(). and there we got our filtering logic:

public static func<func<option<t>>> where<t>(this func<func<option<t>>> source, func<t, bool> filter)
{
    return source.bind(t => filter(t) ? fenumerable.return(t) : fenumerable.empty<t>());
}

a picture is worth a thousand words, so let’s have a look at the where operator realization in terms of bind:

and guess what, the fobservable implementation can be derived by mechanical translation from the one for fenumerable:

public static action<action<option<t>>> where<t>(this action<action<option<t>>> source, func<t, bool> filter)
{
    return source.bind(t => filter(t) ? fobservable.return(t) : fobservable.empty<t>());
}

in fact, the code is exactly the same with fenumerable replaced by fobservable. if we’d have typedefs for the function signatures or static extension methods on a delegate type, we’d actually see both pieces of code being the same of the following “template”:

    public static m<t> where<t>(this m<t> source, func<t, bool> filter)
    {
        return source.bind(t => filter(t) ? m<t>.return(t) : m<t>.empty());
    }
 

such an m<t> abstraction would be realized as a type constructor in haskell and the packaging of both return and bind on m<t> would be realized by means of a type class that looks as follows:

class monad m where
return :: a –> m a
(>>=)  :: m a –> (a –> m b) –> m b

the second function is haskell’s infix operator for bind. more information ca be found at the following locations:

• http://www.haskell.org/haskellwiki/monad
• http://www.haskell.org/tutorial/monads.html
• http://en.wikibooks.org/wiki/haskell/understanding_monads

how can we realize select using bind and return as well? the answer is again very straightforward: this time we simply apply the projection function to the object passed to the bind selector function and wrap the result using return. here’s the code for both worlds, again ready to be abstracted to m<t>:

public static func<func<option<r>>> select<t, r>(this func<func<option<t>>> source, func<t, r> selector)
{
    return source.bind(t => fenumerable.return(selector(t)));
}

public static action<action<option<r>>> select<t, r>(this action<action<option<t>>> source, func<t, r> selector)
{
    return source.bind(t => fobservable.return(selector(t)));
}

again a picture will make the above more clear:

with those extension methods in place, we can actually start writing linq expressions against fenumerable and fobservable (function!) objects. that’s right: now you got a delegate you can dot into, thanks to the magic of extension methods. but using convenient linq syntax, we don’t even have to see any of that:

var res = (from x in enumerable.range(0, 10).asfenumerable()
           where x % 2 == 0
           select x + 1).asenumerable();

foreach (var x in res)
    console.writeline(x);

notice how we go back and forth between classic ienumerable<t> and our fenumerable implementation? but the key to see here is that our where and select operators are getting called. the result obviously prints 1, 3, 5, 7, 9 and to convince ourselves or calls happening to our methods, we’ll have a look in the debugger:

i hope this suffices to convince the reader we got query expression syntax working around our minlinq implementation. it’s left to the reader to decipher the exact call stack we’re observing above. the same exercise can be repeated for the fobservable case, using the following equivalent code:

var res = (from x in observable.range(0, 10).asfobservable()
           where x % 2 == 0
           select x + 1).asobservable();

res.subscribe(console.writeline);
console.readline(); // stuff happening on the background; don't exit yet

since bind is none other than selectmany in disguise, we could rename it as such to enable it for use in linq as well, triggered by query expressions having multiple from clauses. in fact, to fully enable query expressions of that form, you’ll need a slight tweak to the selectmany signature, as follows (same for the observable case of course):

public static func<func<option<r>>> selectmany<t, c, r>(this func<func<option<t>>> source, func<t, func<func<option<c>>>> selector, func<t, c, r> result)
{
    // left as an exercise.
}

if you implement this one correctly, you will be able to run a query of the following shape:

var res = (from x in enumerable.range(1, 5).asfenumerable()
           from y in enumerable.range(1, x).asfenumerable()
           select new string((char)('a' + x - 1), y)).asenumerable();

foreach (var item in res)
    console.writeline(item);

this will print the following output:

a
b
bb
c
cc
ccc
d
dd
ddd
dddd
e
ee
eee
eeee
eeeee

finally, just to go nuts with some back-and-forth transitioning between all worlds (as shown in our diagram before), an all-inclusive sample mixing all sorts of execution:

var res = (from y in
               (from x in enumerable.range(0, 20).asfenumerable()
                where x % 2 == 0
                select x + 1).asenumerable()
               .toobservable() // rx
               .asfobservable()
           where y % 3 == 0
           select y * 2)
          .asobservable()
          .toenumerable(); // rx

foreach (var item in res)
    console.writeline(item);

the interested reader is invited to create short-circuiting operators to provide a direct path for .asenumerable().toobservable().asfobservable() and .asobservable().toenumerable().asfenumerable(). refer back to the diagram to see where those operators’ corresponding arrows occur.

fueling range and sum with ana and cata

to conclude this post, let’s also have a look at how to derive constructor and aggregator operators from our ana and cata primitives. as a sequence constructor we’ll consider range and for the aggregator we’ll consider sum. let’s start with range in terms if ana:

public static func<func<option<int>>> range(int from, int length)
{
    return fenumerable.ana<int>(from, x => x < from + length, x => x + 1);
}

and (again exactly the same code thanks to the shared primitives)

public static action<action<option<int>>> range(int from, int length)
{
    return fobservable.ana<int>(from, x => x < from + length, x => x + 1);
}

now we can get rid of the asfenumerable() use in our samples when creating a range and construct our range sequence immediately in our world (similar example for fobservable of course):

    var res = (from x in fenumerableex.range(0, 10)
               where x % 2 == 0
               select x + 1).asenumerable();

    foreach (var x in res)
        console.writeline(x);

as an exercise, also abstract the asenumerable call followed by foreach into a run method , as seen in system.interactive, so that you can write the code below. implement this operator in terms of cata (!):

(from x in fenumerableex.range(0, 10)
 where x % 2 == 0
 select x + 1).run(
     console.writeline
);

(question: could you benefit from such an operator in fobservable as well?)

for the sum realization we can use cata:

    public static int sum(this func<func<option<int>>> source)
    {
        return source.cata(0, (sum, x) => sum + x);
    }

and

public static int sum(this action<action<option<int>>> source)
{
    return source.cata(0, (sum, x) => sum + x);
}

the following example illustrates how to sum 1 to 10 using range and sum:

console.writeline(fenumerableex.range(1, 10).sum());
console.writeline(fobservableex.range(1, 10).sum());

both print 55 just fine.

implement more aggregation operators as found in the standard query operators. also think about how to implement those over nullable value types (e.g. sum with int?). could you reuse option<t> as an alternative to nullables? could you reuse monadic computation to carry out nullable arithmetic (tip: the maybe monad )? a few aggregates that some people don’t see as aggregates include all, any, first, last, elementat, and more. don’t forget to implement those either (most of them should be a one-liner making a single call to cata). as an additional caveat, the following implementation of average is inadequate (why?):

    public static double average(this func<func<option<int>>> source)
    {
        return (double)source.sum() / source.count();
    }

conclusion

boiling down linq to its core essence can be fun and a great eye-opener to many users of the technology. while optimizations often mandate a lower degree of layering, it’s good to have an idea of the conceptual layering of various operators to see which ones are essential and which ones are not so much. if kids can build castles out of lego blocks, sure every self-respecting developer should be able to exploit the expressive power a few primitive building blocks to create great libraries and applications. choosing the right set of primitives can get you a long way in such a design, as illustrated in this post. readers who can’t get enough of essential primitives and the composition thereof are cordially invited to have a go at another crazy sunday post titled unlambda .net – with a big dose of c# 3.0 lambdas (and many others in that category).