Short circuiting a list mapping with a partial function

Question 1

Based on answers and comments by Daniel and Søren Debois, I've come up with the following:

let tryMap f xs =
    let rec loop ys = function
        | []    -> maybe { return List.rev ys }
        | x::xs -> maybe { let! y = f x in return! loop (y::ys) xs }
    loop [] xs

I'm not quite sure if it's tail-recursive or not though, since I'm not a total expert in the inner workings of computation- (or in this case specifically: maybe-) expressions.

What do you guys think of this? :-)

Question 2

I came up with an implementation using Seq.scan and Seq.takeWhile, which is shorter, but not particularly elegant. It uses Seq for its laziness - that way, we do not run the computation for values that we do not need, because some earlier function has failed.

The idea is to yield a sequence of intermediate states - so we'll start with Some [], followed by
Some [first] and Some [second; first] and so on, and possibly None at the end when some function fails. It appends the new values to the front - which is fine, because we can easily reverse the list later. Using tryFac as the function to call, it looks like this:

[1;2;-3;4;5] 
|> Seq.scan (fun (prev, st) v ->
  // If we failed when calculating previous function, return `None`
  match st with
  | None -> st, None
  | Some l ->
    // Otherwise run the function and see if it worked
    match tryFac v with
    | Some n -> st, Some (n::l) // If so, add new value
    | _ ->      st, None )      // Otherwise, return None
    (Some[], Some[]) // Using empty list as the initial state
  // Take while the previous value was 'Some'
  |> Seq.takeWhile (function Some _, _ -> true | _ -> false)
  // Take the last value we got and reverse the list
  |> Seq.last |> snd |> Option.map List.rev

The state is not just the current value, but a pair containing the previous value and the current value. This way, we can easily get the first None or the last Some value using takeWhile.

EDIT: Well, it was shorter when I first wrote it, but with the comments and nicer formatting, it is probably as long as your original function. So maybe it's not really an improvement :-)

Question 3

Here is a variant in monadic/workflow style:

let rec tryMap f = function 
    | [] -> Some [] 
    | x :: xs -> f x         |> Option.bind (fun x' -> 
                 tryMap f xs |> Option.bind (fun xs' -> 
                 x' :: xs'   |> Some))

Option.bind f x applies the function f to the value inside the option x when there is one, otherwise returns None. This means we get the desired short-circuiting: as soon as f x returns None, tryMap returns.

If we import the maybe monad of FSharpx, we get to use workflow syntax:

let maybe = FSharpx.Option.maybe
let rec tryMap2 f = function 
    | [] -> maybe { return [] }
    | x :: xs -> maybe { let! x' = f x
                         let! xs' = tryMap2 f xs 
                         return x' :: xs' }

Question 4

As pointed out by Mauricio Scheffer, this a specific instance of a more general traverse operation. If you're interested in some of the background, the traverse operation is defined on traversable structures such as a list and supports mapping to an applicative structure, of which option is an instance. As you can see, there is a similarity between folding a list and traversing a list. The similarity is due to a relationship between a monoid and an applicative.

To answer your question, the following is an implementation specific to list (the traversable) and option (the applicative). Here, traverse is defined in terms of sequence by mapping after the fact. This simplifies the implementation.

module List =

    let rec sequenceO (ls:list<'a option>) : list<'a> option =
        match ls with
        | [] -> Some []
        | x::xs -> 
            match x with
            | Some x -> sequenceO xs |> Option.map (fun ls -> x::ls)
            | None -> None

    let traverseO (f:'a -> 'b option) (ls:list<'a>) : list<'b> option =
        sequenceO (List.map f ls)

Question 5

This is a straightforward way to do it:

let tryMap f xs =
    let rec loop ys = function
        | [] -> Some (List.rev ys)
        | x::xs ->
            match f x with
            | None -> None
            | Some y -> loop (y::ys) xs
    loop [] xs

You could save a few chars by using Option.bind but this reads nicely.