scala - 什么是 intercalate 的逆函数，如何实现它？

Question

This question讨论如何以交替方式交错两个列表，即插入它们。

• “插层”的反义词是什么？
• 在 Scala 中是否有一种惯用的方法来实现它？

Answer 1

这个话题讨论了这个Haskell IRC session .

可能性包括“deintercalate”、“extracalate”、“ubercalate”、“outercalate”和“chocolate”；-)

假设我们要“extracalate”，它可以实现为折叠:

def extracalate[A](a: List[A]) = 
    a.foldRight((List[A](), List[A]())){ case (b, (a1,a2)) => (b :: a2, a1) }

例如:

val mary = List("Mary", "had", "a", "little", "lamb")
extracalate(mary)                              
//>  (List(Mary, a, lamb),List(had, little)

请注意，只有在以下任一情况下才能重建原始列表:

• 输入列表的长度相同，或者
• 第一个列表比第二个列表长1

第二种情况实际上对 geohashing 很有用。算法，其中纬度位和经度位被插入，但可能有奇数位。

另请注意，链接问题中 intercalate 的定义与 Haskell libraries 中的定义不同。 ，它在列表列表之间穿插一个列表!

更新:对于任何折叠，我们提供一个起始值和一个函数来应用于输入列表的每个值。此函数修改起始值并将其传递给折叠的下一步。在这里，我们从一对空输出列表开始:(List[A](), List[A]())然后对于输入列表中的每个元素，我们使用 cons :: 将其添加到其中一个输出列表的前面。但是，每次调用函数时，我们也会交换两个输出列表的顺序； (a1, a2) 变为 (b::a2, a1)。这将以交替方式在两个输出列表之间划分输入列表。因为它是右 折叠，所以我们从输入列表的末尾开始，这是按正确顺序获取每个输出列表所必需的。从起始值到最终值，我们将得到:

([], [])
([lamb], [])
([little],[lamb])
([a, lamb],[little])
([had, little],[a, lamb])
([Mary, a, lamb],[had, little])