合并两个列表

我正在寻找以纯功能方式合并F＃中的2个列表。我很难理解语法。合并两个列表

让说我有一个元组([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)

来源

2012-02-01 user1072706

你的功能是几乎权。 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]

来源

2012-02-01 04:34:24 Daniel

感谢您的迅速反应，但我不明白为什么没有参数。 >]我将如何调用该函数？ [< – user1072706 2012-02-01 04:40:18

]您可以像平常一样调用该函数。最后一行代码演示了用法。请参阅[本MSDN文章]（http://msdn.microsoft.com/zh-cn/library/dd233242.aspx）（页面顶部）。它显示了两种形式的（等价）函数声明。 – Daniel 2012-02-01 04:43:26

很重要的一点是，该功能是不正确的。由于您在模式匹配中错过了(xs, [])的情况，因此输入([1;2;3], [])失败。此外，为了更容易使用部分应用，curry形式的参数更好。以下是更正后的版本：

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

你可以看到这个函数是不是尾递归因为它适用利弊(::)构造两次递归调用返回之后。一个有趣的方式让使用序列表达其尾递归：

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

来源

2012-02-01 06:33:00 pad

+1给出了一个尾递归的解决方案，虽然我个人会使用延续或累加器+ List.reverse而不是序列表达式。 – ildjarn 2012-02-01 19:23:55

@ildjarn：你可能对[这个答案]（http://stackoverflow.com/a/7199989/162396）中的发现感兴趣（它们往往是一致的，无论算法如何）。总之，使用累加器+'List.rev'通常表现比继续更好。 – Daniel 2012-02-01 19:44:04

很酷，感谢链接@Daniel。继续和累加器+'List.rev'是有趣的可能性，但是我使用'Seq'编写了这个版本以保持它接近于非尾递归。 – pad 2012-02-01 22:27:07

您可以利用这个机会来定义一个更一般的高阶函数 - 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

来源

2012-02-04 19:46:34 missingfaktor

'List.map2'与Haskell中的'zipWith'完全相同。而F＃列表并不懒，所以在解决方案中使用'zipWith'将会创建一个临时列表。 – pad 2012-02-04 23:47:39

@pad，啊，谢谢。我以前见过'List.map2'，但不知何故忘了它。关于创建中间集合，是的，我意识到这一点，但这几乎是'List'上的每个高阶函数的真实情况。 :-) – missingfaktor 2012-02-05 05:40:47

从目前还不清楚，如果名单有不同的长度应该发生什么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]

来源

2016-12-09 08:17:20

合并两个列表

回答

相关问题