一行代码八皇后

其实是标题党，准确的说是在一定条件只需要一行。

先上代码：

count(accumulate((r, i) -> flatmap((List<Integer> ps0) -> map(y -> cons(y, ps0), filter(y0 -> y((TriFunction<List<Integer>, Integer, Integer, Boolean> fn) -> (List<Integer> ps, Integer y, Integer gap) -> ps == null || !(car(ps) == y || car(ps) == y + gap || car(ps) == y - gap) && fn.apply(cdr(ps), y, gap + 1)).apply(ps0, y0, 1), range(1, 8))), r), list((List<Integer>) null), range(1, 8)));

当然他是不能独立运行的，完整代码：https://gist.github.com/ezksd/07a91873fcacdf66e44ed7aca7171b17

首先要定义一些辅助的数据结构

类似scheme里的pair和list。

class Pair<A, B> {
    A a;
    B b;
    Pair(A a, B b) {
        this.a = a;
        this.b = b;
    }
}

class List<E> extends Pair<E, List<E>> {
    List(E e, List<E> eList) {
        super(e, eList);
    }
}

@FunctionalInterface：用来表示lambda表达式的类型，

interface TriFunction<A,B,C,R>{
    R apply(A a, B b, C c);
}

interface RecurFunc<T> extends Function<RecurFunc<T>, T> {}

function包里面只有单参数的Function，两个参数的BiFunction，现在我们需要一个三参数的。三个参数也可以科里化成单参数的，考虑到代码长度（已经很长了）的原因就直接加了这个东西。

RecurFunc是y combinator里面用来表达一个高阶函数，apply自己，返回目标函数。

因为java的定义不能递归（不支持letrec)，比如你不能写int i = i + 1，而且lambda表达式不借助其他手段不能递归调用自己，y combinator就是这个其他手段。

关于y combinator，可以看看Y combinator 推导过程 ，抄袭自The Y Combinator。

然后是一些工具函数

package core;


import java.util.function.BiFunction;
import java.util.function.Function;

public class EightQueens {

    static <A, B> A car(Pair<A, B> pair) {
        return pair.a;
    }

    static <A, B> B cdr(Pair<A, B> pair) {
        return pair.b;
    }

    static <E> List<E> cons(E item, List<E> list) {
        return new List<>(item, list);
    }

    static <E> List<E> list(E... items) {
        List<E> r = null;
        for (int i = items.length - 1; i >= 0; i--) {
            r = new List<>(items[i], r);
        }
        return r;
    }

    static <E> List<E> append(List<E> l1, List<E> l2) {
        return l1 == null ? l2 : cons(car(l1), append(cdr(l1), l2));
    }

    static <T, R> R apply(Function<T, R> f, T t) {
        return f.apply(t);
    }

    static <T, U, R> R apply(BiFunction<T, U, R> op, T first, U second) {
        return op.apply(first,second);
    }


    static <T, R> List<R> map(Function<T, R> f, List<T> list) {
        return list == null ? null : cons(apply(f, car(list)), map(f, cdr(list)));
    }

    static <E> List<E> filter(Function<E, Boolean> pred, List<E> list) {
        return isNull(list)?null:apply(pred, car(list)) ? cons(car(list), filter(pred, cdr(list))) : filter(pred, cdr(list));
    }


    static <T,R> R accumulate(BiFunction<R, T, R> op, R initial, List<T> list) {
        return list == null ? initial : accumulate(op, apply(op, initial, car(list)), cdr(list));
    }

    static <T, R> List<R> flatmap(Function<T, List<R>> op, List<T> list) {
        return accumulate(EightQueens::append, null, map(op, list));
    }

    static List<Integer> range(int start,int end){
        return start>end?null:cons(start, range(start + 1, end));
    }


    static <A, B, C, D> TriFunction<A, B, C, D> y(Function<TriFunction<A, B, C, D>, TriFunction<A, B, C, D>> x) {
        RecurFunc<TriFunction<A,B,C,D>> prod = f -> x.apply((a,b,c) -> f.apply(f).apply(a,b,c));
        return prod.apply(prod);
    }

    static int count(List<?> list){
        return isNull(list)? 0:1 + count(cdr(list));
    }


    static boolean isNull(Object o) {
        return o == null;
    }

}

是的，你没有看错，虽然标题是一行Java代码，辅助函数却有这么长。但是如果你仔细看看，这些辅助函数并不是为写八皇后特化的，或者说把复杂的东西包起来。

具体这行代码是什么意思，可以看看[用Stream API写八皇后](用Stream API写八皇后) ，其实是一个东西。

。