Злоупотребление обобщениями для реализации функции составления карри в Java

Question

Итак, немного поиграв с дженериками Java, чтобы глубже понять их возможности, я решил попытаться реализовать карри-версию функции композиции, знакомую функциональным программистам. Compose имеет тип (на функциональных языках) (b -> c) -> (a -> b) -> (a -> c). Выполнение арифметических функций каррирования не было слишком сложным, так как они просто полиморфны, но compose - это функция более высокого порядка, и это доказало свою сложность для моего понимания обобщений в Java.

Вот реализация, которую я создал до сих пор:

public class Currying {

  public static void main(String[] argv){
    // Basic usage of currying
    System.out.println(add().ap(3).ap(4));
    // Next, lets try (3 * 4) + 2
    // First lets create the (+2) function...
    Fn<Integer, Integer> plus2 = add().ap(2);
    // next, the times 3 function
    Fn<Integer, Integer> times3 = mult().ap(3);
    // now we compose them into a multiply by 2 and add 3 function
    Fn<Integer, Integer> times3plus2 = compose().ap(plus2).ap(times3);
    // now we can put in the final argument and print the result
    // without compose:
    System.out.println(plus2.ap(times3.ap(4)));
    // with compose:
    System.out.println(times3plus2.ap(new Integer(4)));
  }

  public static <A,B,C> 
                Fn<Fn<B,C>, // (b -> c) -> -- f
                Fn<Fn<A,B>, // (a -> b) -> -- g
                Fn<A,C>>>   // (a -> c)
                compose(){
    return new  Fn<Fn<B,C>, 
                Fn<Fn<A,B>, 
                Fn<A,C>>> () {
      public Fn<Fn<A,B>, 
             Fn<A,C>> ap(final Fn<B,C> f){
        return new Fn<Fn<A,B>, 
                   Fn<A,C>>() {
          public Fn<A,C> ap(final Fn<A,B> g){
            return new Fn<A,C>(){
              public C ap(final A a){
                return f.ap(g.ap(a));
              }
            };
          }
        };
      }
    };
  }

  // curried addition
  public static Fn<Integer, Fn<Integer, Integer>> add(){
    return new Fn<Integer, Fn<Integer, Integer>>(){
      public Fn<Integer,Integer> ap(final Integer a) {
        return new Fn<Integer, Integer>() {
          public Integer ap(final Integer b){
            return a + b;
          }
        };
      }
    };
  }

  // curried multiplication
  public static Fn<Integer, Fn<Integer, Integer>> mult(){
    return new Fn<Integer, Fn<Integer, Integer>>(){
      public Fn<Integer,Integer> ap(final Integer a) {
        return new Fn<Integer, Integer>() {
          public Integer ap(final Integer b){
            return a * b;
          }
        };
      }
    };
  }
}

interface Fn<A, B> {
  public B ap(final A a);
}

Реализации add, mult и compose прекрасно компилируются, но я сталкиваюсь с проблемой, когда дело доходит до фактического использования compose. Я получаю следующую ошибку для строки 12 (первое использование compose в main):

Currying.java:12: ap(Fn<java.lang.Object,java.lang.Object>) in 
Fn<Fn<java.lang.Object,java.lang.Object>,Fn<Fn<java.lang.Object,java.lang.Object>,Fn<java.lang.Object,java.lang.Object>>>
cannot be applied to (Fn<java.lang.Integer,java.lang.Integer>)
    Fn<Integer,Integer> times3plus2 = compose().ap(plus2).ap(times3);

Я предполагаю, что эта ошибка вызвана тем, что универсальные типы являются инвариантными, но я не уверен, как решить проблему. Из того, что я прочитал, переменные с подстановочными знаками могут использоваться в некоторых случаях для облегчения инвариантности, но я не уверен, как использовать это здесь или даже будет ли это полезно.

Отказ от ответственности: я не собираюсь писать подобный код в любом реальном проекте. Это забавная вещь "это может быть сделано". Кроме того, я сделал имена переменных краткими вопреки стандартной практике Java, потому что в противном случае этот пример становится еще более непонятной стены текста.

Answer 1

Основная проблема здесь заключается в том, что при исходном вызове compose() компилятор не может вывести привязки A, B и C, поэтому он предполагает, что все они равны Object.Вы можете исправить это, указав привязки типов в явном виде:

Fn<Integer, Integer> times3plus2 = 
    Currying.<Integer, Integer, Integer>compose().ap(plus2).ap(times3);

Конечно, тогда вы потеряете ясность, вытекающую из вывода типа.Если вам нужен вывод типа, вы можете определить некоторые промежуточные классы, чтобы сделать вывод:

public static ComposeStart compose() {
    return new ComposeStart();
}

class ComposeStart {
    public <B,C> ComposeContinuation<B,C> ap(Fn<B,C> f) {
        return new ComposeContinuation<B, C>(f);
    }
}

class ComposeContinuation<B, C> {
    private final Fn<B,C> f;

    ComposeContinuation(Fn<B,C> f) {
        this.f = f;
    }

    public <A> Fn<A,C> ap(final Fn<A,B> g) {
        return new Fn<A,C>() {
            public C ap(A a) {
                return f.ap(g.ap(a));
            }
        };
    }
}

Однако, тогда промежуточные шаги каррирования больше не будут Fn с.

Answer 2

Я сам реализовал эту функцию в терминах общей последовательности вызовов функций длины n.

public static final <X, Y> Chainer<X, Y> chain(
        final Function<X, Y> primary
) {
    return new Chainer<X, Y>(primary);
}

private static final class FunctionChain<IN, OUT> implements Function<IN, OUT> {

    @SuppressWarnings("rawtypes")
    private final List<Function> chain =  new LinkedList<Function>();

    private FunctionChain(@SuppressWarnings("rawtypes") final List<Function> chain) {
        this.chain.addAll(chain);
    }

    @SuppressWarnings("unchecked")
    @Override
    public OUT apply(final IN in) {
        Object ret = in;
        for (final Function<Object, Object> f : chain) {
            ret = f.apply(ret);
        }
        return (OUT) ret;
    }
}

public static final class Chainer<IN, OUT> {
    @SuppressWarnings("rawtypes")
    private final LinkedList<Function> functions = new LinkedList<Function>();

    @SuppressWarnings("unchecked")
    private Chainer(@SuppressWarnings("rawtypes") final Function func) {
        then(func);
    }

    @SuppressWarnings("unchecked")
    public <OUT2> Chainer<IN, OUT2> then(final Function<OUT, OUT2> func) {
        if (func instanceof FunctionChain) {
            functions.addAll(((FunctionChain<?, ?>)func).chain);
        } else {
            functions.add(func);
        }
        return (Chainer<IN, OUT2>) this;
    }

    @SuppressWarnings("unchecked")
    public Function<IN, OUT> build() {
        // If empty, it's a noop function. If one element, there's no need for a chain.
        return new FunctionChain<IN, OUT>(functions);
    }
}

public static final <X, Y, Z> Function<X, Z> combine(
        final Function<X, Y> primary,
        final Function<Y, Z> secondary
) {
    return chain(primary).then(secondary).build();
}

Я бы сказал, что это квалифицируется как большее злоупотребление обобщениями, поскольку только класс Chainerиспользует универсальные средства, чтобы гарантировать, что последующие вызовы .then () правильно набраны на основе последней предоставленной функции, а функции просто сохраняются в списке в том, что, как известно, является безопасным порядком вызова на будущее, но это работаетхорошо обобщить: цепочка (первая) .then (вторая) .then (третья) .then (четвертая) .build () полностью подходит для этого подхода.guava, но должен нормально переноситься на любой интерфейс Function.

Answer 3

Благодаря пониманию Рассела Захнисера, что я не предоставляю достаточно информации для работы с Java, я немного изменил компоновку, чтобы мы создали экземпляр объекта «Composer» с соответствующими переменными типа. Вот мое текущее рабочее решение :

interface Fn<A, B> {
  public B ap(final A a);
}

public class Currying {

  public static void main(String[] argv){
    // Basic usage of currying
    System.out.println(add().ap(3).ap(4));
    // Next, lets try (3 * 4) + 2
    // First lets create the (+2) function...
    Fn<Integer, Integer> plus2 = add().ap(2);
    // next, the times 3 function
    Fn<Integer, Integer> times3 = mult().ap(3);
    // now we compose them into a multiply by 2 and add 3 function
    Fn<Integer, Integer> times3plus2 = new Composer<Integer,Integer,Integer>()
      .compose().ap(plus2).ap(times3);
    // without compose
    System.out.println(plus2.ap(times3.ap(4)));
    // with compose
    System.out.println(times3plus2.ap(4));
  }

  static class Composer<A,B,C> { 
    public
      Fn<Fn<B,C>, // (b -> c) -> -- f
      Fn<Fn<A,B>, // (a -> b) -> -- g
      Fn<A,C>>>   // (a -> c)
      compose(){
      return new Fn<Fn<B,C>, 
        Fn<Fn<A,B>, 
        Fn<A,C>>> () {
        public Fn<Fn<A,B>, 
          Fn<A,C>> ap(final Fn<B,C> f){
          return new Fn<Fn<A,B>, 
            Fn<A,C>>() {
            public Fn<A,C> ap(final Fn<A,B> g){
              return new Fn<A,C>(){
                public C ap(final A a){
                  return f.ap(g.ap(a));
                }
              };
            }
          };
        }
      };
    }
  }

  public static Fn<Integer, Fn<Integer, Integer>> add(){
    return new Fn<Integer, Fn<Integer, Integer>>(){
      public Fn<Integer,Integer> ap(final Integer a) {
        return new Fn<Integer, Integer>() {
          public Integer ap(final Integer b){
            return a + b;
          }
        };
      }
    };
  }

  public static Fn<Integer, Fn<Integer, Integer>> mult(){
    return new Fn<Integer, Fn<Integer, Integer>>(){
      public Fn<Integer,Integer> ap(final Integer a) {
        return new Fn<Integer, Integer>() {
          public Integer ap(final Integer b){
            return a * b;
          }
        };
      }
    };
  }
}