Is there a standard monad for the "opposite" of the maybe monad?

Question

The maybe monad allows to chain a set of operators that all may fail (by returning None), and at the end returns Some result if every suboperation succeeded, or None if anything failed. Here's a small dummy example:

type MaybeBuilder() =
    member this.Return(x) = 
        Some x
    member this.Bind(m, f) = 
        match m with
        | Some x -> f x
        | None -> None

let maybe = MaybeBuilder()

let list = [1;2;3;4]

// evaluates to Some 3
maybe {
    let! x1 = List.tryFind ((=) 1) list
    let! x2 = List.tryFind ((=) 2) list
    return x1 + x2
}

// evaluates to None 
maybe {
    let! x1 = List.tryFind ((=) 1) list
    let! x2 = List.tryFind ((=) 6) list
    return x1 + x2
}

This is roughly equivalent to this:

// evaluates to Some 3
match List.tryFind ((=) 1) list with
| None -> None
| Some x1 ->
    match List.tryFind ((=) 2) list with
    | None -> None
    | Some x2 -> Some (x1 + x2)

// evaluates to None
match List.tryFind ((=) 1) list with
| None -> None
| Some x1 ->
    match List.tryFind ((=) 6) list with
    | None -> None
    | Some x2 -> Some (x1 + x2)

In a piece of code I have I'm currently doing the "opposite" of this, returning the first successfull hit:

// evaluates to Some 1
match List.tryFind ((=) 1) list with
| Some x1 -> Some x1
| None ->
    match List.tryFind ((=) 2) list with
    | Some x2 -> Some x2
    | None -> None

// evaluates to Some 2
match List.tryFind ((=) 6) list with
| Some x1 -> Some x1
| None ->
    match List.tryFind ((=) 2) list with
    | Some x2 -> Some x2
    | None -> None

Is this also possible to do with a monad to get the nice computation expression syntax?

Answer 1

Some time ago, I wrote a blog that implements imperative computation builder in F#. For example, the following is a computation that returns 0 and never executes the printfn statement:

let test() = imperative {
  return 0
  printfn "after return!"
  return 1 }

I think your code sample could be written as:

imperative { return! List.tryFind ((=) 1) list 
             return! List.tryFind ((=) 2) list }

How does it work?

As you suggest (and Lee mentioned too), the type is also based on the option<'T> type, with the minor difference that I'm using a delayed option value (so that you can compose computations without evaluating them), so the type of the monadic type is actually:

type Imperative<'T> = unit -> option<'T>

The key trick in the computation builder is to add Combine (which behaves like mplus in Lee's Haskell version) that runs the first computation and returns its result (if it was Some) or runs the rest (if it was None) (both a and b are actually functions here - so we need to call them & delay the result):

member x.Combine(a, b) = (fun () ->
  match a() with 
  | Some(v) -> Some(v) // if it returned, we can return the result immediately
  | _ -> b() )         // otherwise, we need to run the second part

It actually works really nicely - you can add support for loops & exception handling and if you make the type more complicated you can add other features like break:

imperative { 
  for x in 1 .. 5 do 
    if (x % 2 = 0) then do! continue
    printfn "number = %d" x }

Answer 2

Tomas' solution with

imperative { 
    return! List.tryFind ((=) 1) list
    return! List.tryFind ((=) 2) list }

does what I wanted, but I just realised that I could also achieve what I needed more simply with just this:

// evaluates to Some 1
[1;2] |> List.tryPick (fun x -> List.tryFind ((=) x) list)
// evaluates to Some 2
[6;2] |> List.tryPick (fun x -> List.tryFind ((=) x) list)