Loại Viết đại số dữ liệu trong Scala

Question

Trong Haskell, tôi có thể xác định một Tree:

data Tree a = Empty | Node a (Tree a) (Tree a)

Làm thế nào tôi có thể viết này trong Scala?

Tôi không chắc chắn cách giữ thông số loại [A] trong Scala cho Node để khớp với loại Tree, a.

Answer 1

Xác định một ADT

Trong mô hình "đối tượng chức năng" Scala, bạn định nghĩa một trait đại diện cho ADT và tất cả các thông số của nó. Sau đó, đối với mỗi trường hợp của bạn, bạn xác định hoặc là case class hoặc case object. Các tham số kiểu và giá trị được coi là đối số cho hàm tạo lớp. Thông thường, bạn tạo đặc điểm sealed để không có gì ngoài tệp hiện tại có thể thêm trường hợp.

sealed trait Tree[A] 
case class Empty[A]() extends Tree[A] 
case class Node[A](value: A, left: Tree[A], right: Tree[A]) extends Tree[A] 

Sau đó, bạn có thể làm:

scala> Node("foo", Node("bar", Empty(), Empty()), Empty()) 
res2: Node[String] = Node(foo,Node(bar,Empty(),Empty()),Empty()) 

Đó là loại gây phiền nhiễu mà chúng ta phải tạo ra một bó toàn bộ Empty trường mới, khi lớp đó không mang dữ liệu. Trong Scala, thực tế phổ biến là thay thế một số không đối số case class, như Empty, với case object, mặc dù trong trường hợp này, nó hơi phức tạp, vì case object là một singleton, nhưng chúng ta cần Empty cho mọi loại cây. May mắn (hoặc không, tùy thuộc vào người bạn yêu cầu), với chú thích hiệp phương sai, bạn có thể có một case object Empty hoạt động như trống Tree loại Nothing, là loại phụ phổ quát của Scala. Do hiệp phương sai, Empty này bây giờ là một subtype của Tree[A] cho tất cả các thể A:

sealed trait Tree[+A] 
case object Empty extends Tree[Nothing] 
case class Node[A](value: A, left: Tree[A], right: Tree[A]) extends Tree[A] 

Sau đó, bạn sẽ có được cú pháp sạch hơn:

scala> Node("foo", Node("bar", Empty, Empty), Empty) 
res4: Node[String] = Node(foo,Node(bar,Empty,Empty),Empty) 

Đây là, trên thực tế, làm thế nào thư viện chuẩn Scala của Nil công trình , đối với List.

hoạt động trên một ADT

Để sử dụng ADT mới, đó là phổ biến ở Scala để xác định chức năng đệ quy có sử dụng các từ khóa để match mổ xẻ nó. Xem:

scala> :paste 
// Entering paste mode (ctrl-D to finish) 

import scala.math.max 
def depth[A](tree: Tree[A]): Int = tree match { 
    case Empty => 0 
    case Node(_, left, right) => 1 + max(depth(left), depth(right)) 
} 

// Exiting paste mode, now interpreting. 

import scala.math.max 
depth: [A](tree: Tree[A])Int 

scala> depth(Node("foo", Node("bar", Empty, Empty), Empty)) 
res5: Int = 2 

Scala đặc trưng cung cấp cho nhà phát triển một loạt các tùy chọn để tổ chức chức năng hoạt động trên ADT. Tôi có thể nghĩ đến bốn phương pháp cơ bản.

1) Bạn có thể làm cho nó một chức năng độc lập bên ngoài để các đặc điểm:

sealed trait Tree[+A] 
case object Empty extends Tree[Nothing] 
case class Node[A](value: A, left: Tree[A], right: Tree[A]) extends Tree[A] 

object Tree { 
    def depth[A](tree: Tree[A]): Int = tree match { 
    case Empty => 0 
    case Node(_, left, right) => 1 + max(depth(left), depth(right)) 
    } 
} 

Điều này có thể được tốt đẹp nếu bạn muốn API của bạn cảm thấy chức năng hơn, hoặc nếu hoạt động một sản phẩm sức hướng đối tượng của bạn ví dụ về ADT của bạn từ các dữ liệu khác. Các companion object thường là một nơi tự nhiên để đưa các phương pháp như vậy.

2) Bạn có thể làm cho nó một phương pháp cụ thể của đặc điểm riêng của mình:

sealed trait Tree[+A] { 
    def depth: Int = this match { 
    case Empty => 0 
    case Node(_, left, right) => 1 + max(left.depth, right.depth) 
    } 
} 
case object Empty extends Tree[Nothing] 
case class Node[A](value: A, left: Tree[A], right: Tree[A]) extends Tree[A] 

Điều này đặc biệt hữu ích nếu hoạt động của bạn có thể được định nghĩa đơn thuần về mặt phương pháp khác của trait, trong trường hợp bạn có thể mà sẽ không sử dụng rõ ràng match.

3) Bạn có thể làm cho nó trở thành một phương pháp trừu tượng của các đặc điểm với triển khai cụ thể trong phân nhóm (obviating nhu cầu sử dụng match):

sealed trait Tree[+A] { 
    def depth: Int 
} 
case object Empty extends Tree[Nothing] { 
    val depth = 0 
} 
case class Node[A](value: A, left: Tree[A], right: Tree[A]) extends Tree[A] { 
    def depth = 1 + max(left.depth, right.depth) 
} 

Đây là giống nhất với cách tiếp cận truyền thống đa hình hướng đối tượng . Tôi cảm thấy tự nhiên khi xác định các hoạt động cấp thấp của trait, với chức năng phong phú hơn được xác định theo các hoạt động này trong chính số trait. Nó cũng phù hợp nhất khi làm việc với các đặc điểm không phải là sealed.

4) Hoặc, trong trường hợp bạn muốn thêm một phương pháp để một ADT mà nguồn là bên ngoài để dự án của bạn, bạn có thể sử dụng một chuyển đổi ngầm cho một loại mới có phương pháp:

// assuming Tree defined elsewhere 
implicit class TreeWithDepth[A](tree: Tree[A]) { 
    def depth: Int = tree match { 
    case Empty => 0 
    case Node(_, left, right) => 1 + max(left.depth, right.depth) 
    } 
} 

Đây là một cách đặc biệt hữu ích để tăng cường các loại được xác định trong mã bạn không kiểm soát, để tính toán hành vi phụ của các loại của bạn để chúng có thể tập trung vào hành vi cốt lõi hoặc để tạo điều kiện cho ad hoc polymorphism.

Phương pháp 1 là hàm cần có Tree và hoạt động như ví dụ đầu tiên. Phương pháp 2-4 là toàn bộ hoạt động trên một Tree:

scala> Node("foo", Node("bar", Empty, Empty), Empty).depth 
res8: Int = 2