12

ときどき Scala をいじってみます。これまでのところ、自分の仕事では使用できませんが、Scala の機能の組み合わせは魅力的です。キックのために、最初の99 個の Haskell Problemsを可能な限り最も一般的な方法で試すことにしました。最初のいくつかの質問はそれほど難しくありませんでしたが、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 の問題セットとまったく同じ問題ではないことに注意してください。異種リストではなく、同種だがネストされたシーケンスを平坦化する関数を作成しようとしています。

Web を検索すると、その質問のScala への翻訳が見つかりましたが、それは List[Any] を操作して返します。これには何らかの型の再帰が必要になるというのは正しいですか? それとも、私はこれをより難しくしているのでしょうか?

4

3 に答える 3

13

以下は 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)
于 2012-08-29T00:07:54.970 に答える
4

.flatten正しい回数だけ呼び出すのが正しいようです：

scala> val x = List(Array(List(1, 2, 3), List(4, 5, 6)), Array(List(7, 8, 9), List(10, 11, 12)))
x: List[Array[List[Int]]] = List(Array(List(1, 2, 3), List(4, 5, 6)), Array(List(7, 8, 9), List(10, 11, 12)))

scala> x.flatten.flatten
res0: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)

Scala は型付けされているため、特定の変数のネストの深さが常に事前にわかります。.flattenこれは前もってわかっているので、呼び出す必要がある回数がわからないかのように、任意の構造を処理することにあまり価値はありません。

于 2012-08-28T14:49:26.433 に答える
3

Haskellソリューションで説明されているのと同じ問題に直面しています。Scala には異質性はありませんList。幸いなことに、Haskell ソリューションで行っているのとまったく同じ道をたどることができます。

ネストできるデータ型を定義します。

sealed trait NestedList[A]
case class Elem[A](a: A) extends NestedList[A]
case class AList[A](a: List[NestedList[A]]) extends NestedList[A]

次に、その型の一般的な flatten 関数を記述します。

def flatten[A](l: NestedList[A]): List[A] = l match {
  case Elem(x) => List(x)
  case AList(x :: xs) => flatten(x) ::: flatten(AList(xs))
  case AList(Nil) => Nil
}

あるいは

def flatten[A](l: NestedList[A]): List[A] = l match {
  case Elem(x) => List(x)
  case AList(x) => x.flatMap(flatten)
}

使用法：

flatten(AList(Elem(1) :: Elem(2) :: AList(Elem(3) :: Nil) :: Nil))

もちろん、これをメソッドとして直接NestedListトレイトに追加することもできます。

于 2012-08-28T14:24:27.697 に答える