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

Question

I'm trying to understand how to use F# computation expressions and it certainly puzzles me.

The following example makes some amount of sense to me.

type ListMonad() =
   member o.Bind(  (m:'a list), (f: 'a -> 'b list) ) = List.collect f m
   member o.Return(x) = [x]

let list = ListMonad()

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

My question is, how would you add a condition to this computation expression? Specifically, how would you alter it to return a list of elements only where the x value is strictly smaller than the y value? (Let's not filter it out afterward).

Answer 1

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 ints, 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.