Scalaでネストされたリストの深い逆転

Question

私は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のリストとTsのリストを任意の深さまで取得する関数が必要です。私は他の場所で見た例に基づいてそれを行うケースクラスを作ろうとしました。 Anyを返すだけでAnyを受け付ける関数は欲しくない。それは不正行為のように感じる。

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

まだ、私はバランスを取るために私のタイプを得ることができませんでした。私はScalaの新機能ですが、再帰と型付けを混乱させる絶好の機会になると思いました。

Answer 1

それは実際に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) 

当社rev方法で暗黙の引数evがAそのものであるという証拠であります可逆であり、evがヌルの場合、そうでないことを意味します。 Aが可逆であるという証拠がある場合は、それを使用してList[A]（これはmapのことです）の要素を逆にしてから、リスト自体を逆にします。この証拠がない場合（getOrElseの場合）、リストを逆にすることができます。

我々はこのように（おそらくもっとperformantlyけど）少し簡潔revを書くことができます：2つのバージョンのいずれかをテストするには

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 
    } 
} 

、我々は次のように記述することができます。

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メソッドでデフォルト引数のトリックを使用する方がより簡潔です（そして私の目には明確です）。しかし、他の人のコードで他のバージョンを見る可能性が高くなります。

Answer 2

あなたは、これは本当に型保証されていたい場合は、型クラスのパターンはあなたの友達です：

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)) 
} 

これで唯一の問題は、あなたがネストされた各リストの種類の型クラスを必要とするということです。