F# Fold while building a list using cons (::) as opposed to concat (@)

Question

I have the following function which does what I want. But is uses the concat (@) operator which is O(n) as opposed to O(1) for the (::) operator

let myFunc s m cs =  
    let n = s * m
    let c = [n - s] // single element list
    (n,  cs @ c) // concat the new value to the accumulated list

let chgLstAndLast = 
    [0.99; 0.98; 1.02] 
    |> List.fold (fun (s, cs) m -> myFunc s m cs) (1., []) 

The chgLstAndLast returns the last value and list of the results generated:

val chgLstAndLast : float * float list = (0.989604, [-0.01; -0.0198; 0.019404])

I would like to improve the above in three ways.

1. Use con (::) rather than concat (@)
2. Move the list accumulation from the myFunc to the List.fold operation
3. Make sure that the resulting list order remains the same as above (i.e last result is at end of list as opposed to the head)

For example, I would like to write a myFunc like this

let myFunc s m cs =  
    let n = s * m
    let c = n - s // single element, but not as list
    (n, c) // No concat here

But when I do, I don't see how to use (::) cons in the Fold function.

Answer 1

If I understand your code correctly, what you want to do is a fold while keeping all intermediary results. This is almost what List.scan does; it also returns the initial state.

let chgLstAndLast data =
    let inner s m =
        let n = s * m
        n, n - s
    let processedData = data |> List.scan (fun (s, _) n -> inner s n) (1.0, 1.0)
    let lastResult = processedData |> List.reduce (fun _ n -> n)
    let seq = processedData |> List.tail |> List.map snd
    lastResult, seq

To explain a bit more on this code: first I declare an inner function to make the code cleaner to the exterior world (assuming myFunc isn't needed by other code), then I use scan to get all intermediary results from a fold, which is a built-in way to do your fold + accumulator trick.
The last value is obtained with a reduce trick since there's no built-in "last of list" function, and the intermediary results are the second parts of the processed data, except for the first element which is the initial state.