Реализация функционала fold_right в Java

Question

Я пытаюсь реализовать функциональный метод fold_right, используя некоторые функциональные возможности Java.Приведенный ниже код работает, но я не совсем понимаю, почему это работает - я думаю, что основная проблема в том, что я немного не уверен в том, как работают лямбды в Java (особенно при их использовании сдженерики).Например, почему я должен вызывать лямбда, которую я возвращаю в apply (), снова вызывая apply?Класс, который я беру, преподается в OCaml, и мне легко понять функцию fold_right, которую OCaml имеет в своей стандартной библиотеке.То, как я реализовал это в Java, кажется гораздо более неуклюжим и многословным - может, кто-то может пролить свет на это для меня?

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

interface Func<A,B> {
    B apply(A a);
}

class Add implements Func<Integer, Func<Integer,Integer>> {
    @Override
    public Func<Integer,Integer> apply(Integer a) {
        return (b) -> a + b;
    }
}

public class Fold {
    public static <E> E fold(Func<E,Func<E,E>> f, E acc, LinkedList<E> lst) {
        if (lst.isEmpty()) {
            return acc;
        } else {
            LinkedList<E> listClone = (LinkedList<E>) lst.clone();
            E theHead = listClone.removeFirst();
            return (E) f.apply(theHead).apply((fold(f,acc,listClone)));
        }
    }

    public static void main(String[] args) {
        Integer[] nums = {1,2,3,4,5};
        List<Integer> nums_lst = Arrays.asList(nums);
        LinkedList<Integer> lst = new LinkedList<Integer>(nums_lst);
        int result = Fold.fold(new Add(), 0, lst);
        System.out.println(result);  // should be 15
        System.out.println(lst);  // should be [1,2,3,4,5]
    }
}

Answer 1

Немного не по теме, но в Java есть Function<T, R>, и, как говорится, чтобы понять, как работает код, давайте начнем с интерфейса Func<A, B>:

interface Func<A,B> {
    B apply(A a);
}

Итак, на первый взгляд, у нас есть два типа, а именно A, B, а метод apply говорит мне, что он принимает аргумент типа A и возвращает объект типа B.Итак, переходя к классу Add, этот класс реализует интерфейс Func следующим образом:

Func<Integer, Func<Integer, Integer>>

Итак, основываясь на наших предыдущих рассуждениях, метод apply, реализованный в Add, будет приниматьInteger и вернуть Func<Integer, Integer>.Поэтому, когда мы посмотрим на метод fold в стороне от класса Fold: (вы можете думать о E как о Object для простоты)

public static <E> E fold(Func<E,Func<E,E>> f, E acc, LinkedList<E> lst) {
    if (lst.isEmpty()) {
        return acc;
    } else {
        LinkedList<E> listClone = (LinkedList<E>) lst.clone();
        E theHead = listClone.removeFirst();
        //             A  B <- remember the Func interface? here A is E and B is Func<E,E>
        // f is a Func<E, Func<E, E>> that takes in an E and returns
        // another Func<E, E> after calling apply thus
        // breaking the steps:
        // f.apply(E) <- we just called the apply method thus this should return a "B"
        // Since B is a Func<E, E> we need to call apply to perform the operation
        // onto the next element, which in this case is an addition. You can think
        // of it as a -> b -> a + b. 
        // Now you played that nice trick of using recursion to call this function
        // and traverse all elements till the end of the collection and accumulate
        // all the intermediate results.
        return (E) f.apply(theHead).apply((fold(f,acc,listClone)));
        // the listClone is one element shorter in each recursion
        // since you are removing the first element
    }
}

На заметку, поскольку ваш Func<A, B>, соответствует сигнатуре java.util.Function, которую вы можете передать Add как лямбду без реализации явного класса Add:

public static void main(String[] args) {
    Integer[] nums = {1,2,3,4,5};
    List<Integer> nums_lst = Arrays.asList(nums);
    LinkedList<Integer> lst = new LinkedList<Integer>(nums_lst);
    int result = Fold.fold(a -> b -> a + b, 0, lst);
    System.out.println(result);  // should be 15
    System.out.println(lst);  // should be [1,2,3,4,5]
}