Add a basic fixpoint function

This adds a 'fixpoint' function which allows you to create recursive
lambda functions more easily

2 files changed, 75 insertions, 0 deletions

diff --git a/src/example/java/bjc/functypes/FixpointExample.java b/src/example/java/bjc/functypes/FixpointExample.java
new file mode 100644
index 0000000..8d3e658
--- /dev/null
+++ b/src/example/java/bjc/functypes/FixpointExample.java
@@ -0,0 +1,17 @@
+package bjc.functypes;
+
+import java.util.function.*;
+
+public class FixpointExample {
+ public static void main(String[] args) {
+	 BiFunction<Integer, Function<Integer, Integer>, Integer> func 
+	 = (input, self) -> {
+		 if (input <= 1) return 1;
+		 else            return input * self.apply(input - 1);
+	 };
+	 
+	 Function<Integer, Integer> factorial = Fixpoints.fix(func);
+	 
+	 for (int i = 0; i < 10; i++) System.out.println(factorial.apply(i));
+ }
+}
diff --git a/src/main/java/bjc/functypes/Fixpoints.java b/src/main/java/bjc/functypes/Fixpoints.java
new file mode 100644
index 0000000..f62969c
--- /dev/null
+++ b/src/main/java/bjc/functypes/Fixpoints.java
@@ -0,0 +1,58 @@
+package bjc.functypes;
+
+import java.util.*;
+import java.util.function.*;
+
+import bjc.data.*;
+
+/**
+ * Function combinators to form 'fixpoints' or recursive functions.
+ * 
+ * @author Ben Culkin
+ *
+ */
+public interface Fixpoints {
+	/**
+	 * Convert a two-argument function to a single argument recursive one.
+	 * 
+	 * @param <InputType> The input type for the function.
+	 * @param <ReturnType> The output type for the function.
+	 * 
+	 * @param func The function to make recursive.
+	 * 
+	 * @return The newly recursive function.
+	 */
+	static <InputType, ReturnType> Function<InputType, ReturnType> fix(
+			BiFunction<InputType, Function<InputType, ReturnType>, ReturnType> func) {
+		IHolder<Function<InputType, ReturnType>> inner = IHolder.of(null);
+		inner.replace((arg) -> {
+			return func.apply(arg, inner.getValue());
+		});
+		return inner.getValue();
+	}
+	
+	/**
+	 * Convert a two-argument function to a single argument recursive memoized one.
+	 * 
+	 * @param <InputType> The input type for the function.
+	 * @param <ReturnType> The output type for the function.
+	 * 
+	 * @param func The function to make recursive.
+	 * 
+	 * @return The newly recursive memoized function.
+	 */
+	static <InputType, ReturnType> Function<InputType, ReturnType> memoFix(
+			BiFunction<InputType, Function<InputType, ReturnType>, ReturnType> func) {
+		Map<InputType, ReturnType> memoMap = new HashMap<>();
+		
+		IHolder<Function<InputType, ReturnType>> inner = IHolder.of(null);
+		inner.replace((arg) ->
+			memoMap.computeIfAbsent(
+					arg,
+					(newArg) -> func.apply(newArg, inner.getValue())
+			)
+		);
+		
+		return inner.getValue();
+	}
+}