스칼라에서 중첩 목록의 역방향 처리

Question

저는 스칼라에서 재귀 적으로 목록의 목록을 뒤집고 싶습니다.

내가 작성한 깊은 목록은 다음과 같이 파이썬으로 반전 :

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

어떻게 스칼라에 해당 할 것? 문제는 알고리즘이 아니에요. 제가 더 새로운 타입의 물건입니다.

[T] 또는 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) 

암시 인수 ev 우리 rev 방법을 증거 A 자체가된다는 점이다 되돌릴 수 있고, ev이 null 인 경우 이는 의미가 없습니다. A이 되돌릴 수 있다는 증거가있는 경우 List[A]의 요소를 뒤집을 때 사용합니다 (map이 수행하는 것입니다). 그런 다음 목록 자체를 뒤집습니다. 우리가이 증거 (getOrElse 경우)를 가지고 있지 않다면, 우리는 그 목록을 되돌릴 수 있습니다.

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) 

로 :

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

이 두 버전 중 하나를 테스트하려면, 우리는 다음과 같은 작성할 수 있습니다

우리는 rev 좀 덜 간결하게 (그러나 아마도 더 performantly)과 같이 쓸 수있다 예상했다.

---

나는 다음과 같은 좀 더 일반적인 관용구가 바로 이런 경우에 implicits를 얻기위한 것이라고 추가해야합니다 :

우리가 같은 수준에 listReverser 및 nestedListReverser를 작성하려는 경우

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._ 

, 두 가지를 우선 순위에 대한 표준 접근 방식은

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)(_ + _)) 

가 낮은 우선 순위의 꼬마 도깨비를 넣어 : 우리는 목록의 목록을 반대 할 때 우리는 다음과 같은 오류를 얻을 것 특성 ( WhateverLow)에 부합하고 그 특성을 확장하는 대상 ( WhateverHigh)에 다른 것.이와 같은 비교적 간단한 경우에는 위의 내 rev 메서드에서 기본 인수 트릭을 사용하는 것이 더 간결합니다. 그러나 다른 사람의 코드에서 다른 버전을 볼 가능성이 더 큽니다.

Answer 2

당신 싶어 정말 형태 보증 된 다음이가있는 경우 typeclass 패턴이 당신의 친구입니다 :

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

이 유일한 문제는 각 중첩 된 목록 유형에 대한 typeclass을 필요로한다는 것입니다.