使用cons(::)而不是concat(@)构建列表时F#折叠

Question

我有以下功能,它做我想要的.但是使用concat(@)运算符,它是O(n)而不是O(1)运算符

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., []) 

chgLstAndLast返回最后生成的结果值和列表:

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

我想以三种方式改进上述内容.

1. 使用con(::)而不是concat(@)
2. 将列表累积从myFunc移动到List.fold操作
3. 确保结果列表顺序保持与上面相同(即最后结果位于列表末尾而不是头部)

例如,我想写一个myFunc这样的

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

但是当我这样做时,我没有看到如何在折叠功能中使用(::)缺点.

Answer 1

如果我正确理解您的代码,您想要做的是fold保留所有中间结果.这几乎是List.scan做什么的; 它也返回初始状态.

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

为了解释一下这段代码:首先我声明一个内部函数,使代码更清洁到外部世界(假设myFunc其他代码不需要),然后我scan用来获取a的所有中间结果fold,这是一个内置的 - 在你的折叠+累积器技巧的方式.
最后一个值是通过reduce技巧获得的,因为没有内置的"最后列表"功能,并且中间结果是处理数据的第二部分,除了作为初始状态的第一个元素.