f# - F# 中的 insertAt 更简单和/或更好

Question

我想开始一些关于简化 F# 中不同表达式的问题。

任何人都有更好和/或更简单地实现 insertAt 的想法（参数也可以重新排序）。可以使用列表或序列。

这是一些开始实现：

let insertAt x xs n = Seq.concat [Seq.take n xs; seq [x]; Seq.skip n xs]

Answer 1

dannyasher 发布的实现是非尾递归的。为了使函数更高效，我们必须引入一个显式累加器参数，它使函数尾递归并允许编译器优化递归开销：

let insertAt =
    let rec insertAtRec acc n e list = 
        match n, list with
        | 0, _     -> (List.rev acc) @ [e] @ list
        | _, x::xs -> insertAtRec (x::acc) (n - 1) e xs
        | _        -> failwith "Index out of range"

    insertAtRec []

Answer 2

使用 Seq 进行尾递归：

let rec insertAt = function
    | 0, x, xs -> seq { yield x; yield! xs }
    | n, x, xs -> seq { yield Seq.hd xs; yield! insertAt (n-1, x, Seq.skip 1 xs) }

Answer 3

这是 Haskell 列表插入的 F# 实现：

let rec insertAt x ys n =
    match n, ys with 
    | 1, _      
    | _, []     -> x::ys
    | _, y::ys  -> y::insertAt x ys (n-1)

let a = [1 .. 5]
let b = insertAt 0 a 3
let c = insertAt 0 [] 3

> 
val a : int list = [1; 2; 3; 4; 5]
val b : int list = [1; 2; 0; 3; 4; 5]
val c : int list = [0]

我的 Haskell 不足以知道在 Haskell 函数中是否正确处理了传递空列表的情况。在 F# 中，我们明确地处理了第二个匹配案例中的空列表。

丹尼

Answer 4

如果您真的想使用序列：

let insertAt x ys n =
  let i = ref n
  seq {
    for y in ys do
    decr i
    if !i = 0 then yield x
    yield y
  }

对于所有其他情况，dannyasher 的答案肯定更好更快。

Answer 5

来自 Haskell Wiki - http://www.haskell.org/haskellwiki/99_questions/21_to_28

insertAt :: a -> [a] -> Int -> [a]
insertAt x ys     1 = x:ys
insertAt x (y:ys) n = y:insertAt x ys (n-1)

我不是 F# 程序员，所以我不知道 F# 的等效语法，但这是 insertAt 的一个很好的递归定义