Como você codifica tipos de dados algébricos em uma linguagem semelhante a C # ou Java?

Existem alguns problemas que são facilmente resolvidos por tipos de dados algébricos, por exemplo, um tipo de lista pode ser expresso de maneira muito 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 exemplo específico está em Haskell, mas seria semelhante em outros idiomas com suporte nativo para Tipos de Dados Algébricos.

Acontece que existe um mapeamento óbvio para a subtipo no estilo OO: o tipo de dados se torna uma classe base abstrata e todo construtor de dados se torna uma subclasse concreta. Aqui está um exemplo no 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+)

A única coisa necessária além da subclasse ingênua é uma maneira de selar classes, ou seja, uma maneira de tornar impossível adicionar subclasses a uma hierarquia.

Como você abordaria esse problema em uma linguagem como C # ou Java? Os dois obstáculos que encontrei ao tentar usar tipos de dados algébricos em c # foram:

• Não consegui descobrir como é chamado o tipo inferior em C # (ou seja, não consegui descobrir em que colocar class Empty : ConsList< ??? >)
• Não consegui descobrir uma maneira de selar ConsList para que nenhuma subclasse possa ser adicionada à hierarquia

Qual seria a maneira mais idiomática de implementar tipos de dados algébricos em C # e / ou Java? Ou, se não for possível, qual seria a substituição idiomática?

Existe uma maneira fácil, porém pesada, de selar classes em Java. Você coloca um construtor privado na classe base e cria subclasses com classes 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;
      }
   }
}

Adote um padrão de visitante para envio.

Meu projeto jADT: Java Algebraic DataTypes gera todo esse padrão para você https://github.com/JamesIry/jADT

Você pode conseguir isso usando o padrão de visitante , que complementará a correspondência de padrões. Por exemplo

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

pode ser escrito em 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);
    }
}

A vedação é alcançada pela Visitorclasse. Cada um de seus métodos declara como desconstruir uma das subclasses. Você poderia adicionar mais subclasses, mas isso teria que ser implementado accepte chamado um dos visit...métodos, para que ele tivesse que se comportar como Consou gostar Nil.

Se você abusar dos parâmetros nomeados do C # (introduzidos no C # 4.0), poderá criar tipos de dados algébricos fáceis de combinar:

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

Aqui está a implementação da Eitherclasse:

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

Em C #, você não pode ter esse Emptytipo, porque, devido à reificação, os tipos de base são diferentes para diferentes tipos de membros. Você só pode ter Empty<T>; não é tão útil.

Em Java, você pode ter Empty : ConsListdevido ao apagamento do tipo, mas não tenho certeza se o verificador de tipos não gritaria em algum lugar.

No entanto, como os dois idiomas têm null, você pode pensar em todos os tipos de referência como sendo "Whatever | Null". Então, basta usar o nullcomo "Vazio" para evitar precisar especificar o que deriva.

A única coisa necessária além da subclasse ingênua é uma maneira de selar classes, ou seja, uma maneira de tornar impossível adicionar subclasses a uma hierarquia.

Em Java você não pode. Mas você pode declarar a classe base como pacote privado, o que significa que todas as subclasses diretas devem pertencer ao mesmo pacote que a classe base. Se você declarar as subclasses como finais, elas não poderão mais ser subclasses.

Não sei se isso resolveria o seu problema real ...

O tipo de dados ConsList<A>pode ser representado como uma interface. A interface expõe um deconstructmétodo único que permite "desconstruir" um valor desse tipo - ou seja, manipular cada um dos possíveis construtores. As chamadas para um deconstructmétodo são análogas a um case offormulário em Haskell ou ML.

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

O deconstructmétodo utiliza uma função de "retorno de chamada" para cada construtor no ADT. No nosso caso, é necessária uma função para o caso de lista vazio e outra função para o caso "cons cell".

Cada função de retorno de chamada aceita como argumentos os valores que são aceitos pelo construtor. Portanto, o caso "lista vazia" não aceita argumentos, mas o caso "cons cell" usa dois argumentos: o cabeçalho e o final da lista.

Podemos codificar esses "múltiplos argumentos" usando Tupleclasses ou usando currying. Neste exemplo, eu escolhi usar uma Pairclasse simples .

A interface é implementada uma vez para cada construtor. Primeiro, temos a implementação da "lista vazia". A deconstructimplementação simplesmente chama a emptyCasefunção de retorno de chamada.

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

Em seguida, implementamos o caso "cons cell" da mesma forma. Desta vez, a classe tem propriedades: a cabeça e a cauda da lista não vazia. Na deconstructimplementação, essas propriedades são passadas para a consCasefunção de retorno de chamada.

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

Aqui está um exemplo do uso dessa codificação de ADTs: podemos escrever uma reducefunção que é a lista de dobras comuns.

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

Isso é análogo a esta implementação em Haskell:

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

A única coisa necessária além da subclasse ingênua é uma maneira de selar classes, ou seja, uma maneira de tornar impossível adicionar subclasses a uma hierarquia.

Como você abordaria esse problema em uma linguagem como C # ou Java?

Não há uma boa maneira de fazer isso, mas se você estiver disposto a conviver com uma invasão hedionda, poderá adicionar alguma verificação explícita de tipo ao construtor da classe base abstrata. Em Java, isso seria algo como

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

No C #, é mais complicado por causa dos genéricos reificados - a abordagem mais simples pode ser converter o tipo em uma string e alterá-la.

Observe que em Java, mesmo esse mecanismo pode teoricamente ser ignorado por alguém que realmente deseja através do modelo de serialização ou sun.misc.Unsafe.