合并两个列表

Question

我想以纯函数式的方式合并两个F#列表，但是我很难理解语法。

假设我有一个元组([5;3;8],[2;9;4])

当我调用函数时，它应该返回[5; 2; 3; 9; 8; 4]

这是我目前所拥有的内容，我确定它是错误的。如果有人能以简单的方式解释一下，我会非常感激。

let rec interleave (xs,ys) = function
|([], ys) -> ys
|(x::xs, y::ys) -> x :: y::  interleave (xs,ys) 

- user1072706

Answer 1

你的函数 几乎 是正确的。let f = function 是let f x = match x with 的简写形式，因此你不需要显式参数。另外，你的算法需要一些调整。

let rec interleave = function //same as: let rec interleave (xs, ys) = match xs, ys with
  |([], ys) -> ys
  |(xs, []) -> xs
  |(x::xs, y::ys) -> x :: y :: interleave (xs,ys)

interleave ([5;3;8],[2;9;4]) //output: [5; 2; 3; 9; 8; 4]

- Daniel

---

谢谢您的迅速回复，但我不太明白为什么没有参数。那我该如何调用这个函数呢？ - user1072706

您可以像平常一样调用该函数。代码的最后一行演示了使用方法。请参阅此MSDN文章（页面顶部）。它展示了两种形式的（等效的）函数声明。 - Daniel

Answer 2

一个重要的问题是该函数不正确。当输入为([1;2;3], [])时，它会失败，因为你在模式匹配中忽略了(xs, [])的情况。此外，为了更容易使用部分应用程序，最好将参数以柯里化形式呈现。以下是已纠正的版本：

let rec interleave xs ys =
    match xs, ys with
    | [], ys -> ys
    | xs, [] -> xs
    | x::xs', y::ys' -> x::y::interleave xs' ys'

您可以看到这个函数不是尾递归，因为在递归调用返回后它应用了两次cons (::)构造器。一种有趣的使其成为尾递归的方法是使用序列表达式：

let interleave xs ys =
    let rec loop xs ys = 
       seq {
             match xs, ys with
             | [], ys -> yield! ys
             | xs, [] -> yield! xs
             | x::xs', y::ys' -> 
                   yield x
                   yield y
                   yield! loop xs' ys'
            }
    loop xs ys |> List.ofSeq

- pad

---

虽然我个人更倾向于使用 continuation 或者累加器与 List.reverse 而不是序列表达式，但你给出了一个尾递归解决方案，+1。 - ildjarn

@ildjarn：你可能会对 这个答案 中的发现感兴趣（它们往往是不考虑算法而一致的）。简而言之，使用累加器+List.rev通常比使用continuations性能更好。 - Daniel

很酷，谢谢链接@Daniel。 Continuations和accumulator + List.rev是有趣的可能性，但我编写了这个版本使用Seq，以使其保持接近非尾递归版本。 - pad

作为 @ildjarn 建议的一个例子，请参见 我的回答。 - Mark Seemann

Answer 3

您可以利用这个机会定义一个更一般的高阶函数 - zipWith，然后使用它来实现interleave。

let rec zipWith f xlist ylist = 
  match f, xlist, ylist with
  | f, (x :: xs), (y :: ys) -> f x y :: zipWith f xs ys
  | _, _, _ -> []

let interleave xs ys = zipWith (fun a b -> [a; b]) xs ys |> List.concat

编辑：

如@pad在下面所说，F#已经有了以List.map2为名的zipWith。因此，您可以将interleave重写如下：

let interleave xs ys = List.map2 (fun a b -> [a; b]) xs ys |> List.concat

- missingfaktor

---

List.map2 在 F# 中的作用与 Haskell 中的 zipWith 相同。而 F# 的列表不是惰性的，因此在您的解决方案中使用 zipWith 将创建一个临时列表。 - pad

@pad，啊，谢谢。我之前见过List.map2，但不知怎么就忘了。关于中间集合的创建，是的，我知道这几乎适用于List上的每个高阶函数。 :-) - missingfaktor

Answer 4

自从F# 4.5（我认为）以后，假设您希望在较短的序列用尽时继续从较长的序列中产生元素，您只需执行以下操作： "最初的回答"

let interleave = Seq.transpose >> Seq.concat >> Seq.toList

> interleave [ [5;3;8]; [2;9;4] ];;
val it : int list = [5; 2; 3; 9; 8; 4]

> interleave [ [1;2;3]; [4;5]; [6;7;8;9] ];; // also works for any number of lists
val it : int list = [1; 4; 6; 2; 5; 7; 3; 8; 9]

"最初的回答"翻译成英文是 "Original Answer"。请注意，List.transpose 会在序列长度不同时抛出异常，但 Seq.transpose 不会，因此您需要使用后者。

- user2163043

---

尽管 OP 只需要合并/交错两个列表，但这种方法具有能够合并多个列表/序列的优点，并且只是使用函数组合。似乎可以在 Mono F# 4.0 上运行（在 repl.it 上进行演示：https://repl.it/@codybartfast/SO-Interleave-Sequences-F）。 - codybartfast

Answer 5

从OP的描述中不清楚如果列表长度不同会发生什么，但这里提供一种通用的尾递归实现，可以完全消耗两个列表：

// 'a list -> 'a list -> 'a list
let interleave xs ys =
    let rec imp xs ys acc =
        match xs, ys with
        |    [],    [] -> acc
        | x::xs,    [] -> imp xs [] (x::acc)
        |    [], y::ys -> imp [] ys (y::acc)
        | x::xs, y::ys -> imp xs ys (y::x::acc)
    imp xs ys [] |> List.rev

示例：

> interleave [5;3;8] [2;9;4];;
val it : int list = [5; 2; 3; 9; 8; 4]
> interleave [] [1..3];;
val it : int list = [1; 2; 3]
> interleave [1..3] [42];;
val it : int list = [1; 42; 2; 3]
> interleave [1..3] [42;1337];;
val it : int list = [1; 42; 2; 1337; 3]
> interleave [42; 1337] [1..3];;
val it : int list = [42; 1; 1337; 2; 3]

- Mark Seemann

Answer 6

我要在这里加入另一种变化。通过简单地将较长列表的剩余部分附加到末尾，可以处理不同长度的列表。

let rec interleave lst1 lst2 = [
    match lst1 with
    | lst1H :: lst1T ->
        yield lst1H
        yield! interleave lst2 lst1T
    | [] -> yield! lst2
]

工作原理：

假设我们有 let a = [1;2;3]; let b = [4;5;6] 并调用 interleave a b。

• 因为左侧列表不为空，所以匹配第一个分支。
• 我们产生第一个列表的头部 (1)。
• 然后我们使用第二个列表和第一个列表的尾部递归进入函数。注意参数的顺序已经被交换了。

在这个中间点上，我们有两个列表：第一个的余数为[2;3]，第二个为[4;5;6]。由于我们交换了参数的顺序，因此现在我们将重点放在第二个列表上。

• 列表不为空，所以我们匹配第一个分支。
• 我们产生列表的头部 (4)。
• 然后我们再次递归，再次交换参数。

此时的列表为 [2;3] 和 [5;6]，而输出包含 [1;4]。

这个过程会一直重复，直到操作的列表为空为止，这与第二个分支相匹配，产生了另一个列表的余数。

- Tyrrrz