New features: Monadic action operators, StreamT, and Iterable

[louthy]

Features:

• Monadic action operators
• New Iterable monad
• New StreamT monad-transformer
  • Support for recursive IO with zero space leaks
• Typed operators for |
• Atom rationalisation
• FoldOption
• Async helper
• IAsyncEnumerable LINQ extensions

Monadic action operators

The monadic action operator >> allow the chaining of two monadic actions together (like a regular bind operation), but we discard the result of the first.

A good example of why we want this is the LINQ discards that end up looking like BASIC:

public static Game<Unit> play =>
    from _0 in Display.askPlayerNames
    from _1 in enterPlayerNames
    from _2 in Display.introduction
    from _3 in Deck.shuffle
    from _4 in playHands
    select unit;

We are always discarding the result because each operation is a side-effecting IO and/or state operation.

Instead, we can now use the monadic action operator:

public static Game<Unit> play =>
    Display.askPlayerNames >>
    enterPlayerNames       >>
    Display.introduction   >>
    Deck.shuffle           >>
    playHands;

Here's another example:

static Game<Unit> playHands =>
    from _   in initPlayers >>
                playHand >>
                Display.askPlayAgain
    from key in Console.readKey
    from __  in when(key.Key == ConsoleKey.Y, playHands)
    select unit;

In the above example you could just write:

static Game<Unit> playHands =>
    initPlayers >>
    playHand >>
    Display.askPlayAgain >>
    from key in Console.readKey
    from __  in when(key.Key == ConsoleKey.Y, playHands)
    select unit;

It's really down to taste. I like things to line up!

Because operators can't have generics, we can only combine operands where the types are all available. For example:

public static IO<A> operator >> (IO<A> lhs, IO<A> rhs) =>
    lhs.Bind(_ => rhs);

But, we can de-abstract the K versions:

public static IO<A> operator >> (IO<A> lhs, K<IO, A> rhs) =>
    lhs.Bind(_ => rhs);

And, also do quite a neat trick with Unit:

public static IO<A> operator >> (IO<A> lhs, IO<Unit> rhs) =>
    lhs.Bind(x => rhs.Map(_ => x));

That propagates the result from the first operation, runs the second (unit returning) operation, and then returns the first-result. This is actually incredibly useful, I find.

Because, it's not completely general case, there will be times when your types don't line up, but it's definitely useful enough, and can drastically reduce the amount of numbered-discards! I also realise some might not like the repurposing of the shift-operator, but I chose that because it's the same operator used for the same purpose in Haskell. Another option may have been to use &, which would be more flexible, but in my mind, less elegant. I'm happy to take soundings on this.

The CardGame sample has more examples.

New Iterable monad

The EnumerableM type that was a wrapper for IEnumerable (that enabled traits like foldable, traversable, etc.) is now Iterable. It's now more advanced than the simple wrapper that existed before. You can Add an item to an Iterable, or prepend an item with Cons and it won't force a re-evaluation of the lazy sequence, which I think is pretty cool. The same is true for concatenation.

Lots of the AsEnumerable have been renamed to AsIterable (I'll probably add AsEnumerable() back later (to return IEnumerable again). Just haven't gotten around to it yet, so watch out for compilation failures due to missing AsEnumerable.

The type is relatively young, but is already has lots of features that IEnumerble doesn't.

New StreamT monad-transformer

If lists are monads (Seq<A>, Lst<A>, Iterable<A>, etc.) then why can't we have list monad-transformers? Well, we can, and that's StreamT. For those that know ListT from Haskell, it's considered to be done wrong. It is formulated like this:

   K<M, Seq<A>>

So, the lifted monad wraps the collection. This has problems because it's not associative, which is one of the rules of monads. It also feels instinctively the wrong way around. Do we want a single effect that evaluates to a collection, or do we want a collection of effects? I'd argue a collection of effects is much more useful, if each entry in a collection can run an IO operation then we have streams.

So, we want something like this:

Seq<K<M, A>>

In reality, it's quite a bit more complicated than this (for boring reasons I won't go into here), but a Seq of effects is a good way to picture it.

It's easy to see how that leads to reactive event systems and the like.

Anyway, that's what StreamT is, it's ListT done right.

Here's a simple example of IO being lifted into StreamT:

StreamT<IO, long> naturals =>
    Range(0, long.MaxValue).AsStream<IO>();

static StreamT<IO, Unit> example =>
    from v in naturals
    where v % 10000 == 0
    from _ in writeLine($"{v:N0}")
    where false
    select unit;

So, naturals is an infinite lazy stream (well, up to long.MaxValue). The example computation iterates every item in naturals, but it uses the where clause to decide what to let through to the rest of the expression. So, where v % 10000 means we only let through every 10,000th value. We then call Console.writeLine to put that number to the screen and finally, we do where false which forces the continuation of the stream.

The output looks like this:

10,000
20,000
30,000
40,000
50,000
60,000
70,000
80,000
90,000
100,000
110,000
120,000
130,000
140,000
150,000
...

That where false might seem weird at first, but if it wasn't there, then we would exit the computation after the first item. false is essentially saying "don't let anything thorugh" and select is saying "we're done". So, if we never get to the select then we'll keep streaming the values (and running the writeLine side effect).

We can also lift IAsyncEnumerable collections into a StreamT (although you must have an IO monad at the base of the transformer stack -- it needs this to get the cancellation token).

static StreamT<IO, long> naturals =>
    naturalsEnum().AsStream<IO, long>();

static StreamT<IO, Unit> example =>
    from v in naturals
    from _ in writeLine($"{v:N0}")
    where false
    select unit;

static async IAsyncEnumerable<long> naturalsEnum()
{
    for (var i = 0L; i < long.MaxValue; i++)
    {
        yield return i;
        await Task.Delay(1000);
    }
}

We can also fold and yield the folded states as its own stream:

static StreamT<IO, int> naturals(int n) =>
    Range(0, n).AsStream<IO>();

static StreamT<IO, Unit> example(int n) =>
    from v in naturals(n).FoldUntil(0, (s, x) => s + x, (_, x) => x % 10 == 0)
    from _ in writeLine(v.ToString())
    where false
    select unit;

Here, FoldUntil will take each number in the stream and sum it. In its predicate it returns true every 10th item. We then write the state to the console. The output looks like so:

0
55
210
465
820
1275
1830
2485
3240
4095
..

Support for recursive IO with zero space leaks

I have run the first StreamT example (that printed every 10,00th entry forever) to the point that this has counted over 4 billion. The internal implementation is recursive, so normally we'd expect a stack-overflow, but for lifted IO there's a special trampoline in there that allows it to recurse forever (without space leaks either). What this means is we can use it for long lived event streams without worrying about memory leaks or stack-overflows.

To an extent I see StreamT as a much simpler pipes system. It doesn't have all of the features of pipes, but it is much, much easier to use.

To see more examples, there's a 'Streams' project in the Samples folder.

Typed operators for |

I've added lots of operators for | that keeps the .As() away when doing failure coalescing with the core types.

Atom rationalisation

I've simplified the Atom type:

• No more effects inside the Swap functions (so, no SwapEff, or the like).
• Swap doesn't return an Option any more. This was only needed for atoms with validators. Instead, if a validator fails then we just return the original unchanged item. You can still use the Changed event to see if an actual change has happened. This makes working with atoms a bit more elegant.
• New Prelude functions for using atoms with IO:
  • atomIO to construct an atom
  • swapIO to swap an item in an atom while in an IO monad
  • valueIO to access a snapshot of the Atom
  • writeIO to overwrite the value in the Atom (should be used with care as the update is not based on the previous value)

FoldOption

New FoldOption and FoldBackOption functions for the Foldable trait. These are like FoldUntil, but instead of a predicate function to test for the end of the fold, the folder function itself can return an Option. If None the fold ends with the latest state.

Async helper

• Async.await(Task<A>) - turns a Task into a synchronous process. This is a little bit like Task.Result but without the baggage. The idea here is that you'd use it where you're already in an IO operation, or something that is within its own asynchronous state, to pass a value to a method that doesn't accept Task.
• Async.fork(Func<A>, TimeSpan) and Async.fork(Func<Task<A>>, TimeSpan) - both return a ForkIO and allow for launching parallel effects that you can await later or cancel.

I see these as potential stop-gap functions for those moving from v4 to v5 where they might find an *Async variant of a method has disappeared (like MatchAsync, but can't at that point refactor everything). I'm still in two minds about this, but I'll leave them in for now.

IAsyncEnumerable LINQ extensions

The BCL doesn't support Select, SelectMany, Where, etc. for IAsyncEnumerable. Well, now we do. I've only done a handful so far, but it's the extensions that matter.

---

This discussion was created from the release New features: Monadic action operators, StreamT, and Iterable.