A bit of fun with the Y combinator
Samuel Dennis Borlongan
srborlongan at gmail.com
Wed Sep 11 01:40:05 PDT 2013
I've made a variant:
http://rosettacode.org/wiki/Y_combinator#Java
Please note that Y::main's combinator and fixedPoint variables are actually
unneeded; they only serve as a way to use the Y combinator without making
the coder's eyes bleed (more).
Also, I would recommend using Stream<STUFF> over STUFF..., since Stream.of
exists, and type safety in generic arrays doesn't.
import java.util.function.Function;
@FunctionalInterface
public interface SelfApplicable<OUTPUT> extends
Function<SelfApplicable<OUTPUT>, OUTPUT> {
public default OUTPUT selfApply() {
return apply(this);
}
}
import java.util.function.Function;
import java.util.function.UnaryOperator;
@FunctionalInterface
public interface FixedPoint<FUNCTION> extends
Function<UnaryOperator<FUNCTION>, FUNCTION> {}
import java.util.Arrays;
import java.util.Optional;
import java.util.function.Function;
import java.util.function.BiFunction;
@FunctionalInterface
public interface VarargsFunction<INPUTS, OUTPUT> extends
Function<INPUTS[], OUTPUT> {
@SuppressWarnings
<http://java.sun.com/j2se/1.5.0/docs/api/java/lang/SuppressWarnings.html>("unchecked")
public OUTPUT apply(INPUTS... inputs);
public static <INPUTS, OUTPUT> VarargsFunction<INPUTS, OUTPUT>
from(Function<INPUTS[], OUTPUT> function) {
return function::apply;
}
public static <INPUTS, OUTPUT> VarargsFunction<INPUTS, OUTPUT>
upgrade(Function<INPUTS, OUTPUT> function) {
return inputs -> function.apply(inputs[0]);
}
public static <INPUTS, OUTPUT> VarargsFunction<INPUTS, OUTPUT>
upgrade(BiFunction<INPUTS, INPUTS, OUTPUT> function) {
return inputs -> function.apply(inputs[0], inputs[1]);
}
@SuppressWarnings
<http://java.sun.com/j2se/1.5.0/docs/api/java/lang/SuppressWarnings.html>("unchecked")
public default <POST_OUTPUT> VarargsFunction<INPUTS, POST_OUTPUT> andThen(
VarargsFunction<OUTPUT, POST_OUTPUT> after) {
return inputs -> after.apply(apply(inputs));
}
@SuppressWarnings
<http://java.sun.com/j2se/1.5.0/docs/api/java/lang/SuppressWarnings.html>("unchecked")
public default Function<INPUTS, OUTPUT> toFunction() {
return input -> apply(input);
}
@SuppressWarnings
<http://java.sun.com/j2se/1.5.0/docs/api/java/lang/SuppressWarnings.html>("unchecked")
public default BiFunction<INPUTS, INPUTS, OUTPUT> toBiFunction() {
return (input, input2) -> apply(input, input2);
}
@SuppressWarnings
<http://java.sun.com/j2se/1.5.0/docs/api/java/lang/SuppressWarnings.html>("unchecked")
public default <PRE_INPUTS> VarargsFunction<PRE_INPUTS, OUTPUT>
transformArguments(Function<PRE_INPUTS, INPUTS> transformer) {
return inputs -> apply((INPUTS[]) Arrays
<http://java.sun.com/j2se/1.5.0/docs/api/java/util/Arrays.html>.stream(inputs).parallel().map(transformer).toArray());
}
}
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.function.Function;
import java.util.function.UnaryOperator;
import java.util.stream.Collectors;
import java.util.stream.LongStream;
@FunctionalInterface
public interface Y<FUNCTION> extends SelfApplicable<FixedPoint<FUNCTION>> {
public static void main(String
<http://java.sun.com/j2se/1.5.0/docs/api/java/lang/String.html>...
arguments) {
BigInteger <http://java.sun.com/j2se/1.5.0/docs/api/java/math/BigInteger.html>
TWO = BigInteger
<http://java.sun.com/j2se/1.5.0/docs/api/java/math/BigInteger.html>.ONE.add(BigInteger
<http://java.sun.com/j2se/1.5.0/docs/api/java/math/BigInteger.html>.ONE);
Function<Number
<http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Number.html>, Long
<http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Long.html>> toLong
= Number <http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Number.html>::longValue;
Function<Number
<http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Number.html>,
BigInteger <http://java.sun.com/j2se/1.5.0/docs/api/java/math/BigInteger.html>>
toBigInteger = toLong.andThen(BigInteger
<http://java.sun.com/j2se/1.5.0/docs/api/java/math/BigInteger.html>::valueOf);
/* Based on https://gist.github.com/aruld/3965968/#comment-604392 */
Y<VarargsFunction<Number
<http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Number.html>,
Number <http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Number.html>>>
combinator = y -> f -> x -> f.apply(y.selfApply().apply(f)).apply(x);
FixedPoint<VarargsFunction<Number
<http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Number.html>,
Number <http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Number.html>>>
fixedPoint = combinator.selfApply();
VarargsFunction<Number
<http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Number.html>,
Number <http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Number.html>>
fibonacci = fixedPoint.apply(
f -> VarargsFunction.upgrade(
toBigInteger.andThen(
n -> (n.compareTo(TWO) <= 0)
? 1
: new BigInteger
<http://java.sun.com/j2se/1.5.0/docs/api/java/math/BigInteger.html>(f.apply(n.subtract(BigInteger
<http://java.sun.com/j2se/1.5.0/docs/api/java/math/BigInteger.html>.ONE)).toString())
.add(new BigInteger
<http://java.sun.com/j2se/1.5.0/docs/api/java/math/BigInteger.html>(f.apply(n.subtract(TWO)).toString()))
)
)
);
VarargsFunction<Number
<http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Number.html>,
Number <http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Number.html>>
factorial = fixedPoint.apply(
f -> VarargsFunction.upgrade(
toBigInteger.andThen(
n -> (n.compareTo(BigInteger
<http://java.sun.com/j2se/1.5.0/docs/api/java/math/BigInteger.html>.ONE)
<= 0)
? 1
: n.multiply(new BigInteger
<http://java.sun.com/j2se/1.5.0/docs/api/java/math/BigInteger.html>(f.apply(n.subtract(BigInteger
<http://java.sun.com/j2se/1.5.0/docs/api/java/math/BigInteger.html>.ONE)).toString()))
)
)
);
VarargsFunction<Number
<http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Number.html>,
Number <http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Number.html>>
ackermann = fixedPoint.apply(
f -> VarargsFunction.upgrade(
(BigInteger
<http://java.sun.com/j2se/1.5.0/docs/api/java/math/BigInteger.html> m,
BigInteger <http://java.sun.com/j2se/1.5.0/docs/api/java/math/BigInteger.html>
n) -> m.equals(BigInteger
<http://java.sun.com/j2se/1.5.0/docs/api/java/math/BigInteger.html>.ZERO)
? n.add(BigInteger
<http://java.sun.com/j2se/1.5.0/docs/api/java/math/BigInteger.html>.ONE)
: f.apply(
m.subtract(BigInteger
<http://java.sun.com/j2se/1.5.0/docs/api/java/math/BigInteger.html>.ONE),
n.equals(BigInteger
<http://java.sun.com/j2se/1.5.0/docs/api/java/math/BigInteger.html>.ZERO)
? BigInteger
<http://java.sun.com/j2se/1.5.0/docs/api/java/math/BigInteger.html>.ONE
: f.apply(m, n.subtract(BigInteger
<http://java.sun.com/j2se/1.5.0/docs/api/java/math/BigInteger.html>.ONE))
)
).transformArguments(toBigInteger)
);
Map <http://java.sun.com/j2se/1.5.0/docs/api/java/util/Map.html><String
<http://java.sun.com/j2se/1.5.0/docs/api/java/lang/String.html>,
VarargsFunction<Number
<http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Number.html>,
Number <http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Number.html>>>
functions = new HashMap
<http://java.sun.com/j2se/1.5.0/docs/api/java/util/HashMap.html><>();
functions.put("fibonacci", fibonacci);
functions.put("factorial", factorial);
functions.put("ackermann", ackermann);
Map <http://java.sun.com/j2se/1.5.0/docs/api/java/util/Map.html><VarargsFunction<Number
<http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Number.html>,
Number <http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Number.html>>,
Number <http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Number.html>[]>
parameters = new HashMap
<http://java.sun.com/j2se/1.5.0/docs/api/java/util/HashMap.html><>();
parameters.put(functions.get("fibonacci"), new Number
<http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Number.html>[]{20});
parameters.put(functions.get("factorial"), new Number
<http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Number.html>[]{10});
parameters.put(functions.get("ackermann"), new Number
<http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Number.html>[]{3,
2});
functions.entrySet().stream().parallel().map(
entry -> entry.getKey()
+ Arrays
<http://java.sun.com/j2se/1.5.0/docs/api/java/util/Arrays.html>.toString(parameters.get(entry.getValue()))
+ " = "
+ entry.getValue().apply(parameters.get(entry.getValue()))
).forEach(System
<http://java.sun.com/j2se/1.5.0/docs/api/java/lang/System.html>.out::println);
}
}
Samuel Dennis R. Borlongan
Samuel Dennis R. Borlongan
On Wed, Sep 11, 2013 at 3:56 PM, Millies, Sebastian <
Sebastian.Millies at softwareag.com> wrote:
> Hello there,
>
> many people seem to enjoy coding the Y combinator in Java. There are
> examples
> in Java 7 (e. g. [1] and [2]) which I decided to try and port to Java 8.
> The popular
> application is to compute the factorial function.
>
> I’ll show my first solution in a minute. The code really does work: There
> are no
> variables, no names assigned to any function, only lambda expressions and
> parameters.
> And yet, we can recursively compute the factorial of arbitrary integers.
>
> Here’s the puzzle for you: I have not been able to “generify” the thing,
> i. e.
> replace all references to “int” in the Y combinator with a suitable type
> parameter.
> I would always get type incompatibilities. And remember: No named methods
> or
> variables are allowed. (e. g. the Java 7 code in [2] violates that
> condition.)
>
> Note that there are a few casts even in the working solution. Why are they
> necessary?
> It would be nice to get rid of them.
>
> Best Regards,
> Sebastian
>
> [1] http://www.righto.com/2009/03/y-combinator-in-arc-and-java.html
> [2] https://gist.github.com/jonbodner/2571928
>
> Code follows
> ------- 8< ----------
>
> import java.util.function.Function;
> import java.util.function.IntUnaryOperator;
>
> public class Combinators {
>
> // First a few abbreviations
>
> /** Function on int returning int. */
> interface IntFunc extends IntUnaryOperator {
> }
>
> /**
> * Higher-order function returning an int function.
> * <br/>F: F -> (int -> int)
> * <br/>This is the type of the Y combinator subexpressions.
> */
> interface FuncToIntFunc extends Function<FuncToIntFunc, IntFunc> {
> }
>
> /**
> * Function from IntFuntToIntFunc to Func.
> * <br/>((int -> int) -> (int -> int)) -> (int -> int)
> */
> interface YCombinator extends Function<Function<IntFunc, IntFunc>,
> IntFunc> {
> }
>
> // Then the meat
>
> /**
> * Computes the factorial with the applicative-order Y combinator.
> * <br/>Y = λr.(λf.(f f)) λf.(r λx.((f f) x))
> */
> public static int factorial(int n) {
> return ((YCombinator) r ->
> ((FuncToIntFunc) (f -> f.apply(f))).apply(
> f -> r.apply(x ->
> f.apply(f).applyAsInt(x)))
> )
> .apply(
> // Recursive function generator
> f -> x -> (x == 0) ? 1 : x *
> f.applyAsInt(x - 1)
> )
> .applyAsInt(
> // Argument
> n);
> }
>
> public static void main(String args[]) {
> int n = Integer.parseInt(args[0]);
> System.out.println(n + "! = " + factorial(n));
> }
> }
>
> Software AG – Sitz/Registered office: Uhlandstraße 12, 64297 Darmstadt,
> Germany – Registergericht/Commercial register: Darmstadt HRB 1562 -
> Vorstand/Management Board: Karl-Heinz Streibich (Vorsitzender/Chairman),
> Dr. Wolfram Jost, Arnd Zinnhardt; - Aufsichtsratsvorsitzender/Chairman of
> the Supervisory Board: Dr. Andreas Bereczky - http://www.softwareag.com
>
>
>
More information about the lambda-dev
mailing list