使用递归混合两个列表中的值

Question

我想使用两个列表混合值：

List1 : [3; 2; 8; 1; 9; 3; 6]
List2: [5; 7; 0]
Output : [3; 5; 2; 7; 8; 0; 1; 9; 3; 6]

我只找到了有关相同长度的列表的信息，当我有不同的例子时，这个例子呢？

相同长度 ：

let rec mix =function
|(x::xs,y::ys) -> x::y::(mix (xs,ys))
|([],[]) -> []
| _ -> failwith "mix:param";;
mix ([3;2;8;1;9;3;6], [5; 7; 0]) ;;

Answer 1

分解这一点的最佳方法是考虑特定步骤的每个可能情况。您目前拥有：

1. |(x::xs,y::ys) 这是每个列表至少还剩下一个项目的情况
2. |([],[]) 这是两个列表都为空的情况
3. _ 此案例处理其他所有内容。

因此，您缺少的情况是一个列表为空而另一个列表至少剩下一个项目的情况。 这些案例是|(x::xs,[])和|([],y::ys)。 因此，将这两个选项添加到您的匹配语句中，如下所示：

let rec mix =function
|(x::xs,[]) |([],y::ys) -> failwith "do something here"
|(x::xs,y::ys) -> x::y::(mix (xs,ys))
|([],[]) -> []
| _ -> failwith "mix:param"

您会注意到，您现在会收到一条警告，指示最后一个案例永远不会匹配，因此可以像这样将其删除：

let rec mix =function    
|([],[]) -> []
|(x,[]) |([],x) -> failwith "test"
|(x::xs,y::ys) -> x::y::(mix (xs,ys))

请注意我如何将基本情况移动到顶部，以便在(x,[])或([], x)之前匹配。 现在所需要的只是处理最后两种情况的代码。 它看起来像这样：

|(x,[]) |([],x) -> x即返回列表中的其余值。

所以最终的解决方案看起来像这样：

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

您可以进行的另一个偷偷摸摸的优化是完全删除基本情况，因为它将被第二种情况覆盖。 即(x,[])也匹配([],[])，并将根据需要返回[]。 这给我们留下的只有：

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

Answer 2

第 1 步：了解示例

如果您很好地理解示例函数的作用，这并不难。确保您知道以下内容的含义;如果您不确定，请查找它们（搜索 web/Stackoverflow）：

• 递归

• 基本 F# 模式匹配

• 缺点(::)，既作为创建列表的运算符，也作为模式

• F# 列表表达式[...] ，再次用于创建列表和作为模式

如果您完全理解原始功能，则只需从模式匹配中删除不再需要的案例，并添加新案例：到达一个列表末尾时如何完成混合。

因此，我建议您在阅读本答案的第二部分之前自己解决它。F# 的 MSDN 参考是一个很好的起点。例如，有关模式匹配的规则和示例，请参阅此页面。

第 2 步：解决方案变体（首先阅读步骤 1！

在这种情况下，修改原始函数并不是您所能做的全部。这里有一个有一些改进的建议：

let rec private mixAux acc = function
    | h1 :: t1, h2 :: t2 -> mixAux (h2 :: h1 :: acc) (t1, t2)
    | [], t | t, [] -> List.rev acc @ t
let mix l1 l2 = mixAux [] (l1, l2)
mix [3; 2; 8; 1; 9; 3; 6] [5; 7; 0] // yields [3; 5; 2; 7; 8; 0; 1; 9; 3; 6]

这里有多种技术在起作用，您可能需要查找：

• 以 | [], t | t, [] 开头的线是 or 模式，其中两个案例只有一个主体。 t以一种或另一种方式匹配，但在两种情况下都用于同一表达式。

• 使用累加器，acc，有助于使函数尾递归。如果函数需要处理长输入或需要快速，请查找尾递归。

• private的使用隐藏了原始的"辅助"函数，并公开了一个函数，该函数以柯里形式接受参数，并且在调用时不需要累加器参数。

• 问题中的代码不遵循常见的格式约定。例如，函数体通常缩进，逗号通常后跟空格。例如，请参阅此有关格式约定的页面，以获取有多少人格式化 F# 的起点。

Answer 3

好吧，实际上只有四种情况，所以这里有一种天真的方法：

let rec mx xs ys =
    match (xs, ys) with
    | (x::xs, y::ys) -> x:: y :: (mx xs ys)
    | ([], y::ys) -> y :: (mx [] ys)
    | (x::xs, []) -> x :: (mx xs [])
    | ([], []) -> []