java - 在Java中实现函数fold_right

Question

我正在尝试使用 Java 的一些函数特性来实现函数方法 Fold_right。我下面的代码可以工作，但我并不真正理解为什么它可以工作 - 我认为主要问题是我有点不确定 lambda 在 Java 中如何工作(特别是在将它们与泛型一起使用时)。例如，为什么我必须通过再次调用 apply 来调用在 apply() 中返回的 lambda？我正在上的类(class)是用 OCaml 授课的，我很容易理解 OCaml 标准库中的 Fold_right 函数。我在 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):

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作为 lambda 而不实现 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]
}