OCaml 中的交错

Question

我正在尝试创建一个交错一对三元组的函数，例如 ((6, 3, 2), ( 4, 5 ,1)) 并从该交错中创建一个 6 元组。 我做了一些研究，但可以理解交错应该如何工作，所以我自己尝试了一些东西，最终得到了一个创建 6 元组的代码，但不是以正确的交错方式。这是我的代码

let interleave ((a, b, c), (a', b', c')) =
  let sort2 (a, b) = if a > b then (a, b) else (b, a) in
  let sort3 (a, b, c) = 
    let (a, b) = sort2 (a, b) in
    let (b, c) = sort2 (b, c) in
    let (a, b) = sort2 (a, b) in
    (a, b, c) in
  let touch ((x), (y)) = 
    let (x) = sort3 (x) in
    let (y) = sort3 (y) in
    ((x),(y)) in
  let ((a, b, c), (a', b', c')) = 
    touch ((a, b, c), (a', b', c')) in
  (a, b', a', b, c, c');;

有人可以向我解释一下如何使用哪些函数来实现正确的交错形式。我还没有了解递归和列表，以防你问我为什么要这样做。 已经谢谢你了。

Answer 1

问题陈述使用了“max”一词，但没有定义它。如果您使用 OCaml 的内置

compare

函数作为定义，则它使用 字典序。因此，您想要 6 元组中第一个位置的最大值（6 个值中的），接下来是第二大值，依此类推。

考虑到您之前建立的元组排序技能，这应该很容易。

就其价值而言，保留两个三元组的身份似乎没有多大价值。一旦进入最外面的函数，您就可以将 6 个值作为 6 元组使用。或者说在我看来是这样。

更新

从你的例子（可能应该在一开始就给出它:-）很清楚你被要求做什么。您希望最终得到一个序列，其中原始元组的元素按其原始顺序排列，但它们可以任意交错。这通常称为“随机播放”（或合并）。你必须找到按字典顺序具有最大值的随机播放。

如果你推理出这一点，那就相当于从两个元组前面取出最大的值并将其放在输出中的下一个。

使用列表更容易做到这一点。

Answer 2

现在我明白你的最终目标是什么了。 。 .

由于

n元素的元组对于不同的n来说是不同的类型，因此您需要定义辅助函数来操作不同大小的元组。

一种方法基本上模仿列表上的递归函数（但需要许多额外的函数，因为元组都具有不同的类型），是拥有两组辅助函数：

• 将值添加到现有元组的函数：

  prepend_to_2

  ，向上到

  prepend_to_5

  。例如，

  let prepend_to_3 (a, (b, c, d)) = (a, b, c, d)
• 交错每个可能大小最多为 3 个的两个元组的函数：

  interleave_1_1

  、

  interleave_1_2

  、

  interleave_1_3

  、

  interleave_2_2

  、

  interleave_2_3

   和 

  interleave_3_3

  。 （请注意，我们不需要例如 

  interleave_2_1

  ，因为我们可以使用相反顺序的参数调用 

  interleave_1_2

  。）例如，

  let interleave_2_2 ((a, b), (a', b')) =
      if a > a'
      then prepend_to_3 (a, interleave_1_2 (b, (a', b')))
      else prepend_to_3 (a', interleave_1_2 (b', (a, b)))

  （你知道这是如何运作的吗？）

那么

interleave

 就只是 

interleave_3_3

。

使用列表和递归，这会简单得多，因为单个函数可以对任意长度的列表进行操作，因此您不需要相同逻辑的多个不同副本。