Add a basic fixpoint function

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

1 files changed, 58 insertions, 0 deletions

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();
+	}
+}