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

Hay algunos problemas que los tipos de datos algebraicos pueden resolver fácilmente, por ejemplo, un tipo de lista puede expresarse de manera muy sucinta como:

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

Este ejemplo particular está en Haskell, pero sería similar en otros idiomas con soporte nativo para tipos de datos algebraicos.

Resulta que hay un mapeo obvio para el subtipo de estilo OO: el tipo de datos se convierte en una clase base abstracta y cada constructor de datos se convierte en una subclase concreta. Aquí hay un ejemplo en 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+)

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ías este problema en un lenguaje como C # o Java? Los dos escollos que encontré al intentar usar tipos de datos algebraicos en C # fueron:

• No pude averiguar cómo se llama el tipo de fondo en C # (es decir, no pude averiguar en qué poner class Empty : ConsList< ??? >)
• No pude encontrar una manera de sellar ConsList para que no se puedan agregar subclases a la jerarquía

¿Cuál sería la forma más idiomática de implementar tipos de datos algebraicos en C # y / o Java? O, si no es posible, ¿cuál sería el reemplazo idiomático?

Hay una manera fácil, pero pesada, de sellar las clases en Java. Pones un constructor privado en la clase base y luego haces subclases de 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;
      }
   }
}

Agregue un patrón de visitante para su envío.

Mi proyecto jADT: Java Algebraic DataTypes genera toda esa plantilla para ti https://github.com/JamesIry/jADT

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 por la Visitorclase. 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 accepty llamando a uno de los visit...métodos, por lo que tendría que comportarse como Conso como Nil.

Si abusa de los parámetros con nombre C # (introducidos en C # 4.0), puede crear tipos de datos algebraicos que sean fáciles de combinar 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 Eitherclase:

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 Emptytipo 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, puede Empty : ConsListdeberse a la eliminación de tipo, pero no estoy seguro de si el verificador de tipo no gritaría en alguna parte.

Sin embargo, dado que ambos idiomas tienen null, puede pensar en todos sus tipos de referencia como "Cualquiera | Nulo". Por lo tanto, utilizaría el nullcomo "Vacío" para evitar tener que especificar de qué 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 declaras las subclases como finales, no se pueden subclasificar más.

Sin embargo, 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 único deconstructmétodo que le permite "deconstruir" un valor de ese tipo, es decir, manejar cada uno de los posibles constructores. Las llamadas a un deconstructmétodo son análogas a un case offormulario en Haskell o ML.

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

El deconstructmétodo 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 la 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 acepta el constructor. Entonces, el caso de la "lista vacía" no toma argumentos, pero el caso de la "celda de contras" toma dos argumentos: el encabezado y el final de la lista.

Podemos codificar estos "argumentos múltiples" usando Tupleclases, o usando curry. En este ejemplo, elegí usar una Pairclase simple .

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

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 "cons cell" de manera similar. Esta vez la clase tiene propiedades: el encabezado y la cola de la lista no vacía. En la deconstructimplementación, esas propiedades se pasan a la consCasefunción de devolución de llamada.

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

Aquí hay un ejemplo del uso de esta codificación de ADT: podemos escribir una reducefunción 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ías 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, entonces puedes agregar alguna comprobación de tipo explícito 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 destrozar eso.

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