Does F# have a foldList function?

Question

Mathematica and perhaps other languages have a foldList function. It is very much like fold but instead of returning only the final computed value it returns every intermediate value.

It is not hard to write a foldList function in F#:

let foldList f (x: 'S) (m: list<'T>) =
    let fs (xs: list<'S>) (y: 'T) = (f (Seq.head xs) y)::xs
    List.fold fs [x] m
    |> List.rev

let m = [1; 2; -3; 5]

foldList (+) 0 m
// val it : int list = [0; 1; 3; 0; 5]

List.fold (+) 0 m
// val it : int = 5

Is there such a function in F#? If not, is there a more efficient implementation than the one above? Is there a way to avoid the call to List.rev?

Answer 1

Yes, this is a built-in function, it's called List.scan:

let m = [1; 2; -3; 5]

List.scan (+) 0 m;;
//val it : int list = [0; 1; 3; 0; 5]

To answer your question about reversing the list, the implementation in FSharp.Core avoids reversing the list by using mutation. This mutable API is not exposed publicly. You can find the source code here if you're interested.