From e3810fbf9b7d207e13b93f4d8698454abe78683f Mon Sep 17 00:00:00 2001
From: Ben Culkin <scorpress@gmail.com>
Date: Sat, 21 Nov 2020 11:03:25 -0500
Subject: Add a basic fixpoint function

This adds a 'fixpoint' function which allows you to create recursive
lambda functions more easily
---
 .../java/bjc/functypes/FixpointExample.java        | 17 +++++++
 src/main/java/bjc/functypes/Fixpoints.java         | 58 ++++++++++++++++++++++
 2 files changed, 75 insertions(+)
 create mode 100644 src/example/java/bjc/functypes/FixpointExample.java
 create mode 100644 src/main/java/bjc/functypes/Fixpoints.java

(limited to 'src')

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();
+	}
+}
-- 
cgit v1.2.3