Come si codificano i tipi di dati algebrici in un linguaggio C#- o Java?

Question

Ci sono alcuni problemi che sono facilmente risolti dai tipi di dati algebrici, ad esempio un tipo di elenco può essere espresso in modo molto succinto come:

data ConsList a = Empty | ConsCell a (ConsList a)

consmap f Empty          = Empty
consmap f (ConsCell a b) = ConsCell (f a) (consmap f b)

l = ConsCell 1 (ConsCell 2 (ConsCell 3 Empty))
consmap (+1) l

Questo particolare esempio è in Haskell, ma sarebbe simile in altre lingue con supporto nativo per tipi di dati algebrici.

Si scopre che esiste un'ovvia mappatura nel sottotyping in stile OO: il tipo di dati diventa una classe di base astratta e ogni costruttore di dati diventa una sottoclasse concreta. Ecco un esempio in Scala:

sealed abstract class ConsList[+T] {
  def map[U](f: T => U): ConsList[U]
}

object Empty extends ConsList[Nothing] {
  override def map[U](f: Nothing => U) = this
}

final class ConsCell[T](first: T, rest: ConsList[T]) extends ConsList[T] {
  override def map[U](f: T => U) = new ConsCell(f(first), rest.map(f))
}

val l = (new ConsCell(1, new ConsCell(2, new ConsCell(3, Empty)))
l.map(1+)

L'unica cosa necessaria oltre la sottoclasse ingenua è un modo per sigillo Classi, cioè un modo per rendere impossibile aggiungere sottoclassi a una gerarchia.

Come affronteresti questo problema in una lingua come C# o Java? I due ostacoli che ho trovato quando ho provato a utilizzare i tipi di dati algebrici in C# erano:

• Non riuscivo a capire come si chiama il tipo inferiore in C# (cioè non riuscivo a capire cosa mettere in class Empty : ConsList< ??? >)
• Non riuscivo a trovare un modo per farlo sigillo ConsList in modo che non possano essere aggiunte sottoclassi alla gerarchia

Quale sarebbe il modo più idiomatico per implementare i tipi di dati algebrici in C# e/o Java? Oppure, se non è possibile, quale sarebbe la sostituzione idiomatica?