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

58

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?

Jörg W Mittag
fuente
3
C # es lenguaje OOP. Resuelve problemas usando OOP. No intentes usar ningún otro paradigma.
Eufórico el
77
@Euphoric C # se ha convertido en un lenguaje funcional bastante utilizable con C # 3.0. Funciones de primera clase, operaciones funcionales comunes incorporadas, mónadas.
Mauricio Scheffer
2
@Euphoric: algunos dominios son fáciles de modelar con objetos y difíciles de modelar con tipos de datos algebraicos, algunos son lo contrario. Saber cómo hacer ambas cosas le brinda más flexibilidad para modelar su dominio. Y como dije, mapear los tipos de datos algebraicos a los conceptos típicos de OO no es tan complejo: el tipo de datos se convierte en una clase base abstracta (o una interfaz, o un rasgo abstracto), los constructores de datos se convierten en subclases de implementación concretas. Eso te da un tipo de datos algebraico abierto. Las restricciones a la herencia le dan un tipo de datos algebraico cerrado. El polimorfismo te da discriminación de casos.
Jörg W Mittag
3
@Eufórico, paradigma, schmaradigm, ¿a quién le importa? Los ADT son ortogonales a la programación funcional (o POO o cualquier otra cosa). Codificar un AST de cualquier idioma es bastante difícil sin el soporte de ADT decente, y compilar ese lenguaje es un dolor sin otra característica agnóstica de paradigma, la coincidencia de patrones.
SK-logic

Respuestas:

42

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

James Iry
fuente
2
¡De alguna manera no me sorprende ver tu nombre aparecer aquí! Gracias, no conocía este idioma.
Jörg W Mittag
44
Cuando dijiste "repetitivo pesado", estaba preparado para algo mucho peor ;-) Java puede ser bastante malo con repetitivo, a veces.
Joachim Sauer
pero esto no se compone: no tienes forma de especializar el tipo A sin tener que afirmarlo a través de un elenco (creo)
nicolas
Desafortunadamente, esto parece incapaz de representar algunos tipos de suma más complejos, por ejemplo Either. Ver mi pregunta
Zoey Hewll
20

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.

Petr Pudlák
fuente
13

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);
    }
}
Joey Adams
fuente
He visto una versión Java de esta técnica antes, pero las lambdas y los parámetros con nombre la hacen mucho más legible. +1!
Doval
1
Creo que el problema aquí es que Right no es genérico sobre el tipo de error. Algo así como: class Right<R> : Either<Bot,R>donde Either se cambia a una interfaz con parámetros de tipo covariante (out), y Bot es el tipo inferior (subtipo de cualquier otro tipo, opuesto a Object). No creo que C # tenga un tipo inferior.
croyd
5

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.

Jan Hudec
fuente
El problema nulles que es demasiado general: representa la ausencia de algo , es decir, el vacío en general, pero quiero representar la ausencia de elementos de la lista, es decir, una lista vacía en particular. Una lista vacía y un árbol vacío deben tener distintos tipos. Además, la lista vacía debe ser un valor real porque todavía tiene un comportamiento propio, por lo que debe tener sus propios métodos. Para construir la lista [1, 2, 3], quiero decir Empty.prepend(3).prepend(2).prepend(1)(o en un lenguaje con operadores asociativos correctos 1 :: 2 :: 3 :: Empty), pero no puedo decir null.prepend ….
Jörg W Mittag
@ JörgWMittag: los valores nulos tienen tipos distintos. También puede crear fácilmente una constante escrita con un valor nulo para ese propósito. Pero es cierto que no se pueden llamar métodos. Su enfoque con métodos no funciona sin un vacío específico de tipo de elemento de todos modos.
Jan Hudec
algunos métodos de extensión astutos pueden falsificar llamadas de 'método' en nulos (por supuesto, todo es realmente estático)
jk.
Puede tener operadores de conversión implícitos an Emptyy an Empty<>y abusos para permitir una simulación bastante práctica, si lo desea. Básicamente, se usa Emptyen código, pero todas las firmas de tipo, etc., solo usan variantes genéricas.
Eamon Nerbonne
3

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 ...

Stephen C
fuente
No tengo un problema real, o habría publicado esto en StackOverflow, no aquí :-) Una propiedad importante de los tipos de datos algebraicos es que pueden cerrarse , lo que significa que el número de casos es fijo: en este ejemplo , una lista está vacía o no lo está. Si puedo asegurar estáticamente que este es el caso, entonces puedo hacer conversiones dinámicas o intanceofverificaciones dinámicas "pseudo-type-safe" (es decir: sé que es seguro, incluso si el compilador no lo hace), simplemente asegurándome de que siempre revisa esos dos casos. Sin embargo, si alguien agrega una nueva subclase, entonces puedo obtener errores de tiempo de ejecución que no esperaba.
Jörg W Mittag
@ JörgWMittag - Bueno, Java claramente no es compatible con eso ... en el sentido estricto de que pareces querer. Por supuesto, puede hacer varias cosas para bloquear subtipos no deseados en tiempo de ejecución, pero luego obtiene "errores de tiempo de ejecución que no espera".
Stephen C
3

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
jameshfisher
fuente
Enfoque interesante, muy agradable! Puedo ver la conexión con F # Active Patterns y Scala Extractors (y probablemente también haya un enlace a Haskell Views, del cual no sé nada, desafortunadamente). No había pensado en trasladar la responsabilidad de la coincidencia de patrones sobre los constructores de datos a la propia instancia de ADT.
Jörg W Mittag
2

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.

Peter Taylor
fuente
1
No sería más complicado en C #:Type type = this.GetType(); if (type != typeof(Empty<T>) && type != typeof(ConsCell<T>)) throw new Exception();
svick
@svick, bien observado. No estaba teniendo en cuenta que el tipo base estaría parametrizado.
Peter Taylor
¡Brillante! Supongo que esto es lo suficientemente bueno para hacer una "verificación manual de tipo estático". Estoy buscando eliminar errores de programación honestos en lugar de intenciones maliciosas.
Jörg W Mittag