Some ADTs in Scala.

ADTs.scala

sealed trait Either[S, T] {

  def fold[X]: (S => X) => (T => X) => X

  def map[X]: (T => X) => Either[S, X]

  def bind[X]: (T => Either[S, X]) => Either[S, X]
}

object Either {

  def Left[S, T]: S => Either[S, T] =
    s => new Either[S, T] {

      def fold[X]: (S => X) => (T => X) => X =
        f => _ => f(s)

      def map[X]: (T => X) => Either[S, X] =
        _ => Either.Left[S, X](s)

      def bind[X]: (T => Either[S, X]) => Either[S, X] =
        _ => Either.Left[S, X](s)
    }

  def Right[S, T]: T => Either[S, T] =
    t => new Either[S, T] {

      def fold[X]: (S => X) => (T => X) => X =
        _ => f => f(t)

      def map[X]: (T => X) => Either[S, X] =
        f => Either.Right[S, X](f(t))

      def bind[X]: (T => Either[S, X]) => Either[S, X] =
        k => k(t)
    }
}

sealed trait Pair[S, T] {

  def fold[X]: (S => T => X) => X

  def map[X]: (T => X) => Pair[S, X]

  def bind[X]: (T => Pair[S, X]) => Pair[S, X]
}

object Pair {

  def apply[S, T]: S => T => Pair[S, T] =
    s => t => new Pair[S, T] {

      def fold[X]: (S => T => X) => X =
        f => f(s)(t)

      def map[X]: (T => X) => Pair[S, X] =
        f => Pair(s)(f(t))

      def bind[X]: (T => Pair[S, X]) => Pair[S, X] =
        k => k(t)
    }
}

sealed trait Maybe[T] {

  def fold[X]: X => (T => X) => X

  def map[X]: (T => X) => Maybe[X]

  def bind[X]: (T => Maybe[X]) => Maybe[X]
}

object Maybe {

  def Nothing[T]: Maybe[T] =
    new Maybe[T] {

      def fold[X]: X => (T => X) => X =
        x => _ => x

      def map[X]: (T => X) => Maybe[X] =
        _ => Maybe.Nothing

      def bind[X]: (T => Maybe[X]) => Maybe[X] =
        _ => Maybe.Nothing
    }

  def Just[T]: T => Maybe[T] =
    t => new Maybe[T] {

      def fold[X]: X => (T => X) => X =
        _ => f => f(t)

      def map[X]: (T => X) => Maybe[X] =
        f => Maybe.Just(f(t))

      def bind[X]: (T => Maybe[X]) => Maybe[X] =
        k => k(t)
    }
}

sealed trait List[T] {

  def fold[X]: (T => X => X) => X => X

  def map[X]: (T => X) => List[X]

  def bind[X]: (T => List[X]) => List[X]
}

object List {

  def Nil[T]: List[T]
    = new List[T] {

      def fold[X]: (T => X => X) => X => X =
        _ => x => x

      def map[X]: (T => X) => List[X] =
        _ => List.Nil

      def bind[X]: (T => List[X]) => List[X] =
        _ => List.Nil
    }

  def Cons[T]: T => List[T] => List[T] =
    t => ts => new List[T] {

      def fold[X]: (T => X => X) => X => X =
        g => x => g(t)(ts.fold(g)(x))

      def map[X]: (T => X) => List[X] =
        f => List.Cons(f(t))(ts.map(f))

      def bind[X]: (T => List[X]) => List[X] =
        k => k(t).fold(List.Cons)(ts.bind(k))
    }
}

Written in the trait/object idiom followed by Argonaut and by Scrooge. By "trait/object idiom" i mean that (1) there is no (public) class defining instances of the datatype, (2) the trait specifies extractors, and (3) the object specifies constructors. Additionally in these examples, the trait defines no fields, only methods, so the resulting instances are immutable.

Left to do: (1) meditate on whether the arguments to the various constructors and eliminators should be lazy, (2) meditate on whether standard tools such as equality checks, to string methods, read-from-string methods, and the likes (all the things you derive in Haskell) belong here or belong in another object.

The constructors and extractors are analogous to the introduction rules and elimination rules of formal logics. I mean "analogous" in the strongest possible sense, i.e., they are the same, modulo a recasting of terminology.