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

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.