Cách an toàn, kiểu an toàn để làm phẳng các bộ sưu tập tùy ý lồng nhau trong Scala?

Question

Thỉnh thoảng tôi dành chút thời gian để chơi với Scala, có sự pha trộn các tính năng hấp dẫn tôi mặc dù không có khả năng sử dụng nó trong công việc của riêng tôi (cho đến nay). Đối với đá tôi quyết định thử một số ít nhất 99 Haskell Problems theo cách chung nhất có thể - vận hành và trả lại bất kỳ loại bộ sưu tập phù hợp nào. Một vài câu hỏi đầu tiên không quá khó, nhưng tôi thấy mình hoàn toàn bị ám ảnh bởi flatten. Tôi chỉ không thể tìm ra cách gõ một thứ như thế.

Để cụ thể về câu hỏi của tôi: bạn có thể viết một hàm an toàn loại làm phẳng tự động được lồng nhau SeqLike s không? Vì vậy mà, nói,

flatten(List(Array(List(1, 2, 3), List(4, 5, 6)), Array(List(7, 8, 9), List(10, 11, 12)))) 

sẽ trở

List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12): List[Int] 

? Lưu ý rằng đây không phải là câu hỏi tương tự như trong bộ vấn đề Haskell và Scala; Tôi đang cố gắng viết một hàm làm phẳng các danh sách không đồng nhất nhưng đúng hơn là các chuỗi đồng nhất nhưng được lồng nhau.

Tìm kiếm trên web Tôi tìm thấy một số translation into Scala của câu hỏi đó, nhưng nó hoạt động và trả về Danh sách [Mọi]. Tôi có chính xác rằng điều này sẽ yêu cầu một số loại đệ quy? Hay tôi làm điều này khó hơn nó?

Answer 1

Các công trình sau đây trong Scala 2.10.0-M7. Bạn sẽ cần phải thêm trường hợp bổ sung cho Array hỗ trợ, và có lẽ tinh chỉnh nó để có các loại bộ sưu tập đầu ra cụ thể hơn, nhưng tôi đoán nó đều có thể được thực hiện bắt đầu từ đây:

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) 

Answer 2

Bạn đang đối mặt với cùng một vấn đề mà họ mô tả trong Haskell solution: Không có dị tính List trong Scala. May mắn là bạn có thể đi theo con đường chính xác mà họ đang đi trong giải pháp Haskell.

Xác định một số kiểu dữ liệu mà có thể được lồng vào nhau:

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

Và sau đó viết một hàm flatten chung cho loại đó:

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 
} 

hoặc thậm chí

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

Cách sử dụng:

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

Tất nhiên, chúng tôi cũng có thể thêm phương thức này làm phương thức trực tiếp vào đặc điểm NestedList.

Answer 3

Nó có vẻ như là điều phải làm là chỉ cần gọi .flatten đúng số lần:

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) 

Kể từ Scala được đánh máy, bạn luôn biết trước thời hạn sâu như thế nào làm tổ đi cho biến cụ thể. Vì bạn biết điều này trước thời hạn, không có nhiều giá trị trong việc xử lý cấu trúc tùy ý như thể bạn không chắc chắn bao nhiêu lần .flatten cần thiết để được gọi.