使用Java实现haskell-style的list

作为一个haskell这门函数式编程语言的爱好者，我特别喜欢它的list操作和推导功能。与传统面向对象或者过程语言不同的是，函数式语言通常喜欢把它们分为head、tail或者init、last等两部分，而不是一个数组性的列表。

针对列表的操作，也通常使用递归和迭代的方式来完成，特别强大。java8后，有了stream之后，才感觉能够和它有得一拼，但总感觉stream操作的list比较繁琐。

工作之余，做为一种爱好或者锻炼，我自己用java实现了一套haskell-style的list类，支持大部分原生haskell list函数和操作，并且可以与java list(准确来说是迭代器)进行相互转换。

得到一个haskell-style列表，你仅仅需要像这样：

PreludeList<Integer> intList = PreludeList.of(1,2,3,4);

你还可以像下面这样，得到一个无限长的列表：

PreludeList<Integer> rangeList = PreludeList.range(1, 10000);
PreludeList<Integer> repeatList = PreludeList.repeat(3);
PreludeList<Integer> cycleList = PreludeList.cycle(Preludelist.of(1,3,5));
PreludeList<Integer> iterableList = PreludeList.iterable(t -> t * 3, 3);          //[3, 9, 27, 81....]

并且，这些全部都是惰性求值，真正用的时候才会去延迟计算。

你还可以进行更多的list操作：

PreludeList<Integer> intList = PreludeList.of(1,2,3,4,5,6);

//基础操作
Integer headValue = PreludeList.head(intList);
PreludeList<Integer> tailList = PreludeList.tail(intList);
PreludeList<Integer> initList = PreludeList.init(intList);
Integer lastValue = PreludeList.last(intList);

//列表操作
PreludeList<Integer> revertList = PreludeList.reverse(intList);     //一个反转的整数列表
PreludeList<Integer> take3List = PreludeList.take(3, intList);      //取前面三项组成一个新的列表
PreludeList<Integer> drop3List = PreludeList.drop(3, intList);     //移除掉前面三项组成的新列表
PreludeList<Integer> filterList = PreludeList.filter(t -> t % 2 == 0, intList);    //取偶数组成新列表
PreludeList<Integer> mapList = PreludeList.map(t -> t * 2, intList);              //每个数增长到2倍的新列表

//与Java迭代器的互动
Iterable iterable = PreludeList.to(intList);
PreludeList<Integer> iterableList = PreludeList.from(iterable);

//其他
System.out.println(intList.toString());             //它会输出[1,2,3,4,5,6]

说了这么多，有没有点期待，完整的功能比上面更丰富，还在不断完善中。。。。。
代码见下：

import javax.swing.text.html.HTMLDocument;
import java.text.NumberFormat;
import java.text.ParseException;
import java.util.Iterator;
import java.util.function.Function;
import java.util.function.Predicate;

/**
 *
 * @author richardyang
 * @version $Id: PreludeList.java, v 0.1 2018年06月01日 下午5:10 richardyang Exp $
 */
public class PreludeList<T> {

    private static class Nil<T> extends PreludeList<T> {
        @Override
        protected T getHead() {
            throw new UnsupportedOperationException("Prelude list empty");
        }

        @Override
        protected PreludeList<T> getTail() {
            throw new UnsupportedOperationException("Prelude list empty");
        }
    }

    private static class RepeatList<T> extends PreludeList<T> {
        private T x;

        protected RepeatList(T x) {
            this.isEmpty = false;
            this.x = x;
        }

        @Override
        protected T getHead() {
            return x;
        }

        @Override
        protected PreludeList<T> getTail() {
            return new RepeatList(x);
        }
    }

    private static class CycleList<T> extends PreludeList<T> {
        private PreludeList<T> cycleList;

        protected CycleList(PreludeList<T> list) {
            this.cycleList = list;
            this.isEmpty = false;
        }

        @Override
        protected T getHead() {
            return cycleList.getHead();
        }

        @Override
        protected PreludeList<T> getTail() {
            if (!nil(cycleList.getTail())) {
                PreludeList<T> tailList = cycleList.getTail();
                return PreludeList.cons(tailList, new CycleList<T>(cycleList));
            }

            return new RepeatList<T>(head(cycleList));
        }
    }

    private static class IterateList<T> extends PreludeList<T> {
        private Function<T, T> function;
        private T x;

        protected IterateList(Function<T, T> function, T x) {
            this.function = function;
            this.x = x;
            this.isEmpty = false;
        }

        @Override
        protected T getHead() {
            return x;
        }

        @Override
        protected PreludeList<T> getTail() {
            return new IterateList<T>(function, function.apply(x));
        }
    }

    private static class RangeList<T extends Number> extends PreludeList<T> {
        private T start;
        private T stop;
        private T step;
        private int stepCount;

        protected RangeList(T start, T stop, T step, int stepCount) {
            this.start = start;
            this.stop = stop;
            this.step = step;
            this.stepCount = stepCount;
            this.isEmpty = false;
        }

        @Override
        protected T getHead() {
            try {
                Number result = NumberFormat.getInstance().parse(String.valueOf(start.doubleValue() + step.doubleValue() * stepCount));
                return (T)result;
            } catch (ParseException e) {
                e.printStackTrace();
            }

            return null;
        }

        @Override
        protected PreludeList<T> getTail() {
            if (canNext()) {
                return new RangeList<T>(start, stop, step, stepCount + 1);
            }

            return nilElem;
        }

        private boolean canNext() {
            boolean lt = step.doubleValue() > 0;
            return lt
                    ? start.doubleValue() + step.doubleValue() * (stepCount + 1) <= stop.doubleValue()
                    : start.doubleValue() + step.doubleValue() * (stepCount + 1) >= stop.doubleValue();
        }
    }

    private static class IteratorList<T> extends PreludeList<T> {
        private Iterable<T> iterable;
        private T headValue;
        protected IteratorList(Iterable<T> iterable) {
            this.iterable = iterable;
            this.isEmpty = !iterable.iterator().hasNext();
            if (!this.isEmpty) {
                this.headValue = iterable.iterator().next();
            }
        }

        @Override
        protected T getHead() {
            if (!isEmpty) {
                return headValue;
            }

            throw new UnsupportedOperationException("Prelude Iterator empty");
        }

        @Override
        protected PreludeList<T> getTail() {
            if (!isEmpty) {
                return new IteratorList<T>(new Iterable<T>() {
                    @Override
                    public Iterator<T> iterator() {
                        Iterator<T> iterator = iterable.iterator();
                        iterator.next();

                        return iterator;
                    }
                });
            }

            return nilElem;
        }
    }

    private static class PreludeIterator<T> implements Iterator<T> {
        private PreludeList<T> list;

        protected PreludeIterator(PreludeList<T> list) {
            this.list = list;
        }

        @Override
        public boolean hasNext() {
            return !PreludeList.nil(list);
        }

        @Override
        public T next() {
            T result = list.getHead();
            list = list.getTail();
            return result;
        }
    }

    private T headItem;
    private PreludeList<T> tailList;
    protected boolean isEmpty = true;

    private static Nil nilElem = new Nil<>();

    protected T getHead() {
        return headItem;
    }

    protected PreludeList<T> getTail() {
        return tailList;
    }

    private PreludeList() {}

    private PreludeList(T elem) {
        this.headItem = elem;
        this.tailList = nilElem;
        this.isEmpty = false;
    }

    private PreludeList(T elem, PreludeList<T> tailList) {
        this.headItem = elem;
        this.tailList = tailList;
        this.isEmpty = false;
    }

    public static <T> PreludeList<T> of(T ...elem) {
        if (elem.length > 0) {
            T _head = elem[0];
            PreludeList<T> p = null;
            for (int i = elem.length - 1; i > 0; --i) {
                if (p != null) {
                    p = new PreludeList<T>(elem[i], p);
                } else {
                    p = new PreludeList<T>(elem[i]);
                }
            }

            return new PreludeList<T>(_head, p);
        }

        return nilElem;
    }

    public static <T extends Number> PreludeList<T> range(T start, T stop, T step) {
        return new RangeList<T>(start, stop, step, 0);
    }

    public static <T> PreludeList<T> from(Iterable<T> iterable) {
        if (iterable != null) {
            return new IteratorList<T>(iterable);
        }

        throw new UnsupportedOperationException("iterable is null");
    }

    public static <T> Iterable<T> to(PreludeList<T> list) {
        return new Iterable<T>() {
            @Override
            public Iterator<T> iterator() {
                return new PreludeIterator<T>(list);
            }
        };
    }

    public static <T> PreludeList<T> empty() {
        return nilElem;
    }

    public static <T> boolean nil(PreludeList<T> list) {
        return list == null || list.isEmpty || list == nilElem;
    }

    public static <T> PreludeList<T> cons(T elem, PreludeList<T> list) {
        if (elem == nilElem) {
            return list;
        }

        if (list == nilElem) {
            return new PreludeList<>(elem);
        }

        return new PreludeList<>(elem, list);
    }

    public static <T> PreludeList<T> cons(PreludeList<T> list, T elem) {
        if (elem == nilElem) {
            return list;
        }

        if (list == nilElem) {
            return new PreludeList<>(elem);
        }

        return PreludeList.cons(list, new PreludeList<T>(elem));
    }

    public static <T> PreludeList<T> cons(PreludeList<T> list1, PreludeList<T> list2) {
        if (list1 == nilElem) {
            return list2;
        }

        if (list2 == nilElem) {
            return list1;
        }

        return new PreludeList<T>(list1.getHead(), cons(list1.getTail(), list2));
    }

    public static <T> T head(PreludeList<T> list) {
        if (!nil(list)) {
            return list.getHead();
        }

        throw new UnsupportedOperationException("Prelude list empty");
    }

    public static <T> PreludeList<T> tail(PreludeList<T> list) {
        if (!nil(list)) {
            return list.getTail();
        }

        throw new UnsupportedOperationException("Prelude list empty");
    }

    public static <T> PreludeList<T> init(PreludeList<T> list) {
        T t = head(list);
        if (nil(list.getTail())) {
            return nilElem;
        }

        return new PreludeList<>(t, init(list.getTail()));
    }

    public static <T> T last(PreludeList<T> list) {
        T t = head(list);
        if (nil(list.getTail())) {
            return t;
        }

        return last(list.getTail());
    }

    public static <T> long length(PreludeList<T> list) {
        if (nil(list)) {
            return 0;
        }

        return 1 + length(list.getTail());
    }

    public static <T> T get(int pos, PreludeList<T> list) {
        if (pos < 0) {
            throw new IllegalArgumentException("pos is negative");
        }

        if (nil(list)) {
            throw new UnsupportedOperationException("prelude list is empty");
        }

        if (pos == 0) {
            return head(list);
        }

        return get(pos - 1, tail(list));
    }

    public static <T> PreludeList<T> repeat(T x) {
        if (x == nilElem) {
            throw new UnsupportedOperationException("The repeat operation doesn't support empty list");
        }

        return new RepeatList<T>(x);
    }

    public static <T> PreludeList<T> replicate(long count, T x) {
        if (x == nilElem) {
            throw new UnsupportedOperationException("The repeat operation doesn't support empty list");
        }

        return take(count, repeat(x));
    }

    public static <T> PreludeList<T> reverse(PreludeList<T> list) {
        if (nil(list)) {
            return nilElem;
        }

        return cons(reverse(list.getTail()), new PreludeList<T>(list.getHead()));
    }

    public static <T> PreludeList<T> take(long count, PreludeList<T> list) {
        if (count <= 0 || list.isEmpty) {
            return nilElem;
        }

        return new PreludeList<T>(list.getHead(), take(count -1, list.getTail()));
    }

    public static <T> PreludeList<T> drop(long count, PreludeList<T> list) {
        if (count <= 0 || list.isEmpty) {
            return list;
        }

        return drop(count - 1, list.getTail());
    }

    public static <T> PreludeList<T> cycle(PreludeList<T> list) {
        if (list == nilElem) {
            throw new UnsupportedOperationException("The repeat operation doesn't support empty list");
        }

        return new CycleList<T>(list);
    }

    public static <T> PreludeList<T> iterate(Function<T, T> function, T x) {
        return new IterateList<T>(function, x);
    }

    public static <T, R> PreludeList<R> map(Function<T, R> function, PreludeList<T> list) {
        if (nil(list)) {
            return nilElem;
        }

        return new PreludeList<R>(function.apply(head(list)), map(function, list.getTail()));
    }

    public static <T> PreludeList<T> filter(Predicate<T> predicate, PreludeList<T> list) {
        if (nil(list)) {
            return list;
        }

        if (!predicate.test(head(list))) {
            return filter(predicate, list.getTail());
        } else {
            return new PreludeList<>(head(list), filter(predicate, list.getTail()));
        }
    }

    public static <T, R> PreludeList<R> flatMap(Function<T, PreludeList<R>> function, PreludeList<T> list) {
        if (nil(list)) {
            return nilElem;
        }

        return PreludeList.cons(function.apply(head(list)), flatMap(function, list.getTail()));
    }

    public static <T> PreludeList<PreludeList<T>> splitAt(int count, PreludeList<T> list) {
        if (nil(list)) {
            return nilElem;
        }

        return new PreludeList<PreludeList<T>>(take(count, list), splitAt(count, drop(count, list)));
    }

    public static <T> PreludeList<PreludeList<T>> splitAt(Predicate<T> predicate, PreludeList<T> list) {
        if (nil(list)) {
            return nilElem;
        }

        PreludeList<T> elem = PreludeList.nilElem;
        PreludeList<T> loopList = list;
        while (!nil(loopList)) {
            T headItem = head(loopList);
            elem = PreludeList.cons(elem, new PreludeList<T>(headItem));
            if (!predicate.test(headItem)) {
                loopList = tail(loopList);
            } else {
                break;
            }
        }

        return !nil(loopList) ? PreludeList.cons(elem, splitAt(predicate, tail(loopList))) : new PreludeList<PreludeList<T>>(elem);
    }

    private static <T> int elemIndex(T x, PreludeList<T> list, int pos) {
        if (nil(list)) {
            return -1;
        }

        T t = head(list);
        if (t.equals(x) || t == x) {
            return pos;
        }

        return elemIndex(x, tail(list), pos + 1);
    }

    public static <T> int elemIndex(T x, PreludeList<T> list) {
        return elemIndex(x, tail(list), 0);
    }

    private static <T> PreludeList<Integer> elemIndices(T x, PreludeList<T> list, int pos) {
        if (nil(list)) {
            return nilElem;
        }

        T t = head(list);

        return t.equals(x) || t == x ? PreludeList.cons(pos, elemIndices(x, tail(list), pos + 1)) : elemIndices(x, tail(list), pos + 1);
    }

    public static <T> PreludeList<Integer> elemIndices(T x, PreludeList<T> list) {
        return elemIndices(x, tail(list), 0);
    }

    private static <T> T find(Predicate<T> predicate, PreludeList<T> list) {
        if (nil(list)) {
            throw new IllegalArgumentException("Can't find value");
        }

        T t = head(list);
        if (predicate.test(t)) {
            return t;
        }

        return find(predicate, tail(list));
    }

    private static <T> int findIndex(Predicate<T> predicate, PreludeList<T> list, int pos) {
        if (nil(list)) {
            return -1;
        }

        T t = head(list);
        if (predicate.test(t)) {
            return pos;
        }

        return findIndex(predicate, tail(list), pos + 1);
    }

    public static <T> int findIndex(Predicate<T> predicate, PreludeList<T> list) {
        return findIndex(predicate, tail(list), 0);
    }

    private static <T> PreludeList<Integer> findIndices(Predicate<T> predicate, PreludeList<T> list, int pos) {
        if (nil(list)) {
            return nilElem;
        }

        T t = head(list);

        return predicate.test(t) ? PreludeList.cons(pos, findIndices(predicate, tail(list), pos + 1)) : findIndices(predicate, tail(list), pos + 1);
    }

    public static <T> PreludeList<Integer> findIndices(Predicate<T> predicate, PreludeList<T> list) {
        return findIndices(predicate, tail(list), 0);
    }

    //partition even [2,4,6,7,9,10,11]  ==>  ([2,4,6,10],[7,9,11])
    public static <T> PreludeList<PreludeList<T>> partition(Predicate<T> predicate, PreludeList<T> list) {
        if (nil(list)) {
            return nilElem;
        }

        return PreludeList.cons(new PreludeList<PreludeList<T>>(filter(predicate, list)), new PreludeList<PreludeList<T>>(filter(predicate.negate(), list)));
    }

    @Override
    public String toString() {
        if (isEmpty) {
            return "[]";
        }

        StringBuilder stringBuilder = new StringBuilder("[");
        PreludeList<T> list = this;
        while (!list.isEmpty) {
            T t = list.getHead();

            stringBuilder.append(t.toString());

            try {
                list = list.getTail();
                if (!list.isEmpty) {
                    stringBuilder.append(",");
                }
            } catch (UnsupportedOperationException e) {
                break;
            }
        }

        stringBuilder.append("]");

        return stringBuilder.toString();
    }
}