tipo di scrittura algebrica dei dati a Scala

Question

In Haskell, posso definire un Tree:

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

Come potrei scrivere questo a Scala?

non sono sicuro di come mantenere il parametro di tipo [A] a Scala per Node per abbinare Tree s' tipo, a.

Answer 1

Definizione di un ADT

Nel modello di "oggetto-funzionale" della Scala, si definisce un trait che rappresenta l'ADT e tutti i suoi parametri. Quindi, per ciascuno dei casi, si definisce uno case class o uno case object. I parametri di tipo e valore sono trattati come argomenti per il costruttore della classe. In genere, si crea il tratto sealed in modo che nulla al di fuori del file corrente possa aggiungere casi.

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] 

allora si può fare:

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

È un po 'fastidioso che dobbiamo creare un insieme di nuove Empty casi, quando la classe non trasporta i dati. In Scala, è prassi comune sostituire un argomento zero case class, come Empty, con un case object, anche se in questo caso è un po 'complicato, perché uno case object è un singleton, ma abbiamo bisogno di un Empty per ogni tipo di albero.

Per fortuna (o meno, a seconda di chi si chiede), con un'annotazione di covarianza, si può avere uno case object Empty agire come il vuoto Tree di tipo Nothing, che è sottotipo universale di Scala. A causa di covarianza, questo Empty ora è un sottotipo di Tree[A] per tutti i possibili 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] 

Quindi si ottiene la sintassi più pulito:

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

Questo è, infatti, quanti libreria standard di Scala Nil opere , rispetto a List.

operativo a un ADT

Per utilizzare il nuovo ADT, è comune a Scala per definire funzioni ricorsive che utilizzano la parola chiave match di decostruire esso. Vedi:

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 dà caratteristicamente lo sviluppatore una sconcertante serie di opzioni tra cui scegliere a come organizzare la funzionalità che opera su ADT. Posso pensare a quattro approcci di base.

1) Si può rendere una funzione autonoma esterna al tratto:

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

Questo potrebbe essere bello se si desidera che l'API per sentirsi più funzionale di object-oriented, o se il funzionamento di un prodotto potrebbe istanza del tuo ADT da altri dati. Il companion object è spesso un posto naturale dove mettere questi metodi.

2) Si può rendere un metodo concreto del tratto stesso:

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] 

Ciò è particolarmente utile se l'operazione può essere definito solo in termini di altri metodi della trait, nel qual caso probabilmente non utilizzerà esplicitamente match.

3) Si può rendere un metodo astratto del carattere con le implementazioni concrete nei sottotipi (ovviando alla necessità di utilizzare 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) 
} 

Questo è più simile al tradizionale approccio polimorfismo orientato agli oggetti . Mi sembra naturale quando definisco le operazioni di basso livello di trait, con funzionalità più dettagliate definite in termini di queste operazioni nello stesso trait. È anche più appropriato quando si lavora con tratti che non sono sealed.

4) In alternativa, nel caso in cui si desidera aggiungere un metodo per un ADT la cui fonte è esterna al progetto, è possibile utilizzare una conversione implicita per un nuovo tipo che ha il metodo:

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

Questo è un modo particolarmente pratico per migliorare i tipi definiti nel codice che non controlli, per tenere conto del comportamento ausiliario dei tuoi tipi in modo che possano essere focalizzati sul comportamento di base o per facilitare ad hoc polymorphism.

Metodo 1 è una funzione che prende uno Tree e funziona come il primo esempio. I metodi 2-4 sono tutte le operazioni su un Tree:

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