How to implement the List Monad (computation expression) with a condition?

computation-expression, f#

Solution

Since computation expressions can be parameterized, you might first think to try something like this:

let filterAndCollect (pred : 'a -> 'b -> bool) (f : 'a -> 'b list) (m : 'a list) =
    let f' a = [ for b in f a do if pred a b then yield b ]
    List.collect f' m

type FilteringListMonad(pred) =
    member o.Bind(  (m:'a list), (f: 'a -> 'b list) ) = filterAndCollect pred f m
    member o.Return(x) = [x]

let filteredList = FilteringListMonad(fun x y -> x < y)

let test2 =
    filteredList {
        let! x = [1 .. 10]
        let! y = [2 .. 2 .. 20]
        return (x,y)
    }

However, that fails with a type error on the `(x,y)` tuple:

This expression was expected to have type '`int`' but here has type '`'a * 'b`'

There are also two compiler warnings: on the `y` of the `x < y` expression in the FilteringListMonad constructor, there's a warning:

This construct causes code to be less generic than indicated by the type annotations. The type variable `'a` has been constrained to be type '`'b`'.

And on the number `1` in the `let! x = [1 .. 10]` expression, there's a warning:

This construct causes code to be less generic than indicated by the type annotations. The type variable `'b` has been constrained to be type '`int`'.

So between these two constraints, the return type of the computation expression (a `'b list`) has been constrained to be `int list`, but your expression is returning a `int * int list` instead. After some thinking about the type constraints, you might conclude that there's no way this can work. But there's a way to make it work. The key is to realize that the `'b` type that will be the output of your computation expression is, in this example, actually the tuple `int * int`, so you rewrite the predicate function to actually just take that `'b` type, and then everything works:

let filterAndCollect (pred : 'b -> bool) (f : 'a -> 'b list) (m : 'a list) =
    let f' a = [ for b in f a do if pred b then yield b ]
    List.collect f' m

type FilteringListMonad(pred) =
    member o.Bind(  (m:'a list), (f: 'a -> 'b list) ) = filterAndCollect pred f m
    member o.Return(x) = [x]

let filteredList = FilteringListMonad(fun (x:int,y:int) -> x < y)

let test2 =
    filteredList {
        let! x = [ 1 .. 10]
        let! y = [2 .. 2 .. 20]
        return (x,y)
    }

Note that I also had to specify the types of the predicate function's inputs. Without that, F# was generalizing them to be "any type that implements `System.IComparable`, but I was passing in `int`s, which are value types and thus don't implement any interfaces. This led to the error

This expression was expected to have type '`System.IComparable`' but here has type '`int`'.

However, declaring both parameters to the predicate as `int` did the trick.

Problem

Original source

Related problems

• Why do F# computation expressions require a builder object (rather than a class)?