¿Cómo se codifican los tipos de datos algebraicos en un lenguaje C # o similar a Java?

Hay una forma sencilla, pero repetitiva, de sellar clases en Java. Coloca un constructor privado en la clase base y luego crea subclases en sus clases internas.

public abstract class List<A> {

   // private constructor is uncallable by any sublclasses except inner classes
   private List() {
   }

   public static final class Nil<A> extends List<A> {
   }

   public static final class Cons<A> extends List<A> {
      public final A head;
      public final List<A> tail;

      public Cons(A head, List<A> tail) {
         this.head = head;
         this.tail = tail;
      }
   }
}

Tachuela en un patrón de visitante para el envío.

Mi proyecto jADT: Java Algebraic DataTypes genera todo lo que usted prepara enlace

Puede lograr esto utilizando el patrón de visitante , que complementará la coincidencia de patrones. Por ejemplo

data List a = Nil | Cons { value :: a, sublist :: List a }

Se puede escribir en Java como

interface List<T> {
    public <R> R accept(Visitor<T,R> visitor);

    public static interface Visitor<T,R> {
        public R visitNil();
        public R visitCons(T value, List<T> sublist);
    }
}

final class Nil<T> implements List<T> {
    public Nil() { }

    public <R> R accept(Visitor<T,R> visitor) {
        return visitor.visitNil();
    }
}
final class Cons<T> implements List<T> {
    public final T value;
    public final List<T> sublist;

    public Cons(T value, List<T> sublist) {
        this.value = value;
        this.sublist = sublist;
    }

    public <R> R accept(Visitor<T,R> visitor) {
        return visitor.visitCons(value, sublist);
    }
}

El sellado se logra mediante la clase Visitor . Cada uno de sus métodos declara cómo deconstruir una de las subclases. Podría agregar más subclases, pero tendría que implementar accept y llamando a uno de los métodos visit... , por lo que tendría que comportarse como Cons o como Nil .

Si abusa de los parámetros con nombre de C # (introducidos en C # 4.0), puede hacer que los tipos de datos algebraicos sean fáciles de hacer coincidir en:

Either<string, string> e = MonthName(2);

// Match with no return value.
e.Match
(
    Left: err => { Console.WriteLine("Could not convert month: {0}", err); },
    Right: name => { Console.WriteLine("The month is {0}", name); }
);

// Match with a return value.
string monthName =
    e.Match
    (
        Left: err => null,
        Right: name => name
    );
Console.WriteLine("monthName: {0}", monthName);

Aquí está la implementación de la clase Either :

public abstract class Either<L, R>
{
    // Subclass implementation calls the appropriate continuation.
    public abstract T Match<T>(Func<L, T> Left, Func<R, T> Right);

    // Convenience wrapper for when the caller doesn't want to return a value
    // from the match expression.
    public void Match(Action<L> Left, Action<R> Right)
    {
        this.Match<int>(
            Left: x => { Left(x); return 0; },
            Right: x => { Right(x); return 0; }
        );
    }
}

public class Left<L, R> : Either<L, R>
{
    L Value {get; set;}

    public Left(L Value)
    {
        this.Value = Value;
    }

    public override T Match<T>(Func<L, T> Left, Func<R, T> Right)
    {
        return Left(Value);
    }
}

public class Right<L, R> : Either<L, R>
{
    R Value { get; set; }

    public Right(R Value)
    {
        this.Value = Value;
    }

    public override T Match<T>(Func<L, T> Left, Func<R, T> Right)
    {
        return Right(Value);
    }
}

En C #, no puede tener ese tipo Empty porque, debido a la reificación, los tipos base son diferentes para los diferentes tipos de miembros. Solo puedes tener Empty<T> ; no es tan útil.

En Java, puedes tener Empty : ConsList debido al borrado de tipo, pero no estoy seguro de que el verificador de tipos no grite en ninguna parte.

Sin embargo, dado que ambos idiomas tienen null , puede pensar en todos sus tipos de referencia como "Whatever | Null". Así que solo usarías null como "Vacío" para evitar tener que especificar lo que se deriva.

  

Lo único que se necesita más allá de las subclases ingenuas es una forma de sellar clases, es decir, una forma de hacer que sea imposible agregar subclases a una jerarquía.

En Java no puedes. Pero puede declarar la clase base como paquete privado, lo que significa que todas las subclases directas deben pertenecer al mismo paquete que la clase base. Si luego declara que las subclases son finales, no se pueden subclasificar más.

Aunque no sé si esto resolvería tu problema real ...

El tipo de datos ConsList<A> se puede representar como una interfaz. La interfaz expone un solo método deconstruct que le permite "deconstruir" un valor de ese tipo, es decir, manejar cada uno de los posibles constructores. Las llamadas a un método deconstruct son análogas a una forma case of en Haskell o ML.

interface ConsList<A> {
  <R> R deconstruct(
    Function<Unit, R> emptyCase,
    Function<Pair<A,ConsList<A>>, R> consCase
  );
}

El método deconstruct toma una función de "devolución de llamada" para cada constructor en el ADT. En nuestro caso, toma una función para el caso de lista vacía, y otra función para el caso de "celda de contras".

Cada función de devolución de llamada acepta como argumentos los valores que son aceptados por el constructor. Por lo tanto, el caso de "lista vacía" no requiere argumentos, pero el caso de "celda contraria" toma dos argumentos: el encabezado y la cola de la lista.

Podemos codificar estos "múltiples argumentos" usando Tuple classes, o usando currying. En este ejemplo, elegí usar una clase simple Pair .

La interfaz se implementa una vez para cada constructor. Primero, tenemos la implementación para la "lista vacía". La implementación deconstruct simplemente llama a la función de devolución de llamada emptyCase .

class ConsListEmpty<A> implements ConsList<A> {
  public ConsListEmpty() {}

  public <R> R deconstruct(
    Function<Unit, R> emptyCase,
    Function<Pair<A,ConsList<A>>, R> consCase
  ) {
    return emptyCase.apply(new Unit());
  }
}

Luego implementamos el caso de "celda de contras" de manera similar. Esta vez la clase tiene propiedades: la cabecera y la cola de la lista no vacía. En la implementación deconstruct , esas propiedades se pasan a la función de devolución de llamada consCase .

class ConsListConsCell<A> implements ConsList<A> {
  private A head;
  private ConsList<A> tail;

  public ConsListCons(A head, ConsList<A> tail) {
    this.head = head;
    this.tail = tail;
  }

  public <R> R deconstruct(
    Function<Unit, R> emptyCase,
    Function<Pair<A,ConsList<A>>, R> consCase
  ) {
    return consCase.apply(new Pair<A,ConsList<A>>(this.head, this.tail));
  }
}

Este es un ejemplo del uso de esta codificación de ADT: podemos escribir una función reduce , que es la lista de plegado habitual.

<T> T reduce(Function<Pair<T,A>,T> reducer, T initial, ConsList<T> l) {
  return l.deconstruct(
    ((unit) -> initial),
    ((t) -> reduce(reducer, reducer.apply(initial, t.v1), t.v2))
  );
}

Esto es análogo a esta implementación en Haskell:

reduce reducer initial l = case l of
  Empty -> initial
  Cons t_v1 t_v2  -> reduce reducer (reducer initial t_v1) t_v2

  

Lo único que se necesita más allá de las subclases ingenuas es una forma de sellar clases, es decir, una forma de hacer que sea imposible agregar subclases a una jerarquía.

     

¿Cómo abordaría este problema en un lenguaje como C # o Java?

No hay una buena manera de hacer esto, pero si estás dispuesto a vivir con un truco horrible, puedes agregar una comprobación explícita de tipos al constructor de la clase base abstracta. En Java, esto sería algo así como

protected ConsList() {
    Class<?> clazz = getClass();
    if (clazz != Empty.class && clazz != ConsCell.class) throw new Exception();
}

En C # es más complicado debido a los genéricos reificados: el enfoque más simple podría ser convertir el tipo en una cadena y manipular eso.

Tenga en cuenta que, en Java, incluso este mecanismo puede ser ignorado teóricamente por alguien que realmente quiere hacerlo a través del modelo de serialización o sun.misc.Unsafe .