什么是intercalate的反函数，如何实现它？

Question

这个问题讨论了如何以交替的方式交错两个列表，即将它们穿插在一起。

• “穿插”的反义词是什么？
• 在Scala中有没有惯用的实现方式？

- DNA

---

自我推广，不错的 ;) - Govind Singh

List("Mary", "had", "a", "little", "lamb", "it's").grouped(2).map{p=>(p(0), p(1))}.toList.unzip。如果列表长度为奇数，则会失败。 - The Archetypal Paul

Answer 1

这个话题在Haskell IRC会话上讨论。

可能的选择包括“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中的定义不同，后者在列表之间插入一个列表！ 更新：对于任何fold，我们提供一个起始值和一个应用于输入列表每个值的函数。这个函数修改起始值并将其传递给fold的下一步。在这里，我们从一对空输出列表开始：(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])

- DNA

---

我添加了打印语句，但我并没有完全理解你的“fold”函数。您能否简单说明一下它的作用？ - Kevin Meredith

Answer 2

此外，使用标准方法。

val mary = List("Mary", "had", "a", "little", "lamb")
       //> mary  : List[String] = List(Mary, had, a, little, lamb)
val (f, s) = mary.zipWithIndex.partition(_._2 % 2 == 0)
       //> f  : List[(String, Int)] = List((Mary,0), (a,2), (lamb,4))
       //| s  : List[(String, Int)] = List((had,1), (little,3))
(f.unzip._1, s.unzip._1) 
       //> res0: (List[String], List[String]) = (List(Mary, a, lamb),List(had, little))

虽然不是很推荐，但折叠屏在性能方面会胜过它。

用另一种方式解决问题

val g = mary.zipWithIndex.groupBy(_._2 % 2) 
        //> g  : scala.collection.immutable.Map[Int,List[(String, Int)]] = Map(1 -> List
        //| ((had,1), (little,3)), 0 -> List((Mary,0), (a,2), (lamb,4)))
 (g(0).unzip._1, g(1).unzip._1)
       //> res1: (List[String], List[String]) = (List(Mary, a, lamb),List(had, little))

也会变得缓慢

- The Archetypal Paul

Answer 3

我认为这个答案不如@DNA的答案好，因为它需要更多的代码，并且需要两次通过列表。

scala> list
res27: List[Int] = List(1, 2, 3, 4, 5)

scala> val first = list.zipWithIndex.filter( x => x._1 % 2 == 1).map(x => x._2)
first: List[Int] = List(0, 2, 4)

scala> val second = list.zipWithIndex.filter( x => x._1 % 2 == 0).map(x => x._2)
second: List[Int] = List(1, 3)

scala> (first, second)
res28: (List[Int], List[Int]) = (List(0, 2, 4),List(1, 3))

- Kevin Meredith