在Scala中压缩任意嵌套集合的通用,类型安全方法？

Question

有时候我会花一些时间和Scala一起玩,虽然在我自己的工作中无法使用Scala,但它的功能组合对我很有吸引力(到目前为止).对于踢,我决定以最通用的方式尝试前几个99 Haskell问题 - 操作并返回任何类型的适用集合.前几个问题并不太难,但我发现自己完全陷入了困境flatten.我只是无法弄清楚如何输入这样的东西.

具体来说我的问题是:是否有可能编写一个类型安全的函数来展平任意嵌套的SeqLikes？那么,比方说,

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问题集中的问题不完全相同; 我正在尝试编写一个函数来展平异构列表,而不是同构但嵌套的序列.

在网上搜索我找到了该问题的Scala翻译,但它运行并返回List [Any].我是否正确,这将需要某种类型的递归？或者我这样做是否比它更难？

Answer 1

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

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)