ADTs in F# and Scala

Question

What are the key differences between ADTs in F# and Scala? Is there anything that F#'s ADTs can do but Scala's ADTs cannot (and vice versa)?

Answer 1

First, there is nothing a language can, the other cannot.

What differs is the style.

I read a little bit Scala, but cannot write. I think binary search tree is a good example to compare the ADT style.

This is the code from http://aperiodic.net/phil/scala/s-99/:

package binarytree {

  sealed abstract class Tree[+T]

  case class Node[+T](value: T, left: Tree[T], right: Tree[T]) extends Tree[T] {
    override def toString = "T(" + value.toString + " " + left.toString + " " + right.toString + ")"
  }

  case object End extends Tree[Nothing] {
    override def toString = "."
  }

  object Node {
    def apply[T](value: T): Node[T] = Node(value, End, End)
  }
}

We can see that the style is quite OO.

Following is the main part of my code for Treap ( a balanced binary search tree ):

module Treap = 

    type node<'T> = {left: treap<'T>; right: treap<'T>; value: 'T; priority:int}
    and treap<'T>  = Empty | Node of node<'T>

    let rec lookup (k:'a) (t:'a treap) =
        match t with
            | Empty -> None
            | Node(n) -> 
                if k = n.value then Some(k)
                elif k < n.value then lookup k (n.left)
                else lookup k (n.right)

    let add (k:'a) (p:int) (tree:'a treap) = 
        let rotate xv xp yv yp a b c =
            if xp < yp then
                {value=xv; priority=xp; left=a; right=Node({value=yv;priority=yp;left=b;right=c})}
            else
                {value=yv; priority=yp; right=c; left=Node({value=xv; priority=xp; left=a; right=b})}

        let rec addNode (k:'a) (p:int) (tree:'a treap) = 
            match tree with
            | Empty -> {value=k; priority=p; left=Empty; right=Empty}, false
            | Node(n) ->
                if k=n.value then
                    n, true
                elif k<n.value then
                    let {value=xv; priority=xp; left=a; right=b}, dup = addNode k p (n.left) 
                    (rotate xv xp (n.value) (n.priority) a b (n.right)), dup
                else
                    let {value=yv; priority=yp; left=b; right=c}, dup = addNode k p (n.right)
                    (rotate (n.value) (n.priority) yv yp (n.left) b c), dup

        let n, dup = addNode k p tree
        Node(n)

I think Scala can also write in this style. However, Scala is more OO.

Answer 2

Conceptually, I think that both languages provide the same power - in F# you can declare ADTs using discriminated unions and in Scala, you can use case classes. The declaration in Scala using classes may get a little bit longer than the F# version (as pointed out by Yin Zhu), but then you can use pattern matching with similar elegancy in both of the languages.

Here is an example (from this article) of simplifying terms:

def simplify(term: Term) = term match {
  case Mul(Num(0), x) => Num(0)
  case Mul(Num(1), x) => x
  case _ => term
}

The same code in F# using match would look very similar:

let simplify term = 
  match term with 
  | Mul(Num(0), x) -> Num(0)
  | Mul(Num(1), x) -> x
  | _ -> term

Differences I think there are a few differences when it comes to more advanced (related) features.

• In Scala, each case is also a type, so you can for example define a method that takes Num or Mul as an argument. In F#, this is not possible, because Num and Mul are just constructors of type Term. I suppose this may be sometimes useful, but most of the time, you'll work with values of type Term anyway.

• Related to the previous point - in Scala, you can also define methods for individual cases. You can for example define a method in the Num class. In F#, all members have to be members of the Term type.

• In F#, you can use active patterns to hide the internal representation of the type (e.g. when exporting it from a module). This is very useful for library design. For example, you can define active patterns:

  val (|Mul|_|) // return Some(..) if Term represents multiplication
  val (|Num|_|) // return Some(..) if Term represents number
  

  The internal representation can change over time without affecting the library interface, so you can for example implement the interface like this:

  type Term = Binary of string * Term * Term | Num of int
  let (|Num|_|) = function Num n -> Some n | _ -> None 
  let (|Mul|_|) = function Binary("*", a, b) -> Some(a, b) | _ -> None
  

Answer 3

I believe Scala supports co- and contravariance but F# does not (yet).