Память стиля Haskell в Java

Ответ 1

Хорошо, это убедило меня в том, что функциональное программирование - это, как правило, плохая идея с Java. Отсутствие лени можно обойти, используя ссылочный объект (который по существу реализует лень). Здесь решение:

public static class FunctionRef<A, B> {
    private F<A, B> func;
    public void set(F<A, B> f) { func = f; }
    public F<A, B> get() { return func; }
}

public static class Pair<A, B> {
    public final A first; public final B second;
    public Pair(A a, B b) {
        this.first = a; this.second = b;
    }
}

public static <A, B> F<A, B> memoFix(final F<Pair<FunctionRef<A, B>, A>, B> func) {
    final FunctionRef<A, B> y = new FunctionRef<A, B>();
    y.set(
        memoize(new F<A, B>() {
            @Override
            public B f(A a) {
                return func.f(new Pair<FunctionRef<A, B>, A>(y, a));
            }
        })
    );
    return y.get();
}


//Test that it works
public static void main(String[] args) {
    F<Pair<FunctionRef<Integer, Integer>,Integer>, Integer> fib = new F<Pair<FunctionRef<Integer, Integer>,Integer>, Integer>() {
        @Override
        public Integer f(Pair<FunctionRef<Integer, Integer>, Integer> a) {
            int value = a.second;
            System.out.println("computing fib of " + value);
            if (value == 0) return 0;
            if (value == 1) return 1;
            return a.first.get().f(value - 2) + a.first.get().f(value - 1);
        }
    };

    F<Integer, Integer> memoized = memoFix(fib);
    System.out.println(memoized.f(10));
}

Обратите внимание, что когда программа запускается, она выводит только "вычислительный фид" один раз для каждого значения!

Ответ 2

Библиотека Guava фактически реализует нечто похожее с ее MapMaker:

final Map<Integer, String> memoizingMap = new MapMaker().makeComputingMap(
    new Function<Integer, String>() {
        @Override
        public String apply(final Integer input) {
            System.out.println("Calculating ...");
            return Integer.toHexString(input.intValue());
        }
    });
System.out.println(memoizingMap.get(1));
System.out.println(memoizingMap.get(100));
System.out.println(memoizingMap.get(100000));
System.out.println("The following should not calculate:");
System.out.println(memoizingMap.get(1));

Вывод:

Расчет...
1
Расчет...
64
Расчет...
186a0
Не следует рассчитывать следующее:
1

Самое приятное, что вы можете точно настроить сгенерированную карту для разных аспектов как срок действия, уровень concurrency и т.д.

Ответ 3

Решение memoFix от Joe K было действительно впечатляющим: -)

Для практических целей это, по-видимому, наиболее элегантное решение для рекурсивных (и нерекурсивных) функций, поскольку оно позволяет избежать необходимости в некоторой ссылочной переменной:

import java.util.HashMap;
import java.util.Map;

public abstract class MemoF<A,B> extends F<A,B> {

    private final Map<A, B> map = new HashMap<A, B>();

    @Override
    public B f(A a) {
                B b = map.get(a);
                if (b == null) {
                    b = func(a);
                    map.put(a, b);
                }
                return b;
    }

    public abstract B func(A a);
}

Теперь вам нужно реализовать func, как обычно, за исключением того, что вы никогда не вызываете его рекурсивно, а вызываете f вместо:

F<Integer, BigInteger> memoFib = new MemoF<Integer, BigInteger>(){
    public BigInteger func(Integer a) {
        return a <= 1 ? BigInteger.valueOf(a) : f(a - 1).add(f(a - 2));
    }
};

System.out.println(memoFib.f(100));
//--> 354224848179261915075

Ответ 4

Почему ты застрял? Похоже, вы закончили.

Вы успешно memoized обращаются к функции с помощью карты.

Ответ 5

Вот фрагмент моего недавнего решения по той же самой проблеме:

private final static class MutableFunction<A, B> implements Function<A, B> {
    public Function<A, B> f;

    @Override
    public B apply(A argument) {
        return f.apply(argument);
    }
}

/**
* Computes the fixed point of function f.
* Only terminates successfully if f is non-strict (that is returns without calling its argument).
*/
public static <A, B, R extends Function<A,B>> R fix(final Function<? super Function<A, B>, ? extends R> f) {
    MutableFunction<A, B> mutable = new MutableFunction<A, B>();
    R result = f.apply(mutable);
    mutable.f = result;
    return result;
}

Memofix f является просто a fix(composition(memo, f)), тогда!