CODEWITHSUNDEEP
javaalgorithmgenerics
SeekingAlpha
SeekingAlpha

Reputation: 7817

Folder: fold method

I came across a problem in Java where I had the following interfaces.

public interface Function2<T, U, R>
{
    R apply(T t, U u);
}

public interface Folder<T, U>
{
    U fold(U u, Queue<T> list, Function2<T,U,U> function);
}

and the question required the developer to implement:

public class MyFolder<T, U> implements Folder<T, U>
{
    public U fold(U u, Queue<T> ts, Function2<T, U, U> function)
    {
        if(u == null || ts == null || function == null)
            throw new IllegalArgumentException();

        if (ts.isEmpty()) {
            return u;
        }

        // The recursive implementation will overflow the stack for
        // any data set of real size, your job is to implement a
        // non-recursive solution
        //return fold(function.apply(ts.poll(), u), ts, function);
        return null;
    }
}

Can someone please explain to me what a fold function does? I cannot seem to find examples online. I have read here about what this method does but it did not give any concrete examples.

Upvotes: 2

Views: 1045

Answers (3)

Elliott Frisch
Elliott Frisch

Reputation: 201507

Fold recursively applies a function to each element, with your code given that would be something like this:

public interface Function2<T, U, R>
{
    R apply(T t, U u);
}

public interface Folder<T, U>
{
    U fold(U u, Queue<T> list, Function2<T,U,U> function);
}
public static class MyFolder<T, U> implements Folder<T, U>
{
    public U fold(U u, Queue<T> ts, Function2<T, U, U> function)
    {
        if(u == null || ts == null || function == null)
            throw new IllegalArgumentException();

        if (ts.isEmpty()) {
            return u;
        }

        return fold(function.apply(ts.poll(), u), ts, function);
    }
}

public static void main(String[] args) {
    Folder<Integer,Integer> fold = new MyFolder<Integer, Integer>();
    Queue<Integer> queue = new LinkedList<Integer>();
    queue.add(1);
    queue.add(2);
    queue.add(3);

    Integer result = fold.fold(0, queue, new Function2<Integer, Integer, Integer>() {
        public Integer apply(Integer a, Integer b) {
            return a + b;
        }
    });
    System.out.println(result);
}

Which outputs

6

The iterative solution should look something like this:

public U fold(U u, Queue<T> ts, Function2<T, U, U> function)
{
    if(u == null || ts == null || function == null)
        throw new IllegalArgumentException();

    if (ts.isEmpty()) {
        return u;
    }

    T item = null;

    while ((item = ts.poll()) != null) {
        u = function.apply(item, u);
    }
    return u;
}

Upvotes: 2

Maurice Perry
Maurice Perry

Reputation: 32841

From wikipedia:

In functional programming, fold – also known variously as reduce, accumulate, aggregate, compress, or inject – refers to a family of higher-order functions that analyze a recursive data structure and recombine through use of a given combining operation the results of recursively processing its constituent parts, building up a return value. Typically, a fold is presented with a combining function, a top node of a data structure, and possibly some default values to be used under certain conditions. The fold then proceeds to combine elements of the data structure's hierarchy, using the function in a systematic way.

http://en.wikipedia.org/wiki/Fold_%28higher-order_function%29

Oh, and the non-recursive equivalent to the implementation in the comment would be:

do {
    u = function.apply(ts.poll(), u);
} while (!ts.isEmpty());
return u;

Upvotes: 2

Tassos Bassoukos
Tassos Bassoukos

Reputation: 16152

As an example, fold(0,{1,2,3,4,5},+) should give as a result 0+1+2+3+4+5 = 15

Upvotes: 0

Related Questions