CODEWITHSUNDEEP
f#seq
Abel
Abel

Reputation: 57159

Try to get all or nothing from a sequence based on a precondition

The following code will not work as I expected it to:

// Gets all or nothing. If predicate is false for at least one item 
// in the sequence, returns None. If seq is empty, returns the empty seq.
let tryGetAllOrNone predicate (source: seq<_>) =
    let mutable condition = true
    let resultSeq =
        seq {
            use e = source.GetEnumerator()
            while condition && e.MoveNext() && (condition <- predicate e.Current; condition) do
                yield e.Current
        }
    if condition then Some resultSeq
    else None

The reason is quite clear: a sequence is lazily evaluated, which means that here the if statement will be evaluated first, returning the sequence. Then, when we consume the resulting sequence we will always get Some results, until the condition turns false:

// expect: None (predicate is false for the first item)
> [1;2;3] |> tryGetAllOrNone (fun x -> x = 2);;
val it : seq<int> option = Some (seq [])

// expect None (predicate is false for the second item)
> [1;2;3] |> tryGetAllOrNone (fun x -> x = 1);;
val it : seq<int> option = Some (seq [1])

// correct (predicate is always true)
> [1;2;3] |> tryGetAllOrNone (fun x -> x > 0);;
val it : seq<int> option = Some (seq [1; 2; 3])

I might just have to consume the sequence first, i.e. by using [...yield ...] instead of seq { .. yield ...}, but maybe there's a simpler solution that retains the laziness (just asking the question makes it sound backwards, so my gut tells me: consume first, right)?

EDIT: thinking about this is a tad longer has me come to the conclusion that what I'm asking is not possible. You cannot first lazily return one after the other from a sequence and then, upon hitting an invalid item, say: "hey, all those items you got thus far, give them back, if one is invalid, all are invalid!".

Leaving it out here nonetheless in case it helps someone else or in case someone has a better idea ;).

Upvotes: 0

Views: 40

Answers (1)

Tomas Petricek
Tomas Petricek

Reputation: 243041

You are right that, in general, you will need to iterate over the whole sequence until you can return None or Some. If the last element of the sequence does not satsify the condition, then you need to first read all the preceding elements until you know that you have failed.

The only optimization you can do is that you can return None as soon as you find a first element that does not satisfy the condition. This is slightly better than building the whole sequence and then checking if the condition was false for any of the elemnetns (in that, if an earlier element fails to satisfy the condition, you can return None sooner). The following implementation does that:

// Gets all or nothing. If predicate is false for at least one item 
// in the sequence, returns None. If seq is empty, returns the empty seq.
let tryGetAllOrNone predicate (source: seq<_>) =
    let results = ResizeArray<_>()
    let mutable failed = false
    use e = source.GetEnumerator()
    while not failed && e.MoveNext() do
      if not (predicate e.Current) then failed <- true
      else results.Add(e.Current)
    if failed then None 
    else Some(seq results)

Upvotes: 2

Related Questions