FMList.java

package fmlist;

import fj.F;
import fj.F2;
import fj.P2;
import fj.P;
import fj.Function;
import fj.Monoid;
import fj.Ord;
import fj.Ordering;
import fj.Hash;
import fj.Show;
import fj.Semigroup;
import fj.Equal;
import fj.data.Option;
import fj.data.Either;
import java.util.Collection;
import java.util.Collections;
import java.util.List;
import java.util.Deque;
import java.util.Iterator;
import java.util.ListIterator;
import java.util.ArrayList;
import java.util.NoSuchElementException;
import java.util.Comparator;
/**
 * @author Alexander Altman
 * @param <E> the element type
 */
public final class FMList<E> implements List<E>, Deque<E>, Cloneable {

    /**
     * Produces a first-class function that casts it's input to it's output's
     * type
     *
     * @param <A> the input type of the first-class function
     * @param <B> the output type of the first-class function
     * @return the requested first-class function
     */
    public static <A, B> F<A, B> castFunc() {
        return new F<A, B>() {

            @Override
            @SuppressWarnings("unchecked")
            public B f(A a) {
                return (B) a;
            }
        };
    }
    private FM<E> inner;

    /**
     * finds out if this list could possibly be finite
     *
     * @return whether or not the list is possibly finite
     */
    public boolean couldBeFinite() {
        return getInner().couldBeFinite();
    }

    /**
     * Produces the dual of a monoid
     *
     * @param <E> the monoid's domain
     * @param m the original monoid
     * @return the requested monoid
     */
    public static <E> Monoid<E> dualMonoid(Monoid<E> m) {
        return Monoid.monoid(Function.uncurryF2(m.sum()).flip(), m.zero());
    }

    /**
     * Produces the dual of a semigroup
     *
     * @param <E> the semigroup's domain
     * @param m the original semigroup
     * @return the requested semigroup
     */
    public static <E> Semigroup<E> dualSemigroup(Semigroup<E> m) {
        return Semigroup.semigroup(Function.uncurryF2(m.sum()).flip());
    }

    /**
     * The monoid of composition over endomorphisms
     *
     * @param <A> the (co)domain of the endomorphisms in question
     * @return the requested monoid
     */
    public static <A> Monoid<F<A, A>> endoMonoid() {
        final F<F<A, A>, F<F<A, A>, F<A, A>>> co = Function.compose();
        final F<A, A> id = Function.identity();
        return Monoid.monoid(co, id);
    }

    /**
     * The semigroup of composition over endomorphisms
     *
     * @param <A> the (co)domain of the endomorphisms in question
     * @return the requested semigroup
     */
    public static <A> Semigroup<F<A, A>> endoSemigroup() {
        final F<F<A, A>, F<F<A, A>, F<A, A>>> co = Function.compose();
        return Semigroup.semigroup(co);
    }

    /**
     * The monoid of append() over FMLists
     *
     * @param <E> the element type
     * @return the requested monoid
     */
    public static <E> Monoid<FMList<E>> fmListMonoid() {
        final F2<FMList<E>, FMList<E>, FMList<E>> append = FMList.append();
        final FMList<E> zero = new FMList<E>();
        return Monoid.monoid(append, zero);
    }

    /**
     * The hash concept over FMLists
     *
     * @param <E> the element type
     * @return the requested hash concept
     */
    public static <E> Hash<FMList<E>> fmListHash() {
        return Hash.anyHash();
    }

    /**
     * The ordering concept over FMLists
     *
     * @param <E> the type of elements to compare
     * @return the requested ordering concept
     */
    public static <E extends Comparable<E>> Ord<FMList<E>> fmListOrd() {
        return Ord.ord(Function.curry(new F2<FMList<E>, FMList<E>, Ordering>() {

            @Override
            public Ordering f(FMList<E> a, FMList<E> b) {
                final int k = a.zipWith((new F2<E, E, Integer>() {

                    @Override
                    public Integer f(E a, E b) {
                        return a.compareTo(b);
                    }
                }), b).foldr1(new F2<Integer, Integer, Integer>() {

                    @Override
                    public Integer f(Integer a_, Integer b) {
                        final int a = a_.intValue();
                        if (a == 0) {
                            return b;
                        } else {
                            return a;
                        }
                    }
                }).intValue();
                if (k < 0) {
                    return Ordering.LT;
                } else if (k == 0) {
                    return Ordering.EQ;
                } else {
                    return Ordering.GT;
                }
            }
        }));
    }

    /**
     * The ordering concept over FMLists
     *
     * @param <E> the type of elements to compare
     * @param cmp the ordering concept to use for the elements
     * @return the requested ordering concept
     */
    public static <E> Ord<FMList<E>> fmListOrd(Ord<E> cmp) {
        final Ord<E> qq = cmp;
        return Ord.ord(Function.curry(new F2<FMList<E>, FMList<E>, Ordering>() {

            @Override
            public Ordering f(FMList<E> a, FMList<E> b) {
                return a.zipWith((new F2<E, E, Ordering>() {

                    @Override
                    public Ordering f(E a, E b) {
                        return qq.compare(a, b);
                    }
                }), b).foldr1(new F2<Ordering, Ordering, Ordering>() {

                    @Override
                    public Ordering f(Ordering a, Ordering b) {
                        if (a.equals(Ordering.EQ)) {
                            return b;
                        } else {
                            return a;
                        }
                    }
                });
            }
        }));
    }

    /**
     * The ordering concept over FMLists
     *
     * @param <E> the type of elements to compare
     * @param cmp the comparator to use for the elements
     * @return the requested ordering concept
     */
    public static <E> Ord<FMList<E>> fmListOrd(Comparator<E> cmp) {
        final Comparator<E> qq = cmp;
        return Ord.ord(Function.curry(new F2<FMList<E>, FMList<E>, Ordering>() {

            @Override
            public Ordering f(FMList<E> a, FMList<E> b) {
                return a.zipWith((new F2<E, E, Ordering>() {

                    @Override
                    public Ordering f(E a, E b) {
                        final int z = qq.compare(a, b);
                        if (z < 0) {
                            return Ordering.LT;
                        } else if (z == 0) {
                            return Ordering.EQ;
                        } else {
                            return Ordering.GT;
                        }
                    }
                }), b).foldr1(new F2<Ordering, Ordering, Ordering>() {

                    @Override
                    public Ordering f(Ordering a, Ordering b) {
                        if (a.equals(Ordering.EQ)) {
                            return b;
                        } else {
                            return a;
                        }
                    }
                });
            }
        }));
    }

    /**
     * The equality concept over FMLists
     *
     * @param <E> the element type
     * @return the requested equality concept
     */
    public static <E> Equal<FMList<E>> fmListEqual() {
        return Equal.anyEqual();
    }

    /**
     * The string conversion concept over FMLists
     *
     * @param <E> the element type
     * @return the requested string conversion concept
     */
    public static <E> Show<FMList<E>> fmListShow() {
        return Show.anyShow();
    }

    /**
     * The string conversion concept over FMLists
     *
     * @param <E> the element type
     * @param showDict the string conversion concept to use for the elements
     * @return the requested string conversion concept
     */
    public static <E> Show<FMList<E>> fmListShow(Show<E> showDict) {
        final Show<E> sD = showDict;
        return Show.showS(new F<FMList<E>, String>() {

            @Override
            public String f(FMList<E> a) {
                return (new StringBuilder("FMList: [")).append(sD.showS(a.head())).append(a.tail().foldMap(Monoid.stringBuilderMonoid, (new F<E, StringBuilder>() {

                    @Override
                    public StringBuilder f(E a) {
                        return (new StringBuilder(", ")).append(sD.showS(a));
                    }
                }))).toString();
            }
        });
    }

    @Override
    public FMList<E> clone() {
        return new FMList<E>(getInner());
    }

    /**
     * The classic "zipWith" function, applied to FMLists
     *
     * @param <N> the other input list's element type
     * @param <Q> the final result list's element type
     * @param zipFunc the function to use for zipping
     * @param other the other input list
     * @return the final result list
     */
    public <N, Q> FMList<Q> zipWith(F2<E, N, Q> zipFunc, FMList<N> other) {
        final F2<E, N, Q> t = zipFunc;
        final FM<E> i1 = getInner();
        final FMList<N> il2 = other;
        return new FMList<Q>(new FM<Q>() {

            @Override
            boolean couldBeFinite() {
                return i1.couldBeFinite() || il2.couldBeFinite();
            }

            @Override
            <X> X fm(Monoid<X> monoid, F<Q, X> mapFunc) {
                return i1.transformCS((new TransformCSFunc<E, Q, FMList<N>>() {

                    @Override
                    <M> M f(Monoid<M> m, F<Q, M> f_, E e, F2<M, FMList<N>, M> c_, FMList<N> i) {
                        final Monoid<M> monoid = m;
                        final F<Q, M> f = f_;
                        final E e2 = e;
                        final F2<M, FMList<N>, M> c = c_;
                        final FMList<N> r1 = i;
                        return r1.foldr((new F2<N, M, M>() {

                            @Override
                            public M f(N e1, M b__) {
                                return c.f(f.f(t.f(e2, e1)), r1);
                            }
                        }), m.zero());
                    }
                }), il2).fm(monoid, mapFunc);
            }
        });
    }

    /**
     * Converts a pair of lists into a list of pairs
     *
     * @param <N> the other input list's element type
     * @param other the other input list
     * @return the zipped output list
     */
    public <N> FMList<P2<E, N>> zip(FMList<N> other) {
        final F<E, F<N, P2<E, N>>> f = P.p2();
        return zipWith(Function.uncurryF2(f), other);
    }

    /**
     * Forces the evaluation of all of the internal delay structures, avoiding
     * potential stack overflows in finite lists. Please note that if enough
     * nested delays must be forced, this could be quite an expensive operation.
     * WARNING: do not use on infinite lists! It will <i>cause</i> stack
     * overflows if used with infinities.
     *
     * @throws InfiniteListException if called on an infinite FMList
     */
    public void force() throws InfiniteListException {
        if (!couldBeFinite()) {
            throw new InfiniteListException(this, "cannnot not force an infinite list");
        } else {
            setInner(FM.newFM(this));
        }
    }

    @Override
    public String toString() {
        return (new StringBuilder("FMList: [")).append(head()).append(tail().foldMap(Monoid.stringBuilderMonoid, new F<E, StringBuilder>() {

            @Override
            public StringBuilder f(E a) {
                return new StringBuilder(", ").append(a);
            }
        })).append("]").toString();
    }

    @Override
    public boolean equals(Object o) {
        if (!(o instanceof FMList)) {
            return false;
        } else {
            final FMList<? extends Object> other = (FMList<? extends Object>) o;
            boolean result = size() == other.size();
            for (int i = 0; i < size(); i++) {
                if (result) {
                    result = result && get(i).equals(other.get(i));
                } else {
                    return false;
                }
            }
            return result;
        }
    }

    @Override
    public int hashCode() {
        return foldr((new F2<E, Integer, Integer>() {

            @Override
            public Integer f(E a, Integer b) {
                return (47 * b) + (a.hashCode());
            }
        }), 7);
    }

    FMList(FM<E> i) {
        setInner(i);
    }

    /**
     * Constructs an new empty FMList
     */
    public FMList() {
        final FM<E> k = FM.newFM();
        setInner(k);
    }

    /**
     * Constructs a new FMList with the contents of an existing Iterable
     *
     * @param i the source Iterable
     */
    public FMList(Iterable<? extends E> i) {
        final FM<E> k = FM.newFM(i);
        setInner(k);
    }

    /**
     * Specialization of the FMList(Iterable) constructor so that it can handle
     * infinite FMLists (and both infinite and finite ones in O(1))
     *
     * @param i the other FMList
     */
    public FMList(FMList<E> i) {
        setInner(i.getInner());
    }

    /**
     * Constructs a new FMList with just one element
     *
     * @param e the sole element
     */
    public FMList(E e) {
        final FM<E> k = FM.newFM(e);
        setInner(k);
    }

    /**
     * Constructs a new FMList with just two elements
     *
     * @param e1 the first element
     * @param e2 the second element
     */
    public FMList(E e1, E e2) {
        final FM<E> k1 = FM.newFM(e1);
        final FM<E> k2 = FM.newFM(e2);
        setInner(k1.appendFM(k2));
    }

    /**
     * Constructs a new FMList with just three elements
     *
     * @param e1 the first element
     * @param e2 the second element
     * @param e3 the third element
     */
    public FMList(E e1, E e2, E e3) {
        final FM<E> k1 = FM.newFM(e1);
        final FM<E> k2 = FM.newFM(e2);
        final FM<E> k3 = FM.newFM(e3);
        setInner(k1.appendFM(k2).appendFM(k3));
    }

    /**
     * Maps "mapFunc" over the list, then folds using "monoid". This is the core
     * operation that enables FMLists to work.
     *
     * @param <X> "monoid"'s domain
     * @param monoid the monoid to use for folding
     * @param mapFunc the function to use for mapping
     * @return the final folded value
     */
    public <X> X foldMap(Monoid<X> monoid, F<E, X> mapFunc) {
        return getInner().fm(monoid, mapFunc);
    }

    /**
     * First-class version of foldMap()
     *
     * @param <X> the domain of the to-be-provided monoid
     * @return the first-class function
     */
    public <X> F2<Monoid<X>, F<E, X>, X> foldMap() {
        return getInner().fm();
    }

    /**
     * Partially applied version of foldMap()
     *
     * @param <X> "monoid"'s domain
     * @param monoid the monoid to use for folding
     * @return the partially applied function
     */
    public <X> F<F<E, X>, X> foldMap(Monoid<X> monoid) {
        return getInner().fm(monoid);
    }

    /**
     * Monoidal fold operation
     *
     * @param monoid the monoid to use for folding
     * @return the final folded result
     */
    public E fold(Monoid<E> monoid) {
        final F<E, E> id = Function.identity();
        return foldMap(monoid, id);
    }

    /**
     * First-class version of fold()
     *
     * @return the first-class function
     */
    public F<Monoid<E>, E> fold() {
        final FMList<E> self = this;
        return new F<Monoid<E>, E>() {

            @Override
            public E f(Monoid<E> a) {
                return self.fold(a);
            }
        };
    }

    /**
     * Right-biased fold operation
     *
     * @param <N> The type of the final folded result
     * @param f the function to use for folding
     * @param z the seed value for the fold
     * @return the final folded result
     */
    public <N> N foldr(F2<E, N, N> f, N z) {
        final Monoid<F<N, N>> eM = endoMonoid();
        return foldMap(eM, f.curry()).f(z);
    }

    /**
     * Partially applied version of foldr()
     *
     * @param <N> The type of the final folded result
     * @param f the function to use for folding
     * @return the partially applied function
     */
    public <N> F<N, N> foldr(F2<E, N, N> f) {
        final Monoid<F<N, N>> eM = endoMonoid();
        return foldMap(eM, f.curry());
    }

    /**
     * First-class version of foldr()
     *
     * @param <N> The type of the final folded result
     * @return the first-class function
     */
    public <N> F2<F2<E, N, N>, N, N> foldr() {
        final FMList<E> self = this;
        return new F2<F2<E, N, N>, N, N>() {

            @Override
            public N f(F2<E, N, N> a, N b) {
                return self.foldr(a, b);
            }
        };
    }

    /**
     * Left-biased fold operation
     *
     * @param <N> The type of the final folded result
     * @param f the function to use for folding
     * @param z the seed value for the fold
     * @return the final folded result
     */
    public <N> N foldl(F2<N, E, N> f, N z) {
        final Monoid<F<N, N>> eM = endoMonoid();
        return foldMap(dualMonoid(eM), f.flip().curry()).f(z);
    }

    /**
     * Partially applied version of foldl()
     *
     * @param <N> The type of the final folded result
     * @param f the function to use for folding
     * @return the partially applied function
     */
    public <N> F<N, N> foldl(F2<N, E, N> f) {
        final Monoid<F<N, N>> eM = endoMonoid();
        return foldMap(dualMonoid(eM), f.flip().curry());
    }

    /**
     * First-class version of foldl()
     *
     * @param <N> The type of the final folded result
     * @return the first-class function
     */
    public <N> F2<F2<N, E, N>, N, N> foldl() {
        final FMList<E> self = this;
        return new F2<F2<N, E, N>, N, N>() {

            @Override
            public N f(F2<N, E, N> a, N b) {
                return self.foldl(a, b);
            }
        };
    }

    /**
     * Applies "mapFunc" to each element in the list
     *
     * @param <N> the final element type after mapping
     * @param mapFunc the function to use for mapping
     * @return the mapped version of the list
     */
    public <N> FMList<N> map(F<E, N> mapFunc) {
        final F<E, N> mf = mapFunc;
        return new FMList<N>(getInner().transform(new TransformFunc<N, E>() {

            @Override
            <M> M f(Monoid<M> monoid, F<N, M> func, E val) {
                return func.f(mf.f(val));
            }
        }));
    }

    /**
     * First-class version of map()
     *
     * @param <N> the final element type after mapping
     * @return the first-class function
     */
    public <N> F<F<E, N>, FMList<N>> map() {
        final FMList<E> self = this;
        return new F<F<E, N>, FMList<N>>() {

            @Override
            public FMList<N> f(F<E, N> a) {
                return self.map(a);
            }
        };
    }

    /**
     * Concatenates all of the sublists together into one large
     * single-dimensional list
     *
     * @param <E>
     * @param lls the nested list
     * @return the flattened version of "lls"
     */
    public static <E> FMList<E> flatten(FMList<FMList<E>> lls) {
        return new FMList<E>(lls.getInner().transform(new TransformFunc<E, FMList<E>>() {

            @Override
            <M> M f(Monoid<M> monoid, F<E, M> func, FMList<E> val) {
                return val.foldMap(monoid, func);
            }
        }));
    }

    /**
     * Concatenates this list to beginning of the given one
     *
     * @param other the other list
     * @return the appended result
     */
    public FMList<E> append(FMList<E> other) {
        return new FMList<E>(getInner().appendFM(other.getInner()));
    }

    /**
     * First-class version of append()
     *
     * @param <E> the element type
     * @return the first-class function
     */
    public static <E> F2<FMList<E>, FMList<E>, FMList<E>> append() {
        return new F2<FMList<E>, FMList<E>, FMList<E>>() {

            @Override
            public FMList<E> f(FMList<E> a, FMList<E> b) {
                return a.append(b);
            }
        };
    }

    /**
     * adds an element at the beginning
     *
     * @param e the new element
     */
    public void cons(E e) {
        final FM<E> k = FM.newFM(e);
        setInner(k.appendFM(getInner()));
    }

    /**
     * adds an element at the end
     *
     * @param e the new element
     */
    public void snoc(E e) {
        final FM<E> k = FM.newFM(e);
        setInner(getInner().appendFM(k));
    }

    /**
     * first-class copying version of cons()
     *
     * @return the first-class function
     */
    public F<E, FMList<E>> cons() {
        final FMList<E> self = this;
        return new F<E, FMList<E>>() {

            @Override
            public FMList<E> f(E a) {
                final FMList<E> ll = self.clone();
                ll.cons(a);
                return ll;
            }
        };
    }

    /**
     * first-class copying version of snoc()
     *
     * @return the first-class function
     */
    public F<E, FMList<E>> snoc() {
        final FMList<E> self = this;
        return new F<E, FMList<E>>() {

            @Override
            public FMList<E> f(E a) {
                final FMList<E> ll = self.clone();
                ll.snoc(a);
                return ll;
            }
        };
    }

    /**
     * finds the first element
     *
     * @return the first element
     */
    public E head() {
        final Monoid<Option<E>> m = Monoid.firstOptionMonoid();
        final F<E, Option<E>> f = Option.some_();
        return getInner().fm(m, f).valueE("Empty list!");
    }

    /**
     * Deletes all entries for which "filtFunc" is false
     *
     * @param filtFunc the predicate to use for filtering
     */
    public void filter(F<E, Boolean> filtFunc) {
        final F<E, Boolean> fF = filtFunc;
        setInner(getInner().transform(new TransformFunc<E, E>() {

            @Override
            <M> M f(Monoid<M> monoid, F<E, M> func, E val) {
                if (fF.f(val)) {
                    return func.f(val);
                } else {
                    return monoid.zero();
                }
            }
        }));
    }

    /**
     * finds the last element
     *
     * @return the last element
     */
    public E last() {
        final Monoid<Option<E>> m = Monoid.lastOptionMonoid();
        final F<E, Option<E>> f = Option.some_();
        return getInner().fm(m, f).valueE("Empty list!");
    }

    /**
     * Cuts this list down to the first "num" elements. Fast but unsafe with left infinities.
     *
     * @param num the number of elements to take
     */
    public void take(int num) {
        setInner(getInner().transformCS((new TransformCSFunc<E, E, Integer>() {

            @Override
            <M> M f(Monoid<M> m, F<E, M> f, E e, F2<M, Integer, M> c, Integer i) {
                if (i.intValue() > 0) {
                    return c.f(f.f(e), (i.intValue()) - 1);
                } else {
                    return m.zero();
                }
            }
        }), num));
    }

    /**
     * Cuts this list down to all except the first "num" elements.
     *
     * @param num the number of elements to drop
     */
    public void drop(int num) {
        setInner(getInner().transformCS((new TransformCSFunc<E, E, Integer>() {

            @Override
            <M> M f(Monoid<M> m, F<E, M> f, E e, F2<M, Integer, M> c, Integer i) {
                if (i.intValue() > 0) {
                    return c.f(m.zero(), (i.intValue() - 1));
                } else {
                    return c.f(f.f(e), 0);
                }
            }
        }), num));
    }

    /**
     * Cuts this list down to the first "num" elements. Somewhat slower than
     * take() but safe with left infinities.
     *
     * @param num the number of elements to take
     */
    public void keepFirst(int num) {
        final FMList<E> internal = new FMList<E>();
        for (int j = 0; j < num; j++) {
            internal.cons(get(j));
        }
        setInner(internal.getInner());
    }

    /**
     * Synonym for drop()
     *
     * @param num the number of elements to take
     */
    public void keepNotFirst(int num) {
        drop(num);
    }

    /**
     * Cuts this list down to the last "num" elements. Somewhat slower than
     * reverse(); take() but safe with right infinities.
     *
     * @param num the number of elements to take
     */
    public void keepLast(int num) {
        final FMList<E> internal1 = clone();
        internal1.reverse();
        final FMList<E> internal2 = new FMList<E>();
        for (int j = 0; j < num; j++) {
            internal2.snoc(internal1.get(j));
        }
        setInner(internal2.getInner());
    }

    /**
     * Synonym for reverse(); drop(); reverse()
     *
     * @param num the number of elements to take
     */
    public void keepNotLast(int num) {
        reverse();
        drop(num);
        reverse();
    }

    /**
     * Cuts this list down to all the elements before the first one that matches
     * "filtFunc"
     *
     * @param filtFunc the predicate to search with
     */
    public void takeWhile(F<E, Boolean> filtFunc) {
        final F<E, Boolean> p = filtFunc;
        setInner(getInner().transformCS((new TransformCSFunc<E, E, Boolean>() {

            @Override
            <M> M f(Monoid<M> m, F<E, M> f, E e, F2<M, Boolean, M> c, Boolean i) {
                if (p.f(e)) {
                    return c.f(f.f(e), true);
                } else {
                    return m.zero();
                }
            }
        }), true));
    }

    /**
     * Cuts this list down to the first element that matches "filtFunc" plus all
     * the elements after that one
     *
     * @param filtFunc the predicate to search with
     */
    public void dropWhile(F<E, Boolean> filtFunc) {
        final F<E, Boolean> p = filtFunc;
        setInner(getInner().transformCS((new TransformCSFunc<E, E, Boolean>() {

            @Override
            <M> M f(Monoid<M> m, F<E, M> f, E e, F2<M, Boolean, M> c, Boolean ok) {
                if (ok && p.f(e)) {
                    return c.f(m.zero(), true);
                } else {
                    return c.f(f.f(e), false);
                }
            }
        }), true));
    }

    public <N> FMList<N> castElements() {
        final F<E, N> cf = castFunc();
        return map(cf);
    }

    /**
     * Gets the first element that matches filtFunc
     *
     * @param filtFunc the predicate to search with
     * @return the element involved
     * @throws NoSuchElementException if no element matches "filtFunc"
     */
    public E find(F<E, Boolean> filtFunc) throws NoSuchElementException {
        final FMList<E> internal = clone();
        internal.dropWhile(filtFunc);
        if (internal.isEmpty()) {
            throw new NoSuchElementException("no element matches the supplied predicate");
        } else {
            return internal.head();
        }
    }

    /**
     * gets all except the first element
     *
     * @return the 'tail' of the list
     */
    public FMList<E> tail() {
        final FMList<E> other = clone();
        other.drop(1);
        return other;
    }

    /**
     * gets all except the last element
     *
     * @return the 'init' of the list
     */
    public FMList<E> init() {
        final FMList<E> other = this.clone();
        other.reverse();
        other.drop(1);
        return other;
    }

    /**
     * reverses this list
     */
    public void reverse() {
        final FM<E> i = getInner();
        setInner(new FM<E>() {

            @Override
            <X> X fm(Monoid<X> monoid, F<E, X> mapFunc) {
                return i.fm(dualMonoid(monoid), mapFunc);
            }

            @Override
            boolean couldBeFinite() {
                return i.couldBeFinite();
            }
        });
    }

    @Override
    public int size() {
        F<E, Integer> cst1 = Function.constant(1);
        return foldMap(Monoid.intAdditionMonoid, cst1).intValue();
    }

    @Override
    public boolean isEmpty() {
        return size() == 0;
    }

    @Override
    public boolean contains(Object o) {
        final Object r = o;
        final FMList<E> testList = this.clone();
        testList.filter(new F<E, Boolean>() {

            @Override
            public Boolean f(E a) {
                return (r == null ? a == null : r.equals(a));
            }
        });
        return !(testList.isEmpty());
    }

    @Override
    public Iterator<E> iterator() {
        final FMList<E> self = this;
        return new Iterator<E>() {

            private int currentIndex = 0;

            @Override
            public boolean hasNext() {
                return currentIndex != self.size();
            }

            @Override
            public E next() {
                if (hasNext()) {
                    currentIndex++;
                    return self.get(currentIndex);
                } else {
                    throw new NoSuchElementException("this FMList is right-finite");
                }
            }

            @Override
            public void remove() {
                self.remove(currentIndex);
                currentIndex--;
            }
        };
    }

    @Override
    public Object[] toArray() {
        final int s = size();
        final Object[] outArray = new Object[s];
        for (int i = 0; i < s; i++) {
            outArray[i] = get(i);
        }
        return outArray;
    }

    @Override
    @SuppressWarnings({"unchecked", "unchecked"})
    public <T> T[] toArray(T[] ts) {
        final int s1 = size();
        final int s2 = ts.length;
        if (s2 > s1) {
            final T[] outArray;
            outArray = ts;
            for (int i = 0; i < s1; i++) {
                outArray[i] = (T) get(i);
            }
            return outArray;
        } else {
            final ArrayList<T> outList = new ArrayList<T>(s1);
            for (E x : this) {
                outList.add((T) x);
            }
            return outList.toArray(ts);
        }
    }

    @Override
    public boolean add(E e) {
        this.snoc(e);
        return true;
    }

    @Override
    public boolean remove(Object o) {
        final Object r = o;
        final F<E, Boolean> filtFunc = new F<E, Boolean>() {

            @Override
            public Boolean f(E a) {
                return !(r == null ? a == null : r.equals(a));
            }
        };
        final FMList<E> testList = clone();
        testList.filter(filtFunc);
        boolean answer = !(testList.isEmpty());
        if (answer) {
            final FMList<E> internal1 = clone();
            final FMList<E> internal2 = clone();
            internal1.takeWhile(filtFunc);
            internal2.dropWhile(filtFunc);
            internal2.tail();
            setInner(internal1.getInner().appendFM(internal2.getInner()));
        }
        return answer;
    }

    @Override
    public boolean containsAll(Collection<?> clctn) {
        final FMList<Object> c = new FMList<Object>(clctn);
        final FMList<E> self = this;
        return c.foldMap(Monoid.conjunctionMonoid, (new F<Object, Boolean>() {

            @Override
            @SuppressWarnings("unchecked")
            public Boolean f(Object a) {
                return self.contains(a);
            }
        }));
    }

    @Override
    public boolean addAll(Collection<? extends E> clctn) {
        return addAll(0, clctn);
    }

    @Override
    public boolean addAll(int i, Collection<? extends E> clctn) {
        final FMList<E> alt1 = clone();
        final FMList<E> alt3 = clone();
        alt1.keepFirst(i);
        alt3.drop(i);
        final FMList<E> alt2 = new FMList<E>(clctn);
        setInner(alt1.getInner().appendFM(alt2.getInner()).appendFM(alt3.getInner()));
        return true;
    }

    /**
     * Monadic core operation
     *
     * @param <N> the final element type
     * @param bindFunc the function to bind this list to
     * @return the result of the binding
     */
    public <N> FMList<N> bind(F<E, FMList<N>> bindFunc) {
        final F<E, FMList<N>> g = bindFunc;
        return new FMList<N>(getInner().transform(new TransformFunc<N, E>() {

            @Override
            <M> M f(Monoid<M> monoid, F<N, M> func, E val) {
                return g.f(val).foldMap(monoid, func);
            }
        }));
    }

    /**
     * Applicative core operation
     *
     * @param <N> the final element type
     * @param appFuncList the list of functions to apply over this list
     * @return the result of the application
     */
    public <N> FMList<N> apply(FMList<F<E, N>> appFuncList) {
        final FM<F<E, N>> gs = appFuncList.getInner();
        final FM<E> xs = getInner();
        return new FMList<N>(gs.transform(new TransformFunc<N, F<E, N>>() {

            @Override
            <M> M f(Monoid<M> monoid, F<N, M> func, F<E, N> val) {
                return xs.fm(monoid, func.o(val));
            }
        }));
    }

    /**
     * Deconstructs this list into head() and tail()
     *
     * @return a tuple containing head() and tail()
     */
    public P2<E, FMList<E>> decons() {
        return P.p(head(), tail());
    }

    /**
     * Deconstructs this list into init() and last()
     *
     * @return a tuple containing init() and last()
     */
    public P2<FMList<E>, E> desnoc() {
        return P.p(init(), last());
    }

    /**
     * splits the list on the given index
     *
     * @param splitIndex the index after which to split the list
     * @return the split lists
     */
    public P2<FMList<E>, FMList<E>> split(int splitIndex) {
        final FMList<E> a = clone();
        final FMList<E> b = clone();
        a.keepFirst(splitIndex + 1);
        b.drop(splitIndex + 1);
        return P.p(a, b);
    }

    /**
     * Splits the list after the first element that matches "filtFunc"
     *
     * @param filtFunc the predicate by which to split the list
     * @return the split lists
     */
    public P2<FMList<E>, FMList<E>> splitOn(F<E, Boolean> filtFunc) {
        final FMList<E> a = clone();
        final FMList<E> b = clone();
        a.takeWhile(filtFunc);
        b.dropWhile(filtFunc);
        a.snoc(b.head());
        return P.p(a, b.tail());
    }

    /**
     * Produces a right-infinite list that contains the progressively iterated
     * application of "iterFunc" to "initialValue", starting with "initialValue"
     * itself
     *
     * @param <E>
     * @param iterFunc
     * @param initialValue
     * @return the infinite list
     */
    public static <E> FMList<E> iterate(F<E, E> iterFunc, E initialValue) {
        final F<E, E> f = iterFunc;
        final E x = initialValue;
        final FM<E> iterFM = new FM<E>() {

            @Override
            <X> X fm(Monoid<X> monoid, F<E, X> mapFunc) {
                return monoid.sum(mapFunc.f(x), fm(monoid, mapFunc));
            }

            @Override
            boolean couldBeFinite() {
                return false;
            }
        };
        return new FMList<E>(iterFM);
    }

    /**
     * cycleM()s a single element
     *
     * @param <E>
     * @param elem
     * @return the infinite list
     */
    public static <E> FMList<E> repeatM(E elem) {
        final FMList<E> result = new FMList<E>(elem);
        result.cycleM();
        return result;
    }

    /**
     * Repeats this list infinitely in the middle
     */
    public void cycleM() {
        final FM<E> l = getInner();
        final FMList<E> self = this;
        final FM<E> cycleFM = new FM<E>() {

            @Override
            <X> X fm(Monoid<X> monoid, F<E, X> mapFunc) {
                final FMList<E> xx = self.clone();
                xx.cycleM();
                return (l.appendFM(xx.getInner()).appendFM(l)).fm(monoid, mapFunc);
            }

            @Override
            boolean couldBeFinite() {
                return false;
            }
        };
        setInner(cycleFM);
    }

    /**
     * cycleR()s a single element
     *
     * @param <E>
     * @param elem
     * @return the infinite list
     */
    public static <E> FMList<E> repeatR(E elem) {
        final FMList<E> result = new FMList<E>(elem);
        result.cycleR();
        return result;
    }

    /**
     * Repeats this list infinitely to the right
     */
    public void cycleR() {
        final FM<E> l = getInner();
        final FMList<E> self = this;
        final FM<E> cycleFM = new FM<E>() {

            @Override
            <X> X fm(Monoid<X> monoid, F<E, X> mapFunc) {
                final FMList<E> xx = self.clone();
                xx.cycleR();
                return ((xx.getInner()).appendFM(l)).fm(monoid, mapFunc);
            }

            @Override
            boolean couldBeFinite() {
                return false;
            }
        };
        setInner(cycleFM);
    }

    /**
     * cycleL()s a single element
     *
     * @param <E>
     * @param elem
     * @return the infinite list
     */
    public static <E> FMList<E> repeatL(E elem) {
        final FMList<E> result = new FMList<E>(elem);
        result.cycleL();
        return result;
    }

    /**
     * Repeats this list infinitely to the left
     */
    public void cycleL() {
        final FM<E> l = getInner();
        final FMList<E> self = this;
        final FM<E> cycleFM = new FM<E>() {

            @Override
            <X> X fm(Monoid<X> monoid, F<E, X> mapFunc) {
                final FMList<E> xx = self.clone();
                xx.cycleL();
                return (l.appendFM(xx.getInner())).fm(monoid, mapFunc);
            }

            @Override
            boolean couldBeFinite() {
                return false;
            }
        };
        setInner(cycleFM);
    }

    /**
     * cycleB()s a single element
     *
     * @param <E>
     * @param elem
     * @return the infinite list
     */
    public static <E> FMList<E> repeatB(E elem) {
        final FMList<E> result = new FMList<E>(elem);
        result.cycleB();
        return result;
    }

    /**
     * Repeats this list infinitely to the left and right
     */
    public void cycleB() {
        final FM<E> l = getInner();
        final FMList<E> self = this;
        final FM<E> cycleFM = new FM<E>() {

            @Override
            <X> X fm(Monoid<X> monoid, F<E, X> mapFunc) {
                final FMList<E> xx = self.clone();
                xx.cycleB();
                final FM<E> xi = xx.getInner();
                return (xi.appendFM(l).appendFM(xi)).fm(monoid, mapFunc);
            }

            @Override
            boolean couldBeFinite() {
                return false;
            }
        };
        setInner(cycleFM);
    }

    /**
     * Builds a list from a seed value. unfold() takes a seed and calls "bFunc"
     * on it. If the result is in right(), then it is appended to the prior. If
     * the result in in left(), then it is used in the core recursive call.
     *
     * @param <E>
     * @param <N>
     * @param bFunc
     * @param seedValue
     * @return the unfolded list
     */
    public static <E, N> FMList<E> unfold(F<N, FMList<Either<N, E>>> bFunc, N seedValue) {
        return new FMList<E>(FM.unfold(bFunc.andThen(new F<FMList<Either<N, E>>, FM<Either<N, E>>>() {

            @Override
            public FM<Either<N, E>> f(FMList<Either<N, E>> a) {
                return a.getInner();
            }
        }), seedValue));
    }

    /**
     * right-biased Option-based version of unfold()
     *
     * @param <E> the final element type
     * @param <N> the seed type
     * @param bFunc the function to use for unfolding
     * @param seedValue the initial seed value
     * @return the unfolded list
     */
    public static <E, N> FMList<E> unfoldr(F<N, Option<P2<E, N>>> bFunc, N seedValue) {
        final F<N, Option<P2<E, N>>> g = bFunc;
        return unfold((new F<N, FMList<Either<N, E>>>() {

            @Override
            public FMList<Either<N, E>> f(N a) {
                final Option<P2<E, N>> k = g.f(a);
                if (k.isNone()) {
                    return new FMList<Either<N, E>>();
                } else {
                    final P2<E, N> p = k.some();
                    final Either<N, E> va = Either.right(p._1());
                    final Either<N, E> vb = Either.left(p._2());
                    return new FMList<Either<N, E>>(va, vb);
                }
            }
        }), seedValue);
    }

    /**
     * left-biased Option-based version of unfold()
     *
     * @param <E> the final element type
     * @param <N> the seed type
     * @param bFunc the function to use for unfolding
     * @param seedValue the initial seed value
     * @return the unfolded list
     */
    public static <E, N> FMList<E> unfoldl(F<N, Option<P2<E, N>>> bFunc, N seedValue) {
        FMList<E> result = unfoldr(bFunc, seedValue);
        result.reverse();
        return result;
    }

    @Override
    public boolean removeAll(Collection<?> clctn) {
        final FMList<Object> c = new FMList<Object>(clctn);
        final FMList<E> self = this;
        return c.foldMap(Monoid.conjunctionMonoid, (new F<Object, Boolean>() {

            @Override
            public Boolean f(Object a) {
                return self.remove(a);
            }
        }));
    }

    @Override
    public boolean retainAll(Collection<?> clctn) {
        final FMList<Object> internal = (new FMList<Object>(clctn));
        internal.filter(new F<Object, Boolean>() {

            @Override
            public Boolean f(Object a) {
                throw new UnsupportedOperationException("Not supported yet.");
            }
        });
        setInner(internal.map(new F<Object, E>() {

            @Override
            @SuppressWarnings("unchecked")
            public E f(Object a) {
                return (E) a;
            }
        }).getInner());
        return true;
    }

    @Override
    public void clear() {
        FM<E> ii = FM.newFM();
        setInner(ii);
    }

    @Override
    public E get(int i) {
        final FMList<E> internal = clone();
        internal.drop(i);
        return internal.head();
    }

    @Override
    public E set(int i, E e) {
        final FMList<E> internal1 = clone();
        final FMList<E> internal2 = clone();
        internal1.take(i);
        internal2.drop(i + 1);
        final FM<E> i3 = FM.newFM(e);
        final E old = get(i);
        setInner(internal1.getInner().appendFM(i3).appendFM(internal2.getInner()));
        return old;
    }

    @Override
    public void add(int i, E e) {
        final FMList<E> internal1 = clone();
        final FMList<E> internal2 = clone();
        internal1.take(i);
        internal2.drop(i);
        final FM<E> i3 = FM.newFM(e);
        setInner(internal1.getInner().appendFM(i3).appendFM(internal2.getInner()));
    }

    @Override
    public E remove(int i) {
        final FMList<E> internal1 = clone();
        final FMList<E> internal2 = clone();
        internal1.take(i);
        internal2.drop(i + 1);
        final E old = get(i);
        setInner(internal1.getInner().appendFM(internal2.getInner()));
        return old;
    }

    public FMList<P2<Integer, E>> number() {
        final FMList<E> self = this;
        return self.tail().foldl((new F2<FMList<P2<Integer, E>>, E, FMList<P2<Integer, E>>>() {

            @Override
            public FMList<P2<Integer, E>> f(FMList<P2<Integer, E>> a, E b) {
                final int k = a.last()._1().intValue();
                a.snoc(P.p((k + 1), b));
                return a;
            }
        }), (new FMList<P2<Integer, E>>(P.p(0, self.head()))));
    }

    @Override
    public int indexOf(Object o) {
        final FMList<P2<Integer, E>> internal = number();
        internal.retainAll(Collections.singletonList(o));
        if (internal.isEmpty()) {
            return -1;
        } else {
            return internal.head()._1().intValue();
        }
    }

    @Override
    public int lastIndexOf(Object o) {
        final FMList<P2<Integer, E>> internal = number();
        internal.retainAll(Collections.singletonList(o));
        if (internal.isEmpty()) {
            return -1;
        } else {
            return internal.last()._1().intValue();
        }
    }

    private static interface FMListIterator<E> extends ListIterator<E> {

        void setCurrentIndex(int i);
    }

    private FMListIterator<E> fmListIterator() {
        final FMList<E> self = this;
        return new FMListIterator<E>() {

            private int currentIndex = 0;

            @Override
            public boolean hasNext() {
                return currentIndex != self.size();
            }

            @Override
            public E next() {
                if (hasNext()) {
                    currentIndex++;
                    return self.get(currentIndex);
                } else {
                    throw new NoSuchElementException("this FMList is right-finite");
                }
            }

            @Override
            public void remove() {
                self.remove(currentIndex);
                currentIndex--;
            }

            @Override
            public boolean hasPrevious() {
                return currentIndex != 0;
            }

            @Override
            public E previous() {
                if (hasPrevious()) {
                    currentIndex--;
                    return self.get(currentIndex);
                } else {
                    throw new NoSuchElementException("this FMList is left-finite");
                }
            }

            @Override
            public int nextIndex() {
                return currentIndex + 1;
            }

            @Override
            public int previousIndex() {
                return currentIndex - 1;
            }

            @Override
            public void set(E e) {
                self.set(currentIndex, e);
            }

            @Override
            public void add(E e) {
                self.add(currentIndex, e);
                currentIndex++;
            }

            @Override
            public void setCurrentIndex(int i) {
                currentIndex = i;
            }
        };
    }

    @Override
    public ListIterator<E> listIterator() {
        return fmListIterator();
    }

    @Override
    public ListIterator<E> listIterator(int i) {
        final FMListIterator<E> li = fmListIterator();
        li.setCurrentIndex(i - 1);
        return li;
    }

    @Override
    public FMList<E> subList(int i, int i1) {
        FMList<E> internal = clone();
        internal.take(i);
        internal.drop(i1 - i);
        return internal;
    }

    @Override
    public void addFirst(E e) {
        cons(e);
    }

    @Override
    public void addLast(E e) {
        snoc(e);
    }

    @Override
    public boolean offerFirst(E e) {
        cons(e);
        return true;
    }

    @Override
    public boolean offerLast(E e) {
        snoc(e);
        return true;
    }

    @Override
    public E removeFirst() {
        E e = head();
        drop(1);
        return e;
    }

    @Override
    public E removeLast() {
        E e = last();
        take(size() - 1);
        return e;
    }

    @Override
    public E pollFirst() {
        if (isEmpty()) {
            return null;
        } else {
            return removeFirst();
        }
    }

    @Override
    public E pollLast() {
        if (isEmpty()) {
            return null;
        } else {
            return removeLast();
        }
    }

    @Override
    public E getFirst() {
        return head();
    }

    @Override
    public E getLast() {
        return last();
    }

    @Override
    public E peekFirst() {
        if (isEmpty()) {
            return null;
        } else {
            return getFirst();
        }
    }

    @Override
    public E peekLast() {
        if (isEmpty()) {
            return null;
        } else {
            return getLast();
        }
    }

    @Override
    public boolean removeFirstOccurrence(Object o) {
        return remove(o);
    }

    @Override
    public boolean removeLastOccurrence(Object o) {
        reverse();
        final boolean r = remove(o);
        reverse();
        return r;
    }

    @Override
    public boolean offer(E e) {
        return offerLast(e);
    }

    @Override
    public E remove() {
        return removeFirst();
    }

    @Override
    public E poll() {
        return pollFirst();
    }

    @Override
    public E element() {
        return getFirst();
    }

    @Override
    public E peek() {
        return peekFirst();
    }

    @Override
    public void push(E e) {
        addFirst(e);
    }

    @Override
    public E pop() {
        return removeFirst();
    }

    /**
     * Unseeded foldr()
     *
     * @param f the folding function
     * @return the final folded value
     * @throws NoSuchElementException if this list is empty
     */
    public E foldr1(F2<E, E, E> f) throws NoSuchElementException {
        if (isEmpty()) {
            throw new NoSuchElementException("cannot do an unseeded fold on an empty list");
        }
        return tail().foldr(f, head());
    }

    /**
     * First-class version of foldr1()
     *
     * @return the first-class function
     */
    public F<F2<E, E, E>, E> foldr1() {
        final FMList<E> self = this;
        return new F<F2<E, E, E>, E>() {

            @Override
            public E f(F2<E, E, E> a) {
                return self.foldr1(a);
            }
        };
    }

    /**
     * Unseeded foldl()
     *
     * @param f the folding function
     * @return the final folded value
     * @throws NoSuchElementException if this list is empty
     */
    public E foldl1(F2<E, E, E> f) {
        if (isEmpty()) {
            throw new NoSuchElementException("cannot do an unseeded fold on an empty list");
        }
        return init().foldl(f, last());
    }

    /**
     * First-class version of foldl1()
     *
     * @return the first-class function
     */
    public F<F2<E, E, E>, E> foldl1() {
        final FMList<E> self = this;
        return new F<F2<E, E, E>, E>() {

            @Override
            public E f(F2<E, E, E> a) {
                return self.foldl1(a);
            }
        };
    }

    /**
     * append()s all the inner lists
     *
     * @param <E> the inner element type
     * @param lli the multi-layer list
     * @return the joined list
     */
    public static <E> FMList<E> concat(FMList<FMList<E>> lli) {
        final Monoid<FMList<E>> m = fmListMonoid();
        return lli.fold(m);
    }

    /**
     * Gets the "&&" of all the booleans in "lli"
     *
     * @param lli the list to be folded
     * @return the final folded value
     * @throws InfiniteListException if "lli" is infinite
     */
    public static Boolean and(FMList<Boolean> lli) throws InfiniteListException {
        if (!(lli.couldBeFinite())) {
            throw new InfiniteListException(lli, "cannot fold an infinite list to a point");
        }
        final Monoid<Boolean> m = Monoid.conjunctionMonoid;
        return lli.fold(m);
    }

    /**
     * Gets the "||" of all the booleans in "lli"
     *
     * @param lli the list to be folded
     * @return the final folded value
     * @throws InfiniteListException if "lli" is infinite
     */
    public static Boolean or(FMList<Boolean> lli) throws InfiniteListException {
        if (!(lli.couldBeFinite())) {
            throw new InfiniteListException(lli, "cannot fold an infinite list to a point");
        }
        final Monoid<Boolean> m = Monoid.disjunctionMonoid;
        return lli.fold(m);
    }

    /**
     * map()s the list to booleans using "f", then "||"'s them
     *
     * @param f
     * @return the final folded value
     * @throws InfiniteListException if "lli" is infinite
     */
    public Boolean any(F<E, Boolean> f) throws InfiniteListException {
        if (!(couldBeFinite())) {
            throw new InfiniteListException(this, "cannot fold an infinite list to a point");
        }
        final Monoid<Boolean> m = Monoid.disjunctionMonoid;
        return foldMap(m, f);
    }

    /**
     * map()s the list to booleans using "f", then "&&"'s them
     *
     * @param f
     * @return the final folded value
     * @throws InfiniteListException if "lli" is infinite
     */
    public Boolean all(F<E, Boolean> f) throws InfiniteListException {
        if (!(couldBeFinite())) {
            throw new InfiniteListException(this, "cannot fold an infinite list to a point");
        }
        final Monoid<Boolean> m = Monoid.conjunctionMonoid;
        return foldMap(m, f);
    }

    /**
     * Gets the maximum value among all the "Comparable"'s in "lli"
     *
     * @param <E>
     * @param lli the list to be folded
     * @return the final folded value
     * @throws InfiniteListException if "lli" is infinite
     */
    public static <E extends Comparable<E>> E maximum(FMList<E> lli) throws InfiniteListException {
        if (!(lli.couldBeFinite())) {
            throw new InfiniteListException(lli, "cannot fold an infinite list to a point");
        }
        return lli.foldr1(new F2<E, E, E>() {

            @Override
            public E f(E a, E b) {
                final int z = a.compareTo(b);
                if (z <= 0) {
                    return b;
                } else {
                    return a;
                }
            }
        });
    }

    /**
     * Gets the minimum value among all the "Comparable"'s in "lli"
     *
     * @param <E>
     * @param lli the list to be folded
     * @return the final folded value
     * @throws InfiniteListException if "lli" is infinite
     */
    public static <E extends Comparable<E>> E minimum(FMList<E> lli) throws InfiniteListException {
        if (!(lli.couldBeFinite())) {
            throw new InfiniteListException(lli, "cannot fold an infinite list to a point");
        }
        return lli.foldr1(new F2<E, E, E>() {

            @Override
            public E f(E a, E b) {
                final int z = a.compareTo(b);
                if (z <= 0) {
                    return a;
                } else {
                    return b;
                }
            }
        });
    }

    /**
     * Gets the maximum value among all the values in the list
     *
     * @param cmp the ordering to use when comparing
     * @return the final folded value
     * @throws InfiniteListException if "lli" is infinite
     */
    public E maximum(Ord<E> cmp) throws InfiniteListException {
        if (!(couldBeFinite())) {
            throw new InfiniteListException(this, "cannot fold an infinite list to a point");
        }
        return foldr1(Function.uncurryF2(cmp.max));
    }

    /**
     * Gets the minimum value among all the values in the list
     *
     * @param cmp the ordering to use when comparing
     * @return the final folded value
     * @throws InfiniteListException if "lli" is infinite
     */
    public E minimum(Ord<E> cmp) throws InfiniteListException {
        if (!(couldBeFinite())) {
            throw new InfiniteListException(this, "cannot fold an infinite list to a point");
        }
        return foldr1(Function.uncurryF2(cmp.min));
    }

    /**
     * Gets the maximum value among all the values in the list
     *
     * @param cmp the comparator to use when comparing
     * @return the final folded value
     * @throws InfiniteListException if "lli" is infinite
     */
    public E maximum(Comparator<E> cmp) throws InfiniteListException {
        if (!(couldBeFinite())) {
            throw new InfiniteListException(this, "cannot fold an infinite list to a point");
        }
        final Comparator<E> k = cmp;
        return foldr1(new F2<E, E, E>() {

            @Override
            public E f(E a, E b) {
                if (k.compare(a, b) < 0) {
                    return b;
                } else {
                    return a;
                }
            }
        });
    }

    /**
     * Gets the minimum value among all the values in the list
     *
     * @param cmp the comparator to use when comparing
     * @return the final folded value
     * @throws InfiniteListException if "lli" is infinite
     */
    public E minimum(Comparator<E> cmp) throws InfiniteListException {
        if (!(couldBeFinite())) {
            throw new InfiniteListException(this, "cannot fold an infinite list to a point");
        }
        final Comparator<E> k = cmp;
        return foldr1(new F2<E, E, E>() {

            @Override
            public E f(E a, E b) {
                if (k.compare(a, b) < 0) {
                    return a;
                } else {
                    return b;
                }
            }
        });
    }

    @Override
    public Iterator<E> descendingIterator() {
        final FMList<E> self = this;
        return new Iterator<E>() {

            private int currentIndex = self.size();

            ;

            @Override
            public boolean hasNext() {
                return currentIndex != 0;
            }

            @Override
            public E next() {
                if (hasNext()) {
                    currentIndex--;
                    return self.get(currentIndex);
                } else {
                    throw new NoSuchElementException("this FMList is left-finite");
                }
            }

            @Override
            public void remove() {
                self.remove(currentIndex);
                currentIndex--;
            }
        };
    }

    FM<E> getInner() {
        return inner;
    }

    private void setInner(FM<E> inner) {
        this.inner = inner;
    }
}