Layered monads

A layered monad is a computation that combines aspects of multiple monads. The paper uses asynchronous sequences as an example - such computation combines non-blocking execution of asynchronous workflows with the ability to generate multiple results from sequence computations. In Haskell, layered computation types can be created using monad transformers (that add state, exceptions, etc.). F# does not support higher-kinded types, so monad transformers cannot be encoded directly, but they still provide useful framework for documenting computations.

The asynchronous sequence computation (from the paper) can be expressed as an application of the list monad transformer to the asynchronous workflow monad:

type ListT<'M, 'T> = 'M<ListTInner<'M, 'T>>
and ListTInner<'M, 'T> = Nil | Cons of 'T * ListT<'M, 'T>

type AsyncSeq<'T> = ListT<Async, 'T> 

This sample is not valid F# (the type parameter 'M would have a kind * -> *), but it demonstrates the idea. In this article, we will not implement asynchronous sequences, because that would be too complex, but we use a simpler example. We show layering of monads using lazy list which is a similar concept. Using the above pseudo-code, it could be expressed as LazyList<'T> = ListT<Lazy, 'T>.

Implementing lazy list computation

The type that represents lazy list (or computation that generates a lazy list) can be defined as follows:

type LazyList<'T> = L of Lazy<LazyListInner<'T>>
and LazyListInner<'T> = Nil | Cons of 'T * LazyList<'T>

As already mentioned, F# does not support higher-kinded types, so we need to implement the operations of the composed monad by hand. In practice, this is not usually an issue, because layered computations are not used that frequently in F# - they are certainly less frequent than in e.g. Haskell and so it is acceptable to repeat some parts of the code.

The following code sample defines the basic operations for composing lazy list computations:

/// Creates a lazy list containing a single element
let unit v = L (lazy Cons(v, L (lazy Nil)))
/// Creates a lazy list that is empty
let zero () = L (lazy Nil)

/// Concatenates the elements of two lazy lists 
let rec combine (L l1) (L l2) = L (Lazy.Create(fun () ->
  match l1.Value with 
  | Nil -> l2.Value
  | Cons(x, xs) -> Cons(x, combine xs (L l2))))

/// For every input, generates a new lazy list using
/// the provided function and concatenates the results
let rec bind f (L l) = L (Lazy.Create(fun () ->
  match l.Value with
  | Nil -> Nil
  | Cons(x, xs) -> 
      let (L res) = combine (f x) (bind f xs)

/// Wraps a function with untracked effects into a lazy list
let delay (f:unit -> LazyList<_>) = L (Lazy.Create(fun () ->
  let (L inner) = f () in inner.Value))

The following code sampel adds a number of functions for converting between lists, lazy lists and lazy values:

/// Turn a lazy value into a singleton list
let ofLazy (l:Lazy<_>) = delay (fun () -> unit (l.Value))
/// Turn a non-lazy list into a lazy list
let rec ofList l = delay (fun () -> 
  match l with
  | [] -> zero ()
  | x::xs -> combine (unit x) (ofList xs))

/// Evaluate a lazy list and obtain a list
let rec toList (L inner) = 
  match inner.Value with
  | Nil -> []
  | Cons(x, xs) -> x::(toList xs)

Defining the computation builder

Using the operations defined above, it is easy to define a computation builder for generating lazy lists. The underlying monad (lazy) is wrapped into a list, which is both monoidal and monadic computation (as discussed earlier. This means that we can define monoidal members such as Yield and Combine that are specific to list computations. The next part of the snippet is more interesting as it defines multiple variants of monadic binding:

/// Computation builder for creating lazy lists
type LazyListBuilder() = 
  // Operations from the monoidal structure
  member x.Yield(v) = unit v
  member x.YieldFrom(lv) = lv
  member x.Combine(l1, l2) = combine l1 l2
  member x.Zero() = zero()
  member x.Delay(f) = delay f

  // Bind and lifted bind operators
  member x.For(ll, f) = bind f ll
  member x.For(l, f) = bind f (ofList (List.ofSeq l))
  member x.Bind(lv, f) = bind f (ofLazy lv)

/// Single instance of the computation builder
let llist = LazyListBuilder()

The last three operations of the computation builder represent various forms of binding. The first For member is the standard binding of the composed monad (that is, lazy list). The next two operations represent binding on one of the underlying monads. In the first case (second For member), we can bind on a non-lazy list - the list is lifted to a lazy list and then used as normal. In the last case (the Bind member), we can bind on a lazy value - the value is converted to a singleton lazy list and then used as normal.

The choice of For for normal binding and binding on a list is discussed in the paper. Briefly, these two represent computations that produce "multiple" values and so processing them using for intuitively feels more appropriate.

Programming with lazy lists

The design of the computation builder is motivated by the aim to get as readable syntax as possible when using the llist { .. } computation (the syntax is the same as the one for asyncSeq { .. } used in the paper).

The following example creates a lazy value lazyRandom, representing a random number generator and then it generates two lazy lists:

/// Lazily constructed random generator
let lazyRandom = lazy System.Random()

/// Generate a lazy list with random numbers
let nums = 
  llist { for x in 1 .. 5 do 
            let! rnd = lazyRandom
            yield rnd.Next(10) }

/// Generate a lazy list by using 'nunms' twice
let twiceNums = 
  llist { yield! nums
          for n in nums do
            yield n * 10 }

// Run this line to see the result
twiceNums |> toList

The computation that creates nums uses for to bind on a non-lazy list (although this construct can be also viewed as standard control-flow extension). Next, it uses the let! syntax to bind on a lazy value, which is initialized on the first access. Finally, it returns the next element of the list using yield.

The second computation uses yield! to generate one part of the result. The second part of the result is generated using the last overloaded for - this time, the argument is lazy list (and so the operation has the type of monadic bind).

The translation of the above samples is standard - it follows the pattern that was shown in all previous examples and so we omit the details.

Monad transformer laws

As discussed in the paper, when describing layered transformations in terms of monad transformers, they are associated with a set of laws that are required to hold. This section discusses the laws - we assume that l is the underlying monad (i.e. lazy) and ll is the result of monad transformer application (i.e. lazy list).

The computation expressions that correspond to the monad transformer laws (using the above sytnax) can be written as follows:

/// Law that specifies lifting w.r.t. unit
let liftUnit v = 
  let m1 = ll { let! x = l { return v } in yield x } 
  let m2 = ll { yield v }
  m1 |> shouldEqual m2

/// Law that specifies lifting w.r.t. bind
let liftBind m g f = 
  let m1 = ll { let! y = l { let! x = m in return! f x } 
                yield! g y }    
  let m2 = ll { let! x = m in let! y = l { return! f x }
                yield! g y }
  m1 |> shouldEqual m2
union case ListTInner.Nil: ListTInner<'M,'T>
union case ListTInner.Cons: 'T * ListT<'M,'T> -> ListTInner<'M,'T>
type ListT<'M,'T> = '?221124

Full name: TryJoinads.ListT<_,_>
type AsyncSeq<'T> = ListT<Async,'T>

Full name: TryJoinads.AsyncSeq<_>
Multiple items
type Async<'T>

Full name: Microsoft.FSharp.Control.Async<_>

type Async
  static member AsBeginEnd : computation:('Arg -> Async<'T>) -> ('Arg * System.AsyncCallback * obj -> System.IAsyncResult) * (System.IAsyncResult -> 'T) * (System.IAsyncResult -> unit)
  static member AwaitEvent : event:IEvent<'Del,'T> * ?cancelAction:(unit -> unit) -> Async<'T> (requires delegate and 'Del :> System.Delegate)
  static member AwaitIAsyncResult : iar:System.IAsyncResult * ?millisecondsTimeout:int -> Async<bool>
  static member AwaitWaitHandle : waitHandle:System.Threading.WaitHandle * ?millisecondsTimeout:int -> Async<bool>
  static member CancelDefaultToken : unit -> unit
  static member Catch : computation:Async<'T> -> Async<Choice<'T,exn>>
  static member FromBeginEnd : beginAction:(System.AsyncCallback * obj -> System.IAsyncResult) * endAction:(System.IAsyncResult -> 'T) * ?cancelAction:(unit -> unit) -> Async<'T>
  static member FromBeginEnd : arg:'Arg1 * beginAction:('Arg1 * System.AsyncCallback * obj -> System.IAsyncResult) * endAction:(System.IAsyncResult -> 'T) * ?cancelAction:(unit -> unit) -> Async<'T>
  static member FromBeginEnd : arg1:'Arg1 * arg2:'Arg2 * beginAction:('Arg1 * 'Arg2 * System.AsyncCallback * obj -> System.IAsyncResult) * endAction:(System.IAsyncResult -> 'T) * ?cancelAction:(unit -> unit) -> Async<'T>
  static member FromBeginEnd : arg1:'Arg1 * arg2:'Arg2 * arg3:'Arg3 * beginAction:('Arg1 * 'Arg2 * 'Arg3 * System.AsyncCallback * obj -> System.IAsyncResult) * endAction:(System.IAsyncResult -> 'T) * ?cancelAction:(unit -> unit) -> Async<'T>
  static member FromContinuations : callback:(('T -> unit) * (exn -> unit) * (System.OperationCanceledException -> unit) -> unit) -> Async<'T>
  static member Ignore : computation:Async<'T> -> Async<unit>
  static member OnCancel : interruption:(unit -> unit) -> Async<System.IDisposable>
  static member Parallel : computations:seq<Async<'T>> -> Async<'T []>
  static member RunSynchronously : computation:Async<'T> * ?timeout:int * ?cancellationToken:System.Threading.CancellationToken -> 'T
  static member Sleep : millisecondsDueTime:int -> Async<unit>
  static member Start : computation:Async<unit> * ?cancellationToken:System.Threading.CancellationToken -> unit
  static member StartChild : computation:Async<'T> * ?millisecondsTimeout:int -> Async<Async<'T>>
  static member StartImmediate : computation:Async<unit> * ?cancellationToken:System.Threading.CancellationToken -> unit
  static member StartWithContinuations : computation:Async<'T> * continuation:('T -> unit) * exceptionContinuation:(exn -> unit) * cancellationContinuation:(System.OperationCanceledException -> unit) * ?cancellationToken:System.Threading.CancellationToken -> unit
  static member SwitchToContext : syncContext:System.Threading.SynchronizationContext -> Async<unit>
  static member SwitchToNewThread : unit -> Async<unit>
  static member SwitchToThreadPool : unit -> Async<unit>
  static member TryCancelled : computation:Async<'T> * compensation:(System.OperationCanceledException -> unit) -> Async<'T>
  static member CancellationToken : Async<System.Threading.CancellationToken>
  static member DefaultCancellationToken : System.Threading.CancellationToken

Full name: Microsoft.FSharp.Control.Async
type LazyList<'T> = | L of Lazy<LazyListInner<'T>>

Full name: TryJoinads.LazyList<_>
  type: LazyList<'T>
union case LazyList.L: Lazy<LazyListInner<'T>> -> LazyList<'T>
Multiple items
active recognizer Lazy: Lazy<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.( |Lazy| )

type Lazy<'T> = System.Lazy<'T>

Full name: Microsoft.FSharp.Control.Lazy<_>
type LazyListInner<'T> =
  | Nil
  | Cons of 'T * LazyList<'T>

Full name: TryJoinads.LazyListInner<_>
  type: LazyListInner<'T>
union case LazyListInner.Nil: LazyListInner<'T>
union case LazyListInner.Cons: 'T * LazyList<'T> -> LazyListInner<'T>
Multiple items
val unit : 'a -> LazyList<'a>

Full name: TryJoinads.unit

 Creates a lazy list containing a single element

type unit = Unit

Full name: Microsoft.FSharp.Core.unit
  type: unit
val v : 'a
val zero : unit -> LazyList<'a>

Full name:

 Creates a lazy list that is empty
val combine : LazyList<'a> -> LazyList<'a> -> LazyList<'a>

Full name: TryJoinads.combine

 Concatenates the elements of two lazy lists
val l1 : Lazy<LazyListInner<'a>>
val l2 : Lazy<LazyListInner<'a>>
static member System.Lazy.Create : creator:(unit -> 'T) -> System.Lazy<'T>
property System.Lazy.Value: LazyListInner<'a>
val x : 'a
val xs : LazyList<'a>
  type: LazyList<'a>
val bind : ('a -> LazyList<'b>) -> LazyList<'a> -> LazyList<'b>

Full name: TryJoinads.bind

 For every input, generates a new lazy list using
 the provided function and concatenates the results
val f : ('a -> LazyList<'b>)
val l : Lazy<LazyListInner<'a>>
val res : Lazy<LazyListInner<'b>>
property System.Lazy.Value: LazyListInner<'b>
val delay : (unit -> LazyList<'a>) -> LazyList<'a>

Full name: TryJoinads.delay

 Wraps a function with untracked effects into a lazy list
val f : (unit -> LazyList<'a>)
val inner : Lazy<LazyListInner<'a>>
val ofLazy : Lazy<'a> -> LazyList<'a>

Full name: TryJoinads.ofLazy

 Turn a lazy value into a singleton list
val l : Lazy<'a>
property System.Lazy.Value: 'a
val ofList : 'a list -> LazyList<'a>

Full name: TryJoinads.ofList

 Turn a non-lazy list into a lazy list
val l : 'a list
  type: 'a list
val xs : 'a list
  type: 'a list
val toList : LazyList<'a> -> 'a list

Full name: TryJoinads.toList

 Evaluate a lazy list and obtain a list
type LazyListBuilder =
    new : unit -> LazyListBuilder
    member Bind : lv:Lazy<'a> * f:('a -> LazyList<'b>) -> LazyList<'b>
    member Combine : l1:LazyList<'i> * l2:LazyList<'i> -> LazyList<'i>
    member Delay : f:(unit -> LazyList<'g>) -> LazyList<'g>
    member For : ll:LazyList<'e> * f:('e -> LazyList<'f>) -> LazyList<'f>
    member For : l:seq<'c> * f:('c -> LazyList<'d>) -> LazyList<'d>
    member Yield : v:'k -> LazyList<'k>
    member YieldFrom : lv:'j -> 'j
    member Zero : unit -> LazyList<'h>

Full name: TryJoinads.LazyListBuilder

 Computation builder for creating lazy lists
val x : LazyListBuilder
member LazyListBuilder.Yield : v:'k -> LazyList<'k>

Full name: TryJoinads.LazyListBuilder.Yield
val v : 'k
member LazyListBuilder.YieldFrom : lv:'j -> 'j

Full name: TryJoinads.LazyListBuilder.YieldFrom
val lv : 'j
member LazyListBuilder.Combine : l1:LazyList<'i> * l2:LazyList<'i> -> LazyList<'i>

Full name: TryJoinads.LazyListBuilder.Combine
val l1 : LazyList<'i>
  type: LazyList<'i>
val l2 : LazyList<'i>
  type: LazyList<'i>
member LazyListBuilder.Zero : unit -> LazyList<'h>

Full name: TryJoinads.LazyListBuilder.Zero
member LazyListBuilder.Delay : f:(unit -> LazyList<'g>) -> LazyList<'g>

Full name: TryJoinads.LazyListBuilder.Delay
val f : (unit -> LazyList<'g>)
member LazyListBuilder.For : ll:LazyList<'e> * f:('e -> LazyList<'f>) -> LazyList<'f>

Full name: TryJoinads.LazyListBuilder.For
val ll : LazyList<'e>
  type: LazyList<'e>
val f : ('e -> LazyList<'f>)
member LazyListBuilder.For : l:seq<'c> * f:('c -> LazyList<'d>) -> LazyList<'d>

Full name: TryJoinads.LazyListBuilder.For
val l : seq<'c>
  type: seq<'c>
  inherits: System.Collections.IEnumerable
val f : ('c -> LazyList<'d>)
Multiple items
module List

from Microsoft.FSharp.Collections

type List<'T> =
  | ( [] )
  | ( :: ) of 'T * 'T list
    interface System.Collections.IEnumerable
    interface System.Collections.Generic.IEnumerable<'T>
    member Head : 'T
    member IsEmpty : bool
    member Item : index:int -> 'T with get
    member Length : int
    member Tail : 'T list
    static member Cons : head:'T * tail:'T list -> 'T list
    static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>
  type: List<'T>
val ofSeq : seq<'T> -> 'T list

Full name: Microsoft.FSharp.Collections.List.ofSeq
member LazyListBuilder.Bind : lv:Lazy<'a> * f:('a -> LazyList<'b>) -> LazyList<'b>

Full name: TryJoinads.LazyListBuilder.Bind
val lv : Lazy<'a>
val llist : LazyListBuilder

Full name: TryJoinads.llist

 Single instance of the computation builder
val lazyRandom : Lazy<System.Random>

Full name: TryJoinads.lazyRandom

 Lazily constructed random generator
namespace System
type Random =
    new : unit -> System.Random
    new : int -> System.Random
    member Next : unit -> int
    member Next : int -> int
    member Next : int * int -> int
    member NextBytes : System.Byte [] -> unit
    member NextDouble : unit -> float

Full name: System.Random
val nums : LazyList<int>

Full name: TryJoinads.nums
  type: LazyList<int>

 Generate a lazy list with random numbers
val x : int
  type: int
  inherits: System.ValueType
val rnd : System.Random
val twiceNums : LazyList<int>

Full name: TryJoinads.twiceNums
  type: LazyList<int>

 Generate a lazy list by using 'nunms' twice
val n : int
  type: int
  inherits: System.ValueType
type LazyBuilder =
    new : unit -> LazyBuilder
    member Bind : l:Lazy<'T> * f:('T -> Lazy<'R>) -> Lazy<'R>
    member Return : v:'T -> Lazy<'T>
    member ReturnFrom : m:Lazy<'T> -> Lazy<'T>

Full name: TryJoinads.LazyBuilder
val x : LazyBuilder
member LazyBuilder.Bind : l:Lazy<'T> * f:('T -> Lazy<'R>) -> Lazy<'R>

Full name: TryJoinads.LazyBuilder.Bind
val l : Lazy<'T>
val f : ('T -> Lazy<'R>)
val failwith : string -> 'T

Full name: Microsoft.FSharp.Core.Operators.failwith
member LazyBuilder.Return : v:'T -> Lazy<'T>

Full name: TryJoinads.LazyBuilder.Return
val v : 'T
member LazyBuilder.ReturnFrom : m:Lazy<'T> -> Lazy<'T>

Full name: TryJoinads.LazyBuilder.ReturnFrom
val m : Lazy<'T>
val l : LazyBuilder

Full name: TryJoinads.l
val ll : LazyListBuilder

Full name: TryJoinads.ll
val shouldEqual : 'a -> 'b -> 'c

Full name: TryJoinads.shouldEqual
val a : 'a
val b : 'b
val liftUnit : 'a -> 'b

Full name: TryJoinads.liftUnit

 Law that specifies lifting w.r.t. unit
val m1 : LazyList<'a>
  type: LazyList<'a>
val m2 : LazyList<'a>
  type: LazyList<'a>
val liftBind : Lazy<'a> -> ('b -> LazyList<'c>) -> ('a -> #Lazy<'b>) -> 'e

Full name: TryJoinads.liftBind

 Law that specifies lifting w.r.t. bind
val m : Lazy<'a>
val g : ('b -> LazyList<'c>)
val f : ('a -> #Lazy<'b>)
val m1 : LazyList<'c>
  type: LazyList<'c>
val y : 'b
val m2 : LazyList<'c>
  type: LazyList<'c>