Short circuiting a list mapping with a partial function

Question

So, I have made this function called tryMap which is as follows:

/// tryMap, with failure and success continuations.
let rec tryMapC : 'R -> ('U list -> 'R) -> ('T -> 'U option) -> ('T list) -> 'R =
    fun failure success mapping list -> 
        match list with
        | []         -> success []
        | head::tail -> 
            match mapping head with
            | None        -> failure
            | Some result -> 
                let success = (fun results -> result::results |> success)
                tryMapC failure success mapping tail

/// <summary>
/// Attempts to map a list with a partial function.
/// <para/>
/// If a value which maps to None is encountered, 
/// the mapping stops, and returns None.
/// <para/>
/// Else, Some(list), containing the mapped values, is returned.
/// </summary>
let tryMap : ('T -> 'U option) -> 'T list -> 'U list option = 
    fun mapping list -> 
        tryMapC None Some mapping list

The purpose, as described in its documentation, is to map a list using a partial function, and short curcuit if a "full" mapping isn't "possible", for lack of better words.

Here's an example of how it could be used:

Given this function...

let tryFac n = 
    do printf "The factorial of %d" n
    if n < 0 then 
        do printf " cannot be computed.\n"
        None
    else
        let result = (List.fold (*) 1 [1..n])
        do printf " is %d\n" result
        Some result

...we can now do an all-or-nothing mapping of a list of integers with tryMap like this:

> let all = tryMap tryFac [1..5];;
The factorial of 1 is 1
The factorial of 2 is 2
The factorial of 3 is 6
The factorial of 4 is 24
The factorial of 5 is 120
val all : int list option = Some [1; 2; 6; 24; 120]

> let nothing = tryMap tryFac [1;2;-3;4;5];;
The factorial of 1 is 1
The factorial of 2 is 2
The factorial of -3 cannot be computed.
val nothing : int list option = None

Afterwards it would be easy to, for example, calculate the sum of these values - if they could all be computed, that is.

Now, my question is:

Is there a simpler/cleaner way to implement this tryMap function? (Besides not being so darn verbose, of course. :-P) I have a feeling something smart could be done using list expressions, maybe-expressions (from FSharpx) or maybe a combination of both, but I can't quite figure out how, at the moment. :-/

PS: If you have a better name than 'tryMap' for this function, don't hesitate to leave a comment. :-)

Update 1:

I have come up with this version, which is very close to what I had in mind, except it sadly doesn't short-circuit. :-/

let tryMap : ('T -> 'U option) -> 'T list -> 'U list option = 
    fun mapping list -> maybe { for value in list do return mapping value }

Note: This uses FSharpx' maybe-expressions.

Update 2:

Thanks to Tomas Petricek, I got an idea for an alternative:

let tryMap (mapping : 'T -> 'U option) (list : 'T list) : 'U list option =
    List.fold
        (
            fun (cont,quit) value -> 
                if quit then 
                    (cont,quit)
                else
                    match mapping value with
                    | None   -> (cont,true)
                    | Some r -> ((fun rs -> (r::rs)) >> cont,quit)
        )
        (id,false)
        list
    |> (fun (cont,quit) -> if quit then None else Some (cont []))

This function stops mapping after it maps to its first None value. When that happens, quit will be true, and the remaining elements won't be mapped. Afterwards, if quit is true, the partly mapped list is discarded and None is returned. If it never maps to None, it will have ended up building a continuation for constructing the mapped list.

It's still quite large though, and now it only does a "light" short circuit, in the sense that it stops trying to map the list, but it still traverses it, since that's how a fold works. :-/

Cove

Seems you reinvented mapM / traverse. (both defined in FSharpPlus in a more generic way) – Weese

Huh. Interesting. I did think the pattern seemed familiar. :-) Can you give an example of how mapM / traverse can be used to "solve the problem"? – Cove

Answer 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? :-)

Cove

Answer 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 :-)

Advised

Answer 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' }

Suspensive

This looks very nice! Is it possible to make it tail-recursive as well? :-) – Cove

Sure, but what you'd get would just be @Daniel's solution using Option.bind instead of his nested match f x with .... – Oyster

Answer 4

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.

Arian

This looks pretty neat. I'd kinda want to avoid reversing the list afterwards as well though - That's why my first implementation used continuations. :-) – Cove

Why do you want to avoid reversing the list? If you're concerned about performance, see this answer which benchmarks against continuations. – Arian

Answer 5

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) 

Haiti

Interesting stuff. :-) The implementation you've provided doesn't short-circuit, though, does it? – Cove

It does. Try it by putting a printfn at the top of the sequenceO function and running through [ Some 1 ; None ; Some 2 ] – Haiti

Oh, right. But traverseO doesn't short-circuit the mapping. :-) – Cove

True! A Seq based impl would. – Haiti

Yes, that difference seems to come from lazy vs strict evaluation. – Weese