F# stop Seq.map when a predicate evaluates true

Question

I'm currently generating a sequence in a similar way to:

migrators
|> Seq.map (fun m -> m())

The migrator function is ultimately returning a discriminated union like:

type MigratorResult =
| Success of string * TimeSpan
| Error of string * Exception

I want to stop the map once I encounter my first Error but I need to include the Error in the final sequence.

I have something like the following to display a final message to the user

match results |> List.rev with
| [] -> "No results equals no migrators"
| head :: _ ->
   match head with
   | Success (dt, t) -> "All migrators succeeded"
   | Error (dt, ex) -> "Migration halted owing to error"

So I need:

1. A way to stop the mapping when one of the map steps produces an Error
2. A way to have that error be the final element added to the sequence

I appreciate there may be a different sequence method other than map that will do this, I'm new to F# and searching online hasn't yielded anything as yet!

Newhouse

Answer 1

I guess there are multiple approaches here, but one way would be to use unfold:

migrators 
|> Seq.unfold (fun ms ->
    match ms with
    | m :: tl -> 
        match m () with
        | Success res -> Some (Success res, tl)
        | Error res   -> Some (Error res, [])
    | [] -> None)
|> List.ofSeq

Note the List.ofSeq at the end, that's just there for realizing the sequence. A different way to go would be to use sequence comprehensions, some might say it results in a clearer code.

Melonie

This actually works great! I knew it was going to be one of the functions with an accumulator but didn't realise unfold could be used this way. – Newhouse

Answer 2

The ugly things Tomaš alludes to are 1) mutable state, and 2) manipulation of the underlying enumerator. A higher-order function which returns up to and including when the predicate holds would then look like this:

module Seq =
    let takeUntil pred (xs : _ seq) = seq{
        use en = xs.GetEnumerator()
        let flag = ref true
        while !flag && en.MoveNext() do
            flag := not <| pred en.Current
            yield en.Current }

seq{1..10} |> Seq.takeUntil (fun x -> x % 5 = 0)
|> Seq.toList
// val it : int list = [1; 2; 3; 4; 5]

For your specific application, you'd map the cases of the DU to a boolean.

(migrators : seq<MigratorResult>)
|> Seq.takeUntil (function Success _ -> false | Error _ -> true)

Ge

Answer 3

I think the answer from @scrwtp is probably the nicest way to do this if your input is reasonably small (and you can turn it into an F# list to use pattern matching). I'll add one more version, which works when your input is just a sequence and you do not want to turn it into a list.

Essentially, you want to do something that's almost like Seq.takeWhile, but it gives you one additional item at the end (the one, for which the predicate fails).

To use a simpler example, the following returns all numbers from a sequence until one that is divisible by 5:

let nums = [ 2 .. 10 ]

nums
|> Seq.map (fun m -> m % 5)
|> Seq.takeWhile (fun n -> n <> 0)

So, you basically just need to look one element ahead - to do this, you could use Seq.pairwise which gives you the current and the next element in the sequence"

nums
|> Seq.map (fun m -> m % 5)
|> Seq.pairwise                          // Get sequence of pairs with the next value
|> Seq.takeWhile (fun (p, n) -> p <> 0)  // Look at the next value for test
|> Seq.mapi (fun i (p, n) ->             // For the first item, we return both
    if i = 0 then [p;n] else [n])        //   for all other, we return the second
|> Seq.concat

The only ugly thing here is that you then need to flatten the sequence again using mapi and concat.

This is not very nice, so a good thing to do would be to define your own higher-order function like Seq.takeUntilAfter that encapsulates the behavior you need (and hides all the ugly things). Then your code could just use the function and look nice & readable (and you can experiment with other ways of implementing this).

Eleonoreeleoptene