Exercise 4.5

[pr-lawrence]

In chapter 5, you’ll develop the process of reversing the list by implementing fold- Left in terms of foldRight, and foldRight in terms of foldLeft. But this shows that the recursive implementation of foldRight won’t be optimal because reverse is an O(n) operation: the time needed to execute it is proportional to the number of ele- ments in the list, because you must traverse the list. By using reverse, you double this time by traversing the list twice. The conclusion is that when considering using fold- Right, you should do one of the following:  Not care about performance  Change the function (if possible) and use foldLeft  Use foldRight only with small lists  Use an imperative implementation

    /**
     * foldRight - stack-based 재귀 버전
     *
     * @param ts
     * @param identity
     * @param f
     * @param <T>
     * @param <U>
     * @return
     */
    public static <T, U> U foldRight(List<T> ts, U identity, Function<T, Function<U, U>> f) {
        return ts.isEmpty()
                ? identity
                : f.apply(head(ts)).apply(foldRight(tail(ts), identity, f));
    }

    /**
     * foldRight - tail call. But this doesn't work.
     * @param acc
     * @param ts
     * @param identity
     * @param f
     * @param <T>
     * @param <U>
     * @return
     */
    public static <T, U> U foldRight2(U acc, List<T> ts, U identity, Function<T, Function<U, U>> f) {
        return ts.isEmpty()
                ? acc
                : foldRight2(f.apply(head(ts)).apply(acc), tail(ts), identity, f);
    }

(1 + (2 + (3 + (4 + (5 + 0)))))
(5 + (4 + (3 + (2 + (1 + 0)))))