在 Scala 中展平任意嵌套集合的通用、类型安全的方法? [英] Generic, type-safe way to flatten arbitrarily nested collections in Scala?

问题描述

有时我会花一些时间来使用 Scala，尽管我无法在自己的工作中使用它(到目前为止)，但它的功能组合对我很有吸引力.对于踢球，我决定以最通用的方式尝试前几个 99 Haskell 问题 - 操作并返回任何一种适用的集合.前几道题并不难，但我发现自己完全被 flatten 所困扰.我就是不知道如何输入这样的东西.

On occasion I take some time to play with Scala, whose mix of features appeals to me despite an inability to use it in my own work (thus far). For kicks I decided to try the first few 99 Haskell Problems in the most generic way possible — operating on and returning any kind of applicable collection. The first few questions weren’t too difficult, but I find myself utterly stymied by flatten. I just can’t figure out how to type such a thing.

具体说明我的问题:是否可以编写一个类型安全的函数来展平任意嵌套的 SeqLike ?所以，比如说，

To be specific about my question: is it possible to write a type-safe function that flattens arbitrarily-nested SeqLikes? So that, say,

flatten(List(Array(List(1, 2, 3), List(4, 5, 6)), Array(List(7, 8, 9), List(10, 11, 12))))

会回来

List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12): List[Int]

?请注意，这与 Haskell 和 Scala 问题集中的问题并不完全相同；我正在尝试编写一个函数，它不是扁平化异构列表，而是扁平化同类但嵌套的序列.

? Note that this isn’t quite the same question as in the Haskell and Scala problem sets; I’m trying to write a function that flattens not heterogeneous lists but, rather, homogeneous-but-nested sequences.

在网上搜索我发现了那个问题的翻译成 Scala，但它对并返回一个 List[Any].我是否正确地认为这需要某种类型的递归?还是我认为这比它更难?

Searching the web I found a translation into Scala of that question, but it operates on and returns a List[Any]. Am I correct that this would require some kind of type recursion? Or am I making this out to be harder than it is?

推荐答案

以下适用于 Scala 2.10.0-M7.您将需要为 Array 支持添加额外的案例，并可能对其进行改进以具有更具体的输出集合类型，但我想这一切都可以从这里开始:

The following works in Scala 2.10.0-M7. You will need to add extra cases for Array support, and perhaps refine it to have more specific output collection types, but I guess it can all be done starting from here:

sealed trait InnerMost {
  implicit def innerSeq[A]: CanFlatten[Seq[A]] { type Elem = A } =
    new CanFlatten[Seq[A]] {
      type Elem = A
      def flatten(seq: Seq[A]): Seq[A] = seq
    }
}
object CanFlatten extends InnerMost {
  implicit def nestedSeq[A](implicit inner: CanFlatten[A]) 
  : CanFlatten[Seq[A]] { type Elem = inner.Elem } =
    new CanFlatten[Seq[A]] {
      type Elem = inner.Elem
      def flatten(seq: Seq[A]): Seq[inner.Elem] =
        seq.flatMap(a => inner.flatten(a))
    }
}
sealed trait CanFlatten[-A] {
  type Elem
  def flatten(seq: A): Seq[Elem]
}

implicit final class FlattenOp[A](val seq: A)(implicit val can: CanFlatten[A]) {
  def flattenAll: Seq[can.Elem] = can.flatten(seq)
}

// test        
assert(List(1, 2, 3).flattenAll == Seq(1, 2, 3))
assert(List(Seq(List(1, 2, 3), List(4, 5, 6)), Seq(List(7, 8, 9),
                List(10, 11, 12))).flattenAll == (1 to 12).toSeq)

这篇关于在 Scala 中展平任意嵌套集合的通用、类型安全的方法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！