How to stop the traversal of a list

Question

I start in Fsharp and I have this question. Assuming I have two lists a and b of the same length, I travel theses lists simultaneously and test a condition on a and b each step, with the result of a previous calculus. If this test fails there is no need to keep on. I wrote this code :

let mutable (i : int) = 0
let mutable (good : bool) = true
let mutable (previous : int) = 0
while good && i < len do
    good <- test a.[i] b.[i] previous
    previous <- my_func a.[i] b.[i]
    i <- i + 1

I saw this code which is much much better :

List.zip a b |> List.fold (fun (x, y) (a,b) -> (p && test a b y, my_func a b) (true, 0)

But, with my code, as soon as the test fails, the process finished, not with the second code. Is there a way, using the design of the second code to stop the process ?

Thank you

score 3 · Accepted Answer · answered Feb 12 '21 at 00:07

I assume you are only interested in whether the final result is good.

As mentioned by Brian, you can use Seq.scan which behaves like Seq.fold but it returns all the intermediate states rather than just the final state. By using Seq instead of List you are also using a lazy sequence and so functions can terminate early. To do what you want, you can use Seq.scan together with Seq.forall, which will check that all values of a given sequence satisfy a certain condition - the nice thing here is that this can terminate early as soon as the condition is false.

Putting all this together, I get something like this:

Seq.zip a b 
|> Seq.scan (fun (good, prev) (a, b) -> 
     test a b prev, my_func a b) (true, 0)
|> Seq.forall (fun (good, _) -> good)

I like this, and it turned out simpler than I anticipated. You could even simplify the last line to `|> Seq.forall fst`. — Brian Berns, Feb 12 '21 at 04:33

Brian Berns · Answer 2 · 2021-02-11T20:12:19.060

Three ideas:

You could write your own variation of fold that stops when a flag is set to false. Personally, I think that would be cumbersome, though.
You could use Seq.scan to lazily accumulate all the results of my_func and then examine them, similar to this answer. Since Seq is lazy, the scan would short circuit the way you want. This is tricky to get right, though.
You could walk the lists recursively. IMHO, this is the simplest functional solution. Something like this:

let rec examine listA listB prev =
    match listA, listB with
        | headA :: tailA, headB :: tailB ->
            if test headA headB prev then
                let prev' = my_func headA headB
                examine tailA tailB prev'
            else false
        | [], [] -> true
        | _ -> false
examine listA listB 0

Thank you for your answe and the link. Basically your code has the same design as my own code, but it's much more elegant ! — joel76, Feb 12 '21 at 10:34

How to stop the traversal of a list

2 Answers2