Tipos de unión/suma etiquetados en Java

¿Hay alguna forma de definir un tipo de suma en Java? Java parece admitir naturalmente tipos de productos directamente, y pensé que las enumeraciones podrían permitirle admitir tipos de suma, y ​​parece que la herencia podría hacerlo, pero hay al menos un caso que no puedo resolver. Para elaborar, un tipo de suma es un tipo que puede tener exactamente uno de un conjunto de diferentes tipos, como una unión etiquetada en C. En mi caso, estoy tratando de implementar el tipo de Haskell en Java:

data Either a b = Left a | Right b

pero en el nivel base tengo que implementarlo como un tipo de producto y simplemente ignorar uno de sus campos:

public class Either<L,R>
{
    private L left = null;
    private R right = null;

    public static <L,R> Either<L,R> right(R right)
    {
        return new Either<>(null, right);
    }

    public static <L,R> Either<L,R> left(L left)
    {
        return new Either<>(left, null);
    }

    private Either(L left, R right) throws IllegalArgumentException
    {
        this.left = left;
        this.right = right;
        if (left != null && right != null)
        {
            throw new IllegalArgumentException("An Either cannot be created with two values");
        }
        if (left == right)
        {
            throw new IllegalArgumentException("An Either cannot be created without a value");
        }
    }

    .
    .
    .
}

Intenté implementar esto con herencia, pero tengo que usar un parámetro de tipo comodín, o equivalente, que los genéricos de Java no permitirán:

public class Left<L> extends Either<L,?>

No he usado mucho los Enums de Java, pero aunque parecen ser los siguientes mejores candidatos, no tengo esperanzas.
En este punto, creo que esto solo podría ser posible tipeando Object valores, que espero evitar por completo, a menos que haya una manera de hacerlo una vez, de manera segura, y poder usar eso para todos los tipos de suma.

Hacer Either una clase abstracta sin campos y solo un constructor (privado, sin argumentos, vacío) y anide sus “constructores de datos” (left y right métodos de fábrica estáticos) dentro de la clase para que puedan ver el constructor privado pero nada más puede, sellando efectivamente el tipo.

Usa un método abstracto either para simular una coincidencia de patrones exhaustiva, reemplazando adecuadamente en los tipos concretos devueltos por los métodos de fábrica estáticos. Implementar métodos de conveniencia (como fromLeft, fromRight, bimap, first, second) en términos de either.

import java.util.Optional;
import java.util.function.Function;

public abstract class Either<A, B> {
    private Either() {}

    public abstract <C> C either(Function<? super A, ? extends C> left,
                                 Function<? super B, ? extends C> right);

    public static <A, B> Either<A, B> left(A value) {
        return new Either<A, B>() {
            @Override
            public <C> C either(Function<? super A, ? extends C> left,
                                Function<? super B, ? extends C> right) {
                return left.apply(value);
            }
        };
    }

    public static <A, B> Either<A, B> right(B value) {
        return new Either<A, B>() {
            @Override
            public <C> C either(Function<? super A, ? extends C> left,
                                Function<? super B, ? extends C> right) {
                return right.apply(value);
            }
        };
    }

    public Optional<A> fromLeft() {
        return this.either(Optional::of, value -> Optional.empty());
    }
}

¡Agradable y seguro! No hay manera de arruinarlo. Debido a que el tipo está efectivamente sellado, puede estar seguro de que solo habrá dos casos y, en última instancia, cada operación debe definirse en términos de either método, que obliga a la persona que llama a manejar ambos casos.

Con respecto al problema que tuviste tratando de hacer class Left<L> extends Either<L,?>considere la firma <A, B> Either<A, B> left(A value). El parámetro de tipo B no aparece en la lista de parámetros. Entonces, dado un valor de algún tipo Apuedes obtener un Either<A, B> por ningún escribe B.

Una forma estándar de codificar tipos de suma es la codificación Boehm-Berarducci (a menudo denominada por el nombre de su prima, codificación Church) que representa un tipo de datos algebraico como su eliminador, es decir, una función que hace coincidir patrones. En Haskell:

left :: a -> (a -> r) -> (b -> r) -> r
left x l _ = l x

right :: b -> (a -> r) -> (b -> r) -> r
right x _ r = r x

match :: (a -> r) -> (b -> r) -> ((a -> r) -> (b -> r) -> r) -> r
match l r k = k l r

-- Or, with a type synonym for convenience:

type Either a b r = (a -> r) -> (b -> r) -> r

left :: a -> Either a b r
right :: b -> Either a b r
match :: (a -> r) -> (b -> r) -> Either a b r -> r

En Java, esto se vería como un visitante:

public interface Either<A, B> {
    <R> R match(Function<A, R> left, Function<B, R> right);
}

public final class Left<A, B> implements Either<A, B> {

    private final A value;

    public Left(A value) {
        this.value = value;
    }

    public <R> R match(Function<A, R> left, Function<B, R> right) {
        return left.apply(value);
    }

}

public final class Right<A, B> implements Either<A, B> {

    private final B value;

    public Right(B value) {
        this.value = value;
    }

    public <R> R match(Function<A, R> left, Function<B, R> right) {
        return right.apply(value);
    }

}

Ejemplo de uso:

Either<Integer, String> result = new Left<Integer, String>(42);
String message = result.match(
  errorCode -> "Error: " + errorCode.toString(),
  successMessage -> successMessage);

Para mayor comodidad, puede hacer una fábrica para crear Left y Right valores sin tener que mencionar los parámetros de tipo cada vez; También puede agregar una versión de match que acepta Consumer<A> left, Consumer<B> right en vez de Function<A, R> left, Function<B, R> right si desea la opción de coincidencia de patrones sin producir un resultado.

Muy bien, entonces la solución de herencia es definitivamente la más prometedora. Lo que nos gustaría hacer es class Left<L> extends Either<L, ?>, que desafortunadamente no podemos hacer debido a las reglas genéricas de Java. Sin embargo, si hacemos las concesiones de que el tipo de Left o Right debe codificar la posibilidad “alternativa”, podemos hacer esto.

public class Left<L, R> extends Either<L, R>`

Ahora, nos gustaría poder convertir Left<Integer, A> a Left<Integer, B>ya que en realidad no usar ese segundo tipo de parámetro. Podemos definir un método para hacer esta conversión internamente, codificando así esa libertad en el sistema de tipos.

public <R1> Left<L, R1> phantom() {
  return new Left<L, R1>(contents);
}

Ejemplo completo:

public class EitherTest {

  public abstract static class Either<L, R> {}

  public static class Left<L, R> extends Either<L, R> {

    private L contents;

    public Left(L x) {
      contents = x;
    }

    public <R1> Left<L, R1> phantom() {
      return new Left<L, R1>(contents);
    }

  }

  public static class Right<L, R> extends Either<L, R> {

    private R contents;

    public Right(R x) {
      contents = x;
    }

    public <L1> Right<L1, R> phantom() {
      return new Right<L1, R>(contents);
    }

  }

}

Por supuesto, querrá agregar algunas funciones para acceder realmente a los contenidos y para verificar si un valor es Left o Right para que no tengas que rociar instanceof y moldes explícitos en todas partes, pero esto debería ser suficiente para comenzar, como mínimo.

Herencia pueden puede usarse para emular tipos de suma (uniones disjuntas), pero hay algunos problemas con los que debe lidiar:

1. Debe tener cuidado de evitar que otros agreguen nuevos casos a su tipo. Esto es especialmente importante si desea manejar exhaustivamente cada caso que pueda encontrar. Es posible con una superclase no final y un constructor privado de paquete.
2. La falta de parches de patrones hace bastante difícil consumir un valor de este tipo. Si desea una forma verificada por el compilador para garantizar que ha manejado exhaustivamente todos los casos, debe implementar una función de coincidencia usted mismo.
3. Estás obligado a usar uno de los dos estilos de API, ninguno de los cuales es ideal:
   • Todos los casos implementan una API común, arrojando errores en la API que no son compatibles. Considerar Optional.get(). Idealmente, este método solo estaría disponible en un tipo disjunto cuyo valor se sabe que es some más bien que none. Pero no hay forma de hacerlo, por lo que es un miembro de instancia de un general Optional escribe. tira NoSuchElementException si lo llama en un opcional cuyo “caso” es “ninguno”.
   • Cada caso tiene una API única que le dice exactamente de lo que es capaz, pero eso requiere una verificación de tipo manual y conversión cada vez que desee llamar a uno de estos métodos específicos de subclase.
4. Cambiar “casos” requiere una nueva asignación de objetos (y agrega presión sobre el GC si se hace con frecuencia).

TL; DR: la programación funcional en Java no es una experiencia agradable.

Qué tal si

import java.util.Optional;

public interface Either<L, R> {
  default Optional<L> left() { return Optional.empty();}
  default Optional<R> right() { return Optional.empty();}

  static <L, R> Either<L, R> fromLeft(L left) {
    return new Either<L, R>() {
      @Override public Optional<L> left() { return Optional.of(left); }
    };
  }

  static <L, R> Either<L, R> fromRight(R right) {
    return new Either<L, R>() {
      @Override public Optional<R> right() { return Optional.of(right); }
    };
  }
}

La diferencia con otras soluciones propuestas aquí no es profunda, sino estilística.

Permítanme sugerir una solución muy diferente, que no haga uso de herencia/clases abstractas/interfaces. En el lado negativo, requiere algo de esfuerzo para cada nuevo “tipo de suma” definido. Sin embargo, creo que tiene muchas ventajas: es seguro, solo usa conceptos básicos, se siente natural de usar y permite más de 2 “subtipos”.

Aquí hay una prueba de concepto para árboles binarios porque es más práctico que “Cualquiera”, pero puede usar los comentarios como guía para construir su propio tipo de suma.

public class Tree {

// 1) Create an enum listing all "subtypes" (there may be more than 2)
enum Type { Node, Leaf }

// 2) Create a static class for each subtype (with the same name for clarity)
public static class Node {
    
    Tree l,r;
    
    public Node(Tree l, Tree r) {
        
        this.l = l;
        this.r = r;
    }
    
}

public static class Leaf {
    
    int label;
    
    public Leaf(int label) {
        this.label = label;
    }
    
}

// 3) Each instance must have:
// One variable to indicate which subtype it corresponds to
Type type;

// One variable for each of the subtypes (only one will be different from null)
Leaf leaf;
Node node;

// 4) Create one constructor for each subtype (it could even be private)
public Tree(Node node) {
    
    this.type = Type.Node;
    this.node = node;
    
}

// 5) Create one "factory" method for each subtype (not mandatory but quite convenient)
public static Tree newNode(Tree l, Tree r) {
    return new Tree(new Node(l,r));
}

public Tree(Leaf leaf) {
    
    this.type = Type.Leaf;
    this.leaf = leaf;
    
}

public static  Tree newLeaf(int label) {
    return new Tree(new Leaf(label));
}

// 6) Create a generic "matching" function with one argument for each subtype
// (the constructors ensure that no "null pointer exception" can be raised)
public <T> T match(Function<Node,T> matchNode, Function<Leaf,T> matchLeaf) {
    
    switch (type) {
    case Node:
        return matchNode.apply(node);
    case Leaf:
        return matchLeaf.apply(leaf);
    }
    return null;
    
}

// 7) Have fun !
// Note that matchings are quite natural to write.
public int size() {
    
    return match(
            node -> 1 + node.l.size() + node.r.size(),
            leaf -> 1
    );
    
}

public String toString() {
    
    return match(
            node -> {
                String sl = node.l.toString();
                String sr = node.r.toString();
                return "Node { "+sl+" , "+sr+" }";
            },
            leaf -> "Leaf: "+leaf.label
    );
    
}


public static void main(String [] args) {
    
    Tree node1 = Tree.newNode(Tree.newLeaf(1),Tree.newLeaf(2));
    Tree node2 = Tree.newNode(node1,Tree.newLeaf(3));
    
    System.out.println(node2.size());
    System.out.println(node2);
    
}
}

Siéntase libre de expresar críticas, estoy genuinamente interesado en este tema y estaré feliz de aprender más.