如何在 F# 中以相反的顺序有效地创建列表

Question

有没有办法在不需要反转的情况下以相反的顺序构造一个列表

这是一个例子，我从标准输入读取所有行

#!/usr/bin/env dotnet fsi

open System

let rec readLines1 () =
  let rec helper acc =
    match Console.ReadLine() with
    | null -> acc
    | line ->
      helper (line :: acc)
  helper [] |> List.rev

readLines1 () |> List.iter (printfn "%s")

在从 readLines1 return 之前，我必须 List.rev 它以便顺序正确。由于结果是一个略微链接的列表，因此它必须读取所有内容并创建反向版本。有什么方法可以按正确的顺序创建列表吗？

Answer 1

您不能以相反的顺序创建列表，因为那样需要修改。如果你一个一个读取输入，并想立即将它们变成一个列表，你唯一能做的就是创建一个新列表，链接到前一个列表。

实际上，颠倒列表非常好，这可能是解决此问题的最佳方法。

出于好奇，您可以尝试定义一个与不可变 F# 列表具有相同结构的可变列表：

open System

type MutableList<'T> = 
  { mutable List : MutableListBody<'T> }

and MutableListBody<'T> = 
  | Empty
  | Cons of 'T * MutableList<'T>

现在您可以通过改变列表来实现您的功能：

let rec readLines () =
  let res = { List = Empty } 
  let rec helper acc =
    match Console.ReadLine() with
    | null -> res
    | line ->
        let next = { List = Empty }
        acc.List <- Cons(line, next)
        helper next
  helper res

这可能具有教育意义，但不是很有用，如果您真的想在 F# 中进行更改，您可能应该使用 ResizeArray。

另一个技巧是使用获取列表尾部的函数：

let rec readLines () =
  let rec helper acc =
    match Console.ReadLine() with
    | null -> acc []
    | line -> helper (fun tail -> acc (line :: tail))
  helper id

在 line 的情况下，这个 returns 一个接受 tail 的函数在 tail 之前添加 line 然后调用之前构造的任何函数在前面添加更多内容。

这实际上以正确的顺序创建了列表，但它的效率可能低于创建列表并反转它。它可能看起来不错，但是您正在为每次迭代分配一个新函数，这并不比分配列表的额外副本更好。（不过，这是个不错的把戏！）

Answer 2

您可以使用序列而不是在列表中累积行：

open System

let readLines1 () =
    let rec helper () =
        seq {
            match Console.ReadLine() with
                | null -> ()
                | line ->
                    yield line
                    yield! helper ()
        }
    helper () |> Seq.toList

readLines1 () |> List.iter (printfn "%s")

Answer 3

不实现递归函数的替代解决方案

let lines =
        Seq.initInfinite (fun _ -> Console.ReadLine())
        |> Seq.takeWhile (not << isNull)
        |> Seq.toList

如何在 F# 中以相反的顺序有效地创建列表

How to efficiently create a list in reversed order in F#

f#