Advertisement
DulcetAirman

Y Combinator in Java

Oct 14th, 2017
574
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.87 KB | None | 0 0
  1. package ch.claude_martin;
  2.  
  3. import java.util.function.*;
  4.  
  5. /**
  6.  * My Y Combinator can handle any reference type (primitives will be auto-boxed,
  7.  * that's why I can use <code>long/Long</code> here). However, since I'm using
  8.  * {@link UnaryOperator}, the recursive function must return the same type as
  9.  * it's (second) argument. Factorial is a good example of this. Instead of long,
  10.  * it could take a {@link java.math.BigInteger} and also return one.
  11.  *
  12.  */
  13. public class YComb {
  14.     /**
  15.      * This is the <i>recursive</i> type of the function that will apply itself to
  16.      * itself. This is how the recursion work.s A function needs itself as the first
  17.      * parameter, so it then can call itself recursively.
  18.      * <p>See this partial application in the code below:<br/>
  19.      * <code>b -> b.apply(b)</code>
  20.      */
  21.     interface Fn2Op<T> extends Function<Fn2Op<T>, UnaryOperator<T>> {
  22.     }
  23.  
  24.     /** Prints the factorial of <code>args[0]</code>.*/
  25.     public static void main(String args[]) {
  26.         final UnaryOperator<UnaryOperator<Long>> factorial =
  27.                     f -> n -> (n == 0) ? 1L : n * f.apply(n - 1);
  28.         System.out.println(apply(factorial, Long.parseLong(args[0])));
  29.     }
  30.  
  31.     /**
  32.      * Takes any <i>recursive</i> function (which takes itself and an argument) and
  33.      * argument and returns the result. The argument and the return value are of the
  34.      * same type <code>T</code>.
  35.      *
  36.      * @param <T> The type of <code>arg</code> and return value
  37.      * @param fn The recursive function (in curried form)
  38.      * @param arg The argument for the function
  39.      * @return the result of applying <code>arg</code> to <code>fn</code>
  40.      */
  41.     private static <T> T apply(UnaryOperator<UnaryOperator<T>> fn, T arg) {
  42.         return ((Function<UnaryOperator<UnaryOperator<T>>, UnaryOperator<T>>)
  43.                 a -> ((Fn2Op<T>) b -> b.apply(b))
  44.                 .apply(
  45.                     c -> a.apply(
  46.                         x -> c.apply(c).apply(x)
  47.                     )
  48.                 )).apply(fn).apply(arg);
  49.     }
  50. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement