14

Scala でリストのリストを再帰的に逆にしたいと思います。

次のようにPythonでディープリストリバースを書きました：

def deepReverse(items):
    if type(items) == list:
        return [deepReverse(item) for item in reversed(items)]
    else: 
        return items

Scalaで同等のことを行うにはどうすればよいですか? 問題はアルゴリズムではなく、私が新しいタイプのものです。

[T] のリスト、List[List[T]]、または T のリストと T のリストを任意の深さまで取得する関数が必要です。他の場所で見た例に基づいて、それを行うためのケースクラスを作成しようとしました。Any を返し、Any を受け入れるだけの関数は必要ありません。それはだまされているように感じます。

case class NL[+T](val v : Either[List[NL[T]],T])

それでも、私は自分のタイプのバランスをとることができませんでした. 私は Scala を初めて使用しますが、再帰と型付けをいじる絶好の機会になると考えました。

4

2 に答える 2

17

sschaef が提案する、任意にネストされたリストに対して機能する型クラス アプローチのバージョンを作成することは、実際にはそれほど難しくありません。

trait Reverser[C] {
  def reverse(xs: C): C
}

implicit def rev[A](implicit ev: Reverser[A] = null) = new Reverser[List[A]] {
  def reverse(xs: List[A]) =
    Option(ev).map(r => xs map r.reverse).getOrElse(xs).reverse
}

def deepReverse[A](xs: A)(implicit ev: Reverser[A]): A = ev.reverse(xs)

メソッドの暗黙の引数evは、それ自体が可逆であることのrev証拠であり、 null の場合はそうでないことを意味します。この可逆的な証拠がある場合、それを使用して要素を逆にし(これがが行っていることです)、リスト自体を逆にします。この証拠 (ケース) がない場合は、リストを逆にするだけです。AevAList[A]mapgetOrElse

rev次のように、もう少し簡潔に (しかしおそらくもっと効率的に)書くことができます。

implicit def rev[A](implicit ev: Reverser[A] = null) = if (ev == null) {
  new Reverser[List[A]] {
    def reverse(xs: List[A]) = xs.reverse
  }
} else {
  new Reverser[List[A]] {
   def reverse(xs: List[A]) = (xs map ev.reverse).reverse
  }
}

これら 2 つのバージョンのいずれかをテストするには、次のように記述します。

scala> deepReverse(List.tabulate(3)(identity))
res0: List[Int] = List(2, 1, 0)

scala> deepReverse(List.tabulate(2,3) { case (a, b) => a + b })
res1: List[List[Int]] = List(List(3, 2, 1), List(2, 1, 0))

scala> deepReverse(List.tabulate(2, 3, 4, 5, 6) {
     |   case (a, b, c, d, e) => a + b + c + d + e
     | }).head.head.head.head
res2: List[Int] = List(15, 14, 13, 12, 11, 10)

予想通り。

以下は、このような場合に暗黙を正しくするためのより一般的なイディオムであることを付け加えておきます。

trait ReverserLow {
  implicit def listReverser[A] = new Reverser[List[A]] {
    def reverse(xs: List[A]) = xs.reverse
  }
}

object ReverserHigh extends ReverserLow {
  implicit def nestedListReverser[A](implicit ev: Reverser[A]) =
    new Reverser[List[A]] {
      def reverse(xs: List[A]) = xs.map(ev.reverse).reverse
    }
}

import ReverserHigh._

listReverser同じレベルで書いたばかりの場合nestedListReverser、リストのリストを逆にしようとすると、次のエラーが発生します。

scala> deepReverse(List.tabulate(2, 3)(_ + _))
<console>:12: error: ambiguous implicit values:
 both method listReverser...
 and method nestedListReverser...
 match expected type Reverser[List[List[Int]]]
              deepReverse(List.tabulate(2, 3)(_ + _))

2 つの優先順位を付けるための標準的なアプローチは、より低い優先順位を暗黙的にトレイト ( ) に配置し、もう一方をそのトレイトを拡張WhateverLowするオブジェクト ( ) に配置することです。WhateverHighただし、このようなかなり単純なケースでは、上記の方法でデフォルトの引数トリックを使用する方がより簡潔です (そして、私の目にはより明確です) rev。しかし、他の人のコードで別のバージョンを目にする可能性が高くなります。

于 2012-09-28T23:44:29.600 に答える
5

これを本当にタイプセーフにしたい場合は、タイプクラスパターンがあなたの友達です:

object Reverse extends App {

  trait Reverser[C] {
    def reverse(xs: C): C
  }

  implicit def List1Reverser[A] = new Reverser[List[A]] {
    def reverse(xs: List[A]) =
      xs.reverse
  }

  implicit def List2Reverser[A] = new Reverser[List[List[A]]] {
    def reverse(xs: List[List[A]]) =
      xs.map(_.reverse).reverse
  }

  implicit def List3Reverser[A] = new Reverser[List[List[List[A]]]] {
    def reverse(xs: List[List[List[A]]]) =
      xs.map(_.map(_.reverse).reverse).reverse
  }

  def deepReverse[A](xs: A)(implicit rev: Reverser[A]): A =
    rev.reverse(xs)

  val xs = List(1,2)
  val xxs = List(List(1,2),List(1,2),List(1,2))
  val xxxs = List(List(List(1,2),List(1,2)),List(List(1,2),List(1,2)),List(List(1,2),List(1,2)))

  println(deepReverse(xs))
  println(deepReverse(xxs))
  println(deepReverse(xxxs))
}

これに関する唯一の問題は、ネストされたリスト型ごとに型クラスが必要なことです。

于 2012-09-28T23:11:25.443 に答える