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

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])

我想从三个方面改进上述内容。

使用 con (::) 而不是 concat (@)

将列表累积从 myFunc 移动到 List.fold 操作

确保结果列表顺序与上面相同(即最后一个结果在列表的末尾而不是头)

例如，我想写一个 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

但是当我这样做时，我没有看到如何在 Fold 函数中使用 (::) cons。

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从 fold 获取所有中间结果，这是执行折叠 + 累加器技巧的内置方法。
最后一个值是通过 reduce 获得的技巧，因为没有内置的“列表的最后一个”函数，中间结果是处理数据的第二部分，除了作为初始状态的第一个元素。