F# 中某个类型的列表成员是否需要显式缓存

Question

我的问题可能是深入探讨 F# 编译器到底有多聪明。

我有一个扫描配置文件的类型模块，然后应该提供介于起始地址和结束地址之间的 IP 地址范围。

type IpRange (config: string) =
    // Parse the config
    member __.StartIp = new MyIp(startIp)
    member __.EndIp = new MyIp(endIp)

现在我想添加实际范围给我所有 IP，所以我添加了

    member __.Range = 
        let result = new List<MyIp>()
        let mutable ipRunner = __.StartIp
        while ipRunner <= __.EndIp do
            result.Add(new MyIp(ipRunner))
            ipRunner <- (ipRunner + 1)
        result

这有效但不是真正地道的 F#。

然后我深入研究了这个问题并提出了以下两个替代方案

let rec GetIpRangeRec (startIp: MyIp) (endIp: MyIp) (ipList: MyIp list) = 
    if startIp <= endIp then
        GetIpRangeRec (startIp + 1) endIp (ipList@[startIp])
    else
        ipList

和

let GetIpRangeUnfold (startIp: MyIp) (endIp: MyIp) =
        startIp |> Seq.unfold(fun currentIp -> 
                                if (currentIp <= endIp) then 
                                    Some(currentIp, currentIp + 1) 
                                else 
                                    None)

据我阅读列表和序列的了解，none 已缓存。因此，每当我尝试访问项目或枚举列表时，所有三个解决方案都会重新评估代码以创建列表。

我可以通过使用 Seq.cache 来解决这个问题（并且在需要时使用之前的转换序列）导致类似

member __.Range =
    GetIpRangeRec startIp endIp []
    |> List.toSeq
    |> Seq.cache

但这真的有必要吗？

我觉得我错过了一些东西，F# 编译器实际上确实缓存了结果而没有明确告诉它。

Answer 1

Seq 在 F# 中是惰性的，即偶尔缓存结果有好处。 F# List 不是惰性的，它是一个不可变的单链表，不会从缓存中获得任何好处。

Answer 2

列表（通常至少，我想可能有一些我不知道的奇怪的边缘情况）直接存储为它们的值。因此，您的递归函数将专门生成一个 MyIp 的列表 - 如果您做了一些奇怪的事情，即每次访问 MyIp 时都会重新评估，这些只会被重新评估。就像在函数 returns 中一样，您将得到一个 MyIps.

的完整评估列表

但是，存在一个小问题，即您实现的功能不是特别有效。相反，我建议以这种稍微替代的方式进行：

let rec GetIpRangeRec (startIp: MyIp) (endIp: MyIp) (ipList: MyIp list) = 
    if startIp <= endIp then
        GetIpRangeRec (startIp + 1) endIp (startIp :: ipList)
    else
        List.rev ipList

基本上，问题在于每次使用 @ 运算符追加到列表末尾时，运行时都必须走到列表末尾才能进行追加。这意味着您最终将遍历列表很多次。相反，最好简单地添加（即追加，但在前面），然后在 return 之前反转列表。这意味着您只需遍历列表一次，因为前置始终是一个恒定时间的操作（您只需创建一个新的列表条目，并带有指向列表前面的指针）。

实际上，由于您可能不想在函数之外使用预先提供的列表，我建议您改用这种方式：

let GetIpRange startIp endIp = 
    let rec GetIpRangeRec (start: MyIp) (end: MyIp) (ipList: MyIp list) = 
        if start <= end then
            GetIpRangeRec (start + 1) end (start :: ipList)
        else
            List.rev ipList 

    GetIpRangeRec startIp endIp List.empty

（请注意，我还没有对此进行测试，因此它可能无法完全完美地工作）。如果您确实希望能够预先提供起始列表，那么您可以只使用第一个。

此外，请记住，虽然列表通常适合顺序访问，但它们不适合随机访问。如果您需要对列表进行随机查找，那么我建议您在获得完整列表后使用对 List.toArray 的调用。如果你只是按顺序迭代它，可能不需要打扰。

不过，我还要强调一点：从完整的函数式编程“纯粹主义者”的角度来看，您的第一个实现可能并不完全 'functional'，但所涉及的唯一可变性都隐藏在函数内部。也就是说，您不会改变传递给函数的任何内容。从功能纯度的角度来看，这是非常好的，并且可能对性能有好处。请记住，F# 是功能优先的，而不是热衷于功能性的 ;)

编辑：想到一件事我想补充一点：我不知道你的 MyIp 类型是如何构造的，但如果你可以用数字来构建它们，那可能是值得的考虑使用像 seq {1 .. 100} 这样的序列理解，然后将其通过管道传递给 map 以创建 MyIp，例如seq {1 .. 100} |> Seq.map makeIp |> Seq.toList。这是最简单的方法，但仅当您可以简单地指定一个简单的数字范围时才有效。

F# 中某个类型的列表成员是否需要显式缓存

Is explicit caching required for List members of a type in F#

list

caching

f#

evaluation