Seq.fold and boolean accumulator

Question

I can never find the source code of the F# core libraries. I know it is supposedly open but google is not kind to me in helping me locate it, if so I would have looked up the impl of Seq.fold - but here goes the question.

Does anybody see any issue with the following snippet:

let success = myList |>
                    Seq.fold 
                        (fun acc item -> evaluation item)
                        false 

Logically it doesn't seem to hold water and I can and will experiment to test it. But I wanted to ask the community. If any single evaluation inside of myList retruns false, I want the success variable to be false...

---

So the test:

let myList = [true; true]
let success = List.fold (fun acc item -> acc && item) true myList

and

let myList = [true; false; true]
let success = List.fold (fun acc item -> acc && item) true myList

do return the proper results - I just would be more comfy seeing the source...

Answer 1

I get that this is an old question, but the following may be relevant to those who have a similar question.

About the specific question here

There already exists a function that returns false as soon as one element in a Sequence is false: Seq.forAll.

So the easiest answer to the question is in fact:

let success = Seq.forAll evaluation myList

which is slightly easier to grasp than TechNeilogy’s (rewritten) answer

let success = not (Seq.exists evaluation myList)

Both in the accepted answer by Wesley Wiser and in this answer, the evaluation function is not evaluated on the items after the first item that evaluates to false. But, as Pascal Cuoq correctly remarked, in the accepted answer all the elements of the remainder of the list are still iterated over, which is useless. In contrast, Seq.forAll really stops iterating when there is no use to continue. So do Seq.exists, Seq.takeWhile, …

About short-circuiting a folding in general

There are other cases where one wants to short-circuit a folding. It can be done.

Step 1: Define a folder with some kind of indication that the state won’t change during the traversal the rest of the source sequence, and the folding should be short-circuited.

Step 2: Use Seq.scan instead of Seq.fold. Seq.scan is like Seq.fold, takes the same arguments, but computes on-demand, and returns not just the final state, but the sequence of all intermediate states and the final state. It follows that (for finite mySequence): Seq.last (Seq.scan folder initialState mySequence) = Seq.fold folder initialState mySequence

Step 3: Use a short-circuiting function on the output of Seq.scan. Take your pick: Seq.takeWhile, Seq.forall, Seq.exists, …

In the following example, the state becomes None when a duplicate element is found, which means that the scanning may be short-circuited.

let allDistinct mySequence =
    let folder state element =
        match state with
            | Some elementsSoFar when not (Set.contains element elementsSoFar) ->
                Some (Set.add element elementsSoFar)
            | _ ->
                None
    let initialState = Some Set.empty
    let scanning = Seq.scan folder initialState mySequence
    Seq.forall Option.isSome scanning

Answer 2

As for the original source, here are the fold functions from the August 10, 2010 release.

Shouldn't really need to concern yourself over the implementation, but seeing it can often be educational.

// Seq module
let fold<'T,'State> f (x:'State) (source : seq<'T>)  = 
    checkNonNull "source" source
    use e = source.GetEnumerator() 
    let mutable state = x 
    while e.MoveNext() do
        state <- f state  e.Current;
    state


// Array module
let fold<'T,'State> (f : 'State -> 'T -> 'State) (acc: 'State) (array:'T[]) = //'
    checkNonNull "array" array
    let f = OptimizedClosures.FSharpFunc<_,_,_>.Adapt(f)
    let mutable state = acc 
    let len = array.Length
    for i = 0 to len - 1 do 
        state <- f.Invoke(state,array.[i])
    state


// List module
let fold<'T,'State> f (s:'State) (list: 'T list) = 
    match list with 
    | [] -> s
    | _ -> 
        let f = OptimizedClosures.FSharpFunc<_,_,_>.Adapt(f)
        let rec loop s xs = 
            match xs with 
            | [] -> s
            | h::t -> loop (f.Invoke(s,h)) t
        loop s list


// MapTree module (Used by Map module)
let rec fold (f:OptimizedClosures.FSharpFunc<_,_,_,_>) x m  = 
    match m with 
    | MapEmpty -> x
    | MapOne(k,v) -> f.Invoke(x,k,v)
    | MapNode(k,v,l,r,_) -> 
        let x = fold f x l
        let x = f.Invoke(x,k,v)
        fold f x r

// Map module
let fold<'Key,'T,'State when 'Key : comparison> f (z:'State) (m:Map<'Key,'T>) = //'
    let f = OptimizedClosures.FSharpFunc<_,_,_,_>.Adapt(f)
    MapTree.fold f z m.Tree


// SetTree module (Used by Set module)
let rec fold f x m = 
    match m with 
    | SetNode(k,l,r,_) -> 
        let x = fold f x l in 
        let x = f x k
        fold f x r
    | SetOne(k) -> f x k
    | SetEmpty -> x

// Set module
let fold<'T,'State  when 'T : comparison> f (z:'State) (s : Set<'T>) = //'
    SetTree.fold f z s.Tree

Answer 3

something like this

let l = [true; true; true; false; true]

let eval x = x

let x = (true, l) ||> Seq.fold(fun acc item -> acc && (eval item))

or you want to stop evaluation on first false result?

let l = [true; false; true]

l |> Seq.forall id

Answer 4

Seq.exists will short circuit:

let success = 
  [1;2;3;40;5;2] 
  |> Seq.exists (fun item->(item>30))
  |> not

Answer 5

Hmmmm, I upgraded my Visual Studio and F# recently, and can't seem to locate the directory containing the F# library code. But, for what its worth, Seq.fold is equivalent to the following:

let fold f seed items =
    let mutable res = seed
    for item in items do
        res <- f res item
    res

If any single evaluation inside of myList retruns false, I want the success variable to be false...

It depends on how your evaluation function is implemented. If you want to return false when any of your items are false, use Seq.forall instead.

Answer 6

I think what you're looking for is something like this:

let success = myList |>
                    Seq.fold
                        (fun acc item -> acc && evaluation item)
                        true

This also offers "short-circut" evaluation so that if acc is false from a previous evaluation, evaluation item won't run and the expression will simply return false.

MSDN documentation for fold operator