Want more features on Pastebin? Sign Up, it's FREE!
Guest

FMList.java

By: PthariensFlame on Feb 4th, 2012  |  syntax: Java  |  size: 58.86 KB  |  views: 77  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. package fmlist;
  2.  
  3. import fj.F;
  4. import fj.F2;
  5. import fj.P2;
  6. import fj.P;
  7. import fj.Function;
  8. import fj.Monoid;
  9. import fj.Ord;
  10. import fj.Ordering;
  11. import fj.Hash;
  12. import fj.Show;
  13. import fj.Semigroup;
  14. import fj.Equal;
  15. import fj.data.Option;
  16. import fj.data.Either;
  17. import java.util.Collection;
  18. import java.util.Collections;
  19. import java.util.List;
  20. import java.util.Deque;
  21. import java.util.Iterator;
  22. import java.util.ListIterator;
  23. import java.util.ArrayList;
  24. import java.util.NoSuchElementException;
  25. import java.util.Comparator;
  26. /**
  27.  * @author Alexander Altman
  28.  * @param <E> the element type
  29.  */
  30. public final class FMList<E> implements List<E>, Deque<E>, Cloneable {
  31.  
  32.     /**
  33.      * Produces a first-class function that casts it's input to it's output's
  34.      * type
  35.      *
  36.      * @param <A> the input type of the first-class function
  37.      * @param <B> the output type of the first-class function
  38.      * @return the requested first-class function
  39.      */
  40.     public static <A, B> F<A, B> castFunc() {
  41.         return new F<A, B>() {
  42.  
  43.             @Override
  44.             @SuppressWarnings("unchecked")
  45.             public B f(A a) {
  46.                 return (B) a;
  47.             }
  48.         };
  49.     }
  50.     private FM<E> inner;
  51.  
  52.     /**
  53.      * finds out if this list could possibly be finite
  54.      *
  55.      * @return whether or not the list is possibly finite
  56.      */
  57.     public boolean couldBeFinite() {
  58.         return getInner().couldBeFinite();
  59.     }
  60.  
  61.     /**
  62.      * Produces the dual of a monoid
  63.      *
  64.      * @param <E> the monoid's domain
  65.      * @param m the original monoid
  66.      * @return the requested monoid
  67.      */
  68.     public static <E> Monoid<E> dualMonoid(Monoid<E> m) {
  69.         return Monoid.monoid(Function.uncurryF2(m.sum()).flip(), m.zero());
  70.     }
  71.  
  72.     /**
  73.      * Produces the dual of a semigroup
  74.      *
  75.      * @param <E> the semigroup's domain
  76.      * @param m the original semigroup
  77.      * @return the requested semigroup
  78.      */
  79.     public static <E> Semigroup<E> dualSemigroup(Semigroup<E> m) {
  80.         return Semigroup.semigroup(Function.uncurryF2(m.sum()).flip());
  81.     }
  82.  
  83.     /**
  84.      * The monoid of composition over endomorphisms
  85.      *
  86.      * @param <A> the (co)domain of the endomorphisms in question
  87.      * @return the requested monoid
  88.      */
  89.     public static <A> Monoid<F<A, A>> endoMonoid() {
  90.         final F<F<A, A>, F<F<A, A>, F<A, A>>> co = Function.compose();
  91.         final F<A, A> id = Function.identity();
  92.         return Monoid.monoid(co, id);
  93.     }
  94.  
  95.     /**
  96.      * The semigroup of composition over endomorphisms
  97.      *
  98.      * @param <A> the (co)domain of the endomorphisms in question
  99.      * @return the requested semigroup
  100.      */
  101.     public static <A> Semigroup<F<A, A>> endoSemigroup() {
  102.         final F<F<A, A>, F<F<A, A>, F<A, A>>> co = Function.compose();
  103.         return Semigroup.semigroup(co);
  104.     }
  105.  
  106.     /**
  107.      * The monoid of append() over FMLists
  108.      *
  109.      * @param <E> the element type
  110.      * @return the requested monoid
  111.      */
  112.     public static <E> Monoid<FMList<E>> fmListMonoid() {
  113.         final F2<FMList<E>, FMList<E>, FMList<E>> append = FMList.append();
  114.         final FMList<E> zero = new FMList<E>();
  115.         return Monoid.monoid(append, zero);
  116.     }
  117.  
  118.     /**
  119.      * The hash concept over FMLists
  120.      *
  121.      * @param <E> the element type
  122.      * @return the requested hash concept
  123.      */
  124.     public static <E> Hash<FMList<E>> fmListHash() {
  125.         return Hash.anyHash();
  126.     }
  127.  
  128.     /**
  129.      * The ordering concept over FMLists
  130.      *
  131.      * @param <E> the type of elements to compare
  132.      * @return the requested ordering concept
  133.      */
  134.     public static <E extends Comparable<E>> Ord<FMList<E>> fmListOrd() {
  135.         return Ord.ord(Function.curry(new F2<FMList<E>, FMList<E>, Ordering>() {
  136.  
  137.             @Override
  138.             public Ordering f(FMList<E> a, FMList<E> b) {
  139.                 final int k = a.zipWith((new F2<E, E, Integer>() {
  140.  
  141.                     @Override
  142.                     public Integer f(E a, E b) {
  143.                         return a.compareTo(b);
  144.                     }
  145.                 }), b).foldr1(new F2<Integer, Integer, Integer>() {
  146.  
  147.                     @Override
  148.                     public Integer f(Integer a_, Integer b) {
  149.                         final int a = a_.intValue();
  150.                         if (a == 0) {
  151.                             return b;
  152.                         } else {
  153.                             return a;
  154.                         }
  155.                     }
  156.                 }).intValue();
  157.                 if (k < 0) {
  158.                     return Ordering.LT;
  159.                 } else if (k == 0) {
  160.                     return Ordering.EQ;
  161.                 } else {
  162.                     return Ordering.GT;
  163.                 }
  164.             }
  165.         }));
  166.     }
  167.  
  168.     /**
  169.      * The ordering concept over FMLists
  170.      *
  171.      * @param <E> the type of elements to compare
  172.      * @param cmp the ordering concept to use for the elements
  173.      * @return the requested ordering concept
  174.      */
  175.     public static <E> Ord<FMList<E>> fmListOrd(Ord<E> cmp) {
  176.         final Ord<E> qq = cmp;
  177.         return Ord.ord(Function.curry(new F2<FMList<E>, FMList<E>, Ordering>() {
  178.  
  179.             @Override
  180.             public Ordering f(FMList<E> a, FMList<E> b) {
  181.                 return a.zipWith((new F2<E, E, Ordering>() {
  182.  
  183.                     @Override
  184.                     public Ordering f(E a, E b) {
  185.                         return qq.compare(a, b);
  186.                     }
  187.                 }), b).foldr1(new F2<Ordering, Ordering, Ordering>() {
  188.  
  189.                     @Override
  190.                     public Ordering f(Ordering a, Ordering b) {
  191.                         if (a.equals(Ordering.EQ)) {
  192.                             return b;
  193.                         } else {
  194.                             return a;
  195.                         }
  196.                     }
  197.                 });
  198.             }
  199.         }));
  200.     }
  201.  
  202.     /**
  203.      * The ordering concept over FMLists
  204.      *
  205.      * @param <E> the type of elements to compare
  206.      * @param cmp the comparator to use for the elements
  207.      * @return the requested ordering concept
  208.      */
  209.     public static <E> Ord<FMList<E>> fmListOrd(Comparator<E> cmp) {
  210.         final Comparator<E> qq = cmp;
  211.         return Ord.ord(Function.curry(new F2<FMList<E>, FMList<E>, Ordering>() {
  212.  
  213.             @Override
  214.             public Ordering f(FMList<E> a, FMList<E> b) {
  215.                 return a.zipWith((new F2<E, E, Ordering>() {
  216.  
  217.                     @Override
  218.                     public Ordering f(E a, E b) {
  219.                         final int z = qq.compare(a, b);
  220.                         if (z < 0) {
  221.                             return Ordering.LT;
  222.                         } else if (z == 0) {
  223.                             return Ordering.EQ;
  224.                         } else {
  225.                             return Ordering.GT;
  226.                         }
  227.                     }
  228.                 }), b).foldr1(new F2<Ordering, Ordering, Ordering>() {
  229.  
  230.                     @Override
  231.                     public Ordering f(Ordering a, Ordering b) {
  232.                         if (a.equals(Ordering.EQ)) {
  233.                             return b;
  234.                         } else {
  235.                             return a;
  236.                         }
  237.                     }
  238.                 });
  239.             }
  240.         }));
  241.     }
  242.  
  243.     /**
  244.      * The equality concept over FMLists
  245.      *
  246.      * @param <E> the element type
  247.      * @return the requested equality concept
  248.      */
  249.     public static <E> Equal<FMList<E>> fmListEqual() {
  250.         return Equal.anyEqual();
  251.     }
  252.  
  253.     /**
  254.      * The string conversion concept over FMLists
  255.      *
  256.      * @param <E> the element type
  257.      * @return the requested string conversion concept
  258.      */
  259.     public static <E> Show<FMList<E>> fmListShow() {
  260.         return Show.anyShow();
  261.     }
  262.  
  263.     /**
  264.      * The string conversion concept over FMLists
  265.      *
  266.      * @param <E> the element type
  267.      * @param showDict the string conversion concept to use for the elements
  268.      * @return the requested string conversion concept
  269.      */
  270.     public static <E> Show<FMList<E>> fmListShow(Show<E> showDict) {
  271.         final Show<E> sD = showDict;
  272.         return Show.showS(new F<FMList<E>, String>() {
  273.  
  274.             @Override
  275.             public String f(FMList<E> a) {
  276.                 return (new StringBuilder("FMList: [")).append(sD.showS(a.head())).append(a.tail().foldMap(Monoid.stringBuilderMonoid, (new F<E, StringBuilder>() {
  277.  
  278.                     @Override
  279.                     public StringBuilder f(E a) {
  280.                         return (new StringBuilder(", ")).append(sD.showS(a));
  281.                     }
  282.                 }))).toString();
  283.             }
  284.         });
  285.     }
  286.  
  287.     @Override
  288.     public FMList<E> clone() {
  289.         return new FMList<E>(getInner());
  290.     }
  291.  
  292.     /**
  293.      * The classic "zipWith" function, applied to FMLists
  294.      *
  295.      * @param <N> the other input list's element type
  296.      * @param <Q> the final result list's element type
  297.      * @param zipFunc the function to use for zipping
  298.      * @param other the other input list
  299.      * @return the final result list
  300.      */
  301.     public <N, Q> FMList<Q> zipWith(F2<E, N, Q> zipFunc, FMList<N> other) {
  302.         final F2<E, N, Q> t = zipFunc;
  303.         final FM<E> i1 = getInner();
  304.         final FMList<N> il2 = other;
  305.         return new FMList<Q>(new FM<Q>() {
  306.  
  307.             @Override
  308.             boolean couldBeFinite() {
  309.                 return i1.couldBeFinite() || il2.couldBeFinite();
  310.             }
  311.  
  312.             @Override
  313.             <X> X fm(Monoid<X> monoid, F<Q, X> mapFunc) {
  314.                 return i1.transformCS((new TransformCSFunc<E, Q, FMList<N>>() {
  315.  
  316.                     @Override
  317.                     <M> M f(Monoid<M> m, F<Q, M> f_, E e, F2<M, FMList<N>, M> c_, FMList<N> i) {
  318.                         final Monoid<M> monoid = m;
  319.                         final F<Q, M> f = f_;
  320.                         final E e2 = e;
  321.                         final F2<M, FMList<N>, M> c = c_;
  322.                         final FMList<N> r1 = i;
  323.                         return r1.foldr((new F2<N, M, M>() {
  324.  
  325.                             @Override
  326.                             public M f(N e1, M b__) {
  327.                                 return c.f(f.f(t.f(e2, e1)), r1);
  328.                             }
  329.                         }), m.zero());
  330.                     }
  331.                 }), il2).fm(monoid, mapFunc);
  332.             }
  333.         });
  334.     }
  335.  
  336.     /**
  337.      * Converts a pair of lists into a list of pairs
  338.      *
  339.      * @param <N> the other input list's element type
  340.      * @param other the other input list
  341.      * @return the zipped output list
  342.      */
  343.     public <N> FMList<P2<E, N>> zip(FMList<N> other) {
  344.         final F<E, F<N, P2<E, N>>> f = P.p2();
  345.         return zipWith(Function.uncurryF2(f), other);
  346.     }
  347.  
  348.     /**
  349.      * Forces the evaluation of all of the internal delay structures, avoiding
  350.      * potential stack overflows in finite lists. Please note that if enough
  351.      * nested delays must be forced, this could be quite an expensive operation.
  352.      * WARNING: do not use on infinite lists! It will <i>cause</i> stack
  353.      * overflows if used with infinities.
  354.      *
  355.      * @throws InfiniteListException if called on an infinite FMList
  356.      */
  357.     public void force() throws InfiniteListException {
  358.         if (!couldBeFinite()) {
  359.             throw new InfiniteListException(this, "cannnot not force an infinite list");
  360.         } else {
  361.             setInner(FM.newFM(this));
  362.         }
  363.     }
  364.  
  365.     @Override
  366.     public String toString() {
  367.         return (new StringBuilder("FMList: [")).append(head()).append(tail().foldMap(Monoid.stringBuilderMonoid, new F<E, StringBuilder>() {
  368.  
  369.             @Override
  370.             public StringBuilder f(E a) {
  371.                 return new StringBuilder(", ").append(a);
  372.             }
  373.         })).append("]").toString();
  374.     }
  375.  
  376.     @Override
  377.     public boolean equals(Object o) {
  378.         if (!(o instanceof FMList)) {
  379.             return false;
  380.         } else {
  381.             final FMList<? extends Object> other = (FMList<? extends Object>) o;
  382.             boolean result = size() == other.size();
  383.             for (int i = 0; i < size(); i++) {
  384.                 if (result) {
  385.                     result = result && get(i).equals(other.get(i));
  386.                 } else {
  387.                     return false;
  388.                 }
  389.             }
  390.             return result;
  391.         }
  392.     }
  393.  
  394.     @Override
  395.     public int hashCode() {
  396.         return foldr((new F2<E, Integer, Integer>() {
  397.  
  398.             @Override
  399.             public Integer f(E a, Integer b) {
  400.                 return (47 * b) + (a.hashCode());
  401.             }
  402.         }), 7);
  403.     }
  404.  
  405.     FMList(FM<E> i) {
  406.         setInner(i);
  407.     }
  408.  
  409.     /**
  410.      * Constructs an new empty FMList
  411.      */
  412.     public FMList() {
  413.         final FM<E> k = FM.newFM();
  414.         setInner(k);
  415.     }
  416.  
  417.     /**
  418.      * Constructs a new FMList with the contents of an existing Iterable
  419.      *
  420.      * @param i the source Iterable
  421.      */
  422.     public FMList(Iterable<? extends E> i) {
  423.         final FM<E> k = FM.newFM(i);
  424.         setInner(k);
  425.     }
  426.  
  427.     /**
  428.      * Specialization of the FMList(Iterable) constructor so that it can handle
  429.      * infinite FMLists (and both infinite and finite ones in O(1))
  430.      *
  431.      * @param i the other FMList
  432.      */
  433.     public FMList(FMList<E> i) {
  434.         setInner(i.getInner());
  435.     }
  436.  
  437.     /**
  438.      * Constructs a new FMList with just one element
  439.      *
  440.      * @param e the sole element
  441.      */
  442.     public FMList(E e) {
  443.         final FM<E> k = FM.newFM(e);
  444.         setInner(k);
  445.     }
  446.  
  447.     /**
  448.      * Constructs a new FMList with just two elements
  449.      *
  450.      * @param e1 the first element
  451.      * @param e2 the second element
  452.      */
  453.     public FMList(E e1, E e2) {
  454.         final FM<E> k1 = FM.newFM(e1);
  455.         final FM<E> k2 = FM.newFM(e2);
  456.         setInner(k1.appendFM(k2));
  457.     }
  458.  
  459.     /**
  460.      * Constructs a new FMList with just three elements
  461.      *
  462.      * @param e1 the first element
  463.      * @param e2 the second element
  464.      * @param e3 the third element
  465.      */
  466.     public FMList(E e1, E e2, E e3) {
  467.         final FM<E> k1 = FM.newFM(e1);
  468.         final FM<E> k2 = FM.newFM(e2);
  469.         final FM<E> k3 = FM.newFM(e3);
  470.         setInner(k1.appendFM(k2).appendFM(k3));
  471.     }
  472.  
  473.     /**
  474.      * Maps "mapFunc" over the list, then folds using "monoid". This is the core
  475.      * operation that enables FMLists to work.
  476.      *
  477.      * @param <X> "monoid"'s domain
  478.      * @param monoid the monoid to use for folding
  479.      * @param mapFunc the function to use for mapping
  480.      * @return the final folded value
  481.      */
  482.     public <X> X foldMap(Monoid<X> monoid, F<E, X> mapFunc) {
  483.         return getInner().fm(monoid, mapFunc);
  484.     }
  485.  
  486.     /**
  487.      * First-class version of foldMap()
  488.      *
  489.      * @param <X> the domain of the to-be-provided monoid
  490.      * @return the first-class function
  491.      */
  492.     public <X> F2<Monoid<X>, F<E, X>, X> foldMap() {
  493.         return getInner().fm();
  494.     }
  495.  
  496.     /**
  497.      * Partially applied version of foldMap()
  498.      *
  499.      * @param <X> "monoid"'s domain
  500.      * @param monoid the monoid to use for folding
  501.      * @return the partially applied function
  502.      */
  503.     public <X> F<F<E, X>, X> foldMap(Monoid<X> monoid) {
  504.         return getInner().fm(monoid);
  505.     }
  506.  
  507.     /**
  508.      * Monoidal fold operation
  509.      *
  510.      * @param monoid the monoid to use for folding
  511.      * @return the final folded result
  512.      */
  513.     public E fold(Monoid<E> monoid) {
  514.         final F<E, E> id = Function.identity();
  515.         return foldMap(monoid, id);
  516.     }
  517.  
  518.     /**
  519.      * First-class version of fold()
  520.      *
  521.      * @return the first-class function
  522.      */
  523.     public F<Monoid<E>, E> fold() {
  524.         final FMList<E> self = this;
  525.         return new F<Monoid<E>, E>() {
  526.  
  527.             @Override
  528.             public E f(Monoid<E> a) {
  529.                 return self.fold(a);
  530.             }
  531.         };
  532.     }
  533.  
  534.     /**
  535.      * Right-biased fold operation
  536.      *
  537.      * @param <N> The type of the final folded result
  538.      * @param f the function to use for folding
  539.      * @param z the seed value for the fold
  540.      * @return the final folded result
  541.      */
  542.     public <N> N foldr(F2<E, N, N> f, N z) {
  543.         final Monoid<F<N, N>> eM = endoMonoid();
  544.         return foldMap(eM, f.curry()).f(z);
  545.     }
  546.  
  547.     /**
  548.      * Partially applied version of foldr()
  549.      *
  550.      * @param <N> The type of the final folded result
  551.      * @param f the function to use for folding
  552.      * @return the partially applied function
  553.      */
  554.     public <N> F<N, N> foldr(F2<E, N, N> f) {
  555.         final Monoid<F<N, N>> eM = endoMonoid();
  556.         return foldMap(eM, f.curry());
  557.     }
  558.  
  559.     /**
  560.      * First-class version of foldr()
  561.      *
  562.      * @param <N> The type of the final folded result
  563.      * @return the first-class function
  564.      */
  565.     public <N> F2<F2<E, N, N>, N, N> foldr() {
  566.         final FMList<E> self = this;
  567.         return new F2<F2<E, N, N>, N, N>() {
  568.  
  569.             @Override
  570.             public N f(F2<E, N, N> a, N b) {
  571.                 return self.foldr(a, b);
  572.             }
  573.         };
  574.     }
  575.  
  576.     /**
  577.      * Left-biased fold operation
  578.      *
  579.      * @param <N> The type of the final folded result
  580.      * @param f the function to use for folding
  581.      * @param z the seed value for the fold
  582.      * @return the final folded result
  583.      */
  584.     public <N> N foldl(F2<N, E, N> f, N z) {
  585.         final Monoid<F<N, N>> eM = endoMonoid();
  586.         return foldMap(dualMonoid(eM), f.flip().curry()).f(z);
  587.     }
  588.  
  589.     /**
  590.      * Partially applied version of foldl()
  591.      *
  592.      * @param <N> The type of the final folded result
  593.      * @param f the function to use for folding
  594.      * @return the partially applied function
  595.      */
  596.     public <N> F<N, N> foldl(F2<N, E, N> f) {
  597.         final Monoid<F<N, N>> eM = endoMonoid();
  598.         return foldMap(dualMonoid(eM), f.flip().curry());
  599.     }
  600.  
  601.     /**
  602.      * First-class version of foldl()
  603.      *
  604.      * @param <N> The type of the final folded result
  605.      * @return the first-class function
  606.      */
  607.     public <N> F2<F2<N, E, N>, N, N> foldl() {
  608.         final FMList<E> self = this;
  609.         return new F2<F2<N, E, N>, N, N>() {
  610.  
  611.             @Override
  612.             public N f(F2<N, E, N> a, N b) {
  613.                 return self.foldl(a, b);
  614.             }
  615.         };
  616.     }
  617.  
  618.     /**
  619.      * Applies "mapFunc" to each element in the list
  620.      *
  621.      * @param <N> the final element type after mapping
  622.      * @param mapFunc the function to use for mapping
  623.      * @return the mapped version of the list
  624.      */
  625.     public <N> FMList<N> map(F<E, N> mapFunc) {
  626.         final F<E, N> mf = mapFunc;
  627.         return new FMList<N>(getInner().transform(new TransformFunc<N, E>() {
  628.  
  629.             @Override
  630.             <M> M f(Monoid<M> monoid, F<N, M> func, E val) {
  631.                 return func.f(mf.f(val));
  632.             }
  633.         }));
  634.     }
  635.  
  636.     /**
  637.      * First-class version of map()
  638.      *
  639.      * @param <N> the final element type after mapping
  640.      * @return the first-class function
  641.      */
  642.     public <N> F<F<E, N>, FMList<N>> map() {
  643.         final FMList<E> self = this;
  644.         return new F<F<E, N>, FMList<N>>() {
  645.  
  646.             @Override
  647.             public FMList<N> f(F<E, N> a) {
  648.                 return self.map(a);
  649.             }
  650.         };
  651.     }
  652.  
  653.     /**
  654.      * Concatenates all of the sublists together into one large
  655.      * single-dimensional list
  656.      *
  657.      * @param <E>
  658.      * @param lls the nested list
  659.      * @return the flattened version of "lls"
  660.      */
  661.     public static <E> FMList<E> flatten(FMList<FMList<E>> lls) {
  662.         return new FMList<E>(lls.getInner().transform(new TransformFunc<E, FMList<E>>() {
  663.  
  664.             @Override
  665.             <M> M f(Monoid<M> monoid, F<E, M> func, FMList<E> val) {
  666.                 return val.foldMap(monoid, func);
  667.             }
  668.         }));
  669.     }
  670.  
  671.     /**
  672.      * Concatenates this list to beginning of the given one
  673.      *
  674.      * @param other the other list
  675.      * @return the appended result
  676.      */
  677.     public FMList<E> append(FMList<E> other) {
  678.         return new FMList<E>(getInner().appendFM(other.getInner()));
  679.     }
  680.  
  681.     /**
  682.      * First-class version of append()
  683.      *
  684.      * @param <E> the element type
  685.      * @return the first-class function
  686.      */
  687.     public static <E> F2<FMList<E>, FMList<E>, FMList<E>> append() {
  688.         return new F2<FMList<E>, FMList<E>, FMList<E>>() {
  689.  
  690.             @Override
  691.             public FMList<E> f(FMList<E> a, FMList<E> b) {
  692.                 return a.append(b);
  693.             }
  694.         };
  695.     }
  696.  
  697.     /**
  698.      * adds an element at the beginning
  699.      *
  700.      * @param e the new element
  701.      */
  702.     public void cons(E e) {
  703.         final FM<E> k = FM.newFM(e);
  704.         setInner(k.appendFM(getInner()));
  705.     }
  706.  
  707.     /**
  708.      * adds an element at the end
  709.      *
  710.      * @param e the new element
  711.      */
  712.     public void snoc(E e) {
  713.         final FM<E> k = FM.newFM(e);
  714.         setInner(getInner().appendFM(k));
  715.     }
  716.  
  717.     /**
  718.      * first-class copying version of cons()
  719.      *
  720.      * @return the first-class function
  721.      */
  722.     public F<E, FMList<E>> cons() {
  723.         final FMList<E> self = this;
  724.         return new F<E, FMList<E>>() {
  725.  
  726.             @Override
  727.             public FMList<E> f(E a) {
  728.                 final FMList<E> ll = self.clone();
  729.                 ll.cons(a);
  730.                 return ll;
  731.             }
  732.         };
  733.     }
  734.  
  735.     /**
  736.      * first-class copying version of snoc()
  737.      *
  738.      * @return the first-class function
  739.      */
  740.     public F<E, FMList<E>> snoc() {
  741.         final FMList<E> self = this;
  742.         return new F<E, FMList<E>>() {
  743.  
  744.             @Override
  745.             public FMList<E> f(E a) {
  746.                 final FMList<E> ll = self.clone();
  747.                 ll.snoc(a);
  748.                 return ll;
  749.             }
  750.         };
  751.     }
  752.  
  753.     /**
  754.      * finds the first element
  755.      *
  756.      * @return the first element
  757.      */
  758.     public E head() {
  759.         final Monoid<Option<E>> m = Monoid.firstOptionMonoid();
  760.         final F<E, Option<E>> f = Option.some_();
  761.         return getInner().fm(m, f).valueE("Empty list!");
  762.     }
  763.  
  764.     /**
  765.      * Deletes all entries for which "filtFunc" is false
  766.      *
  767.      * @param filtFunc the predicate to use for filtering
  768.      */
  769.     public void filter(F<E, Boolean> filtFunc) {
  770.         final F<E, Boolean> fF = filtFunc;
  771.         setInner(getInner().transform(new TransformFunc<E, E>() {
  772.  
  773.             @Override
  774.             <M> M f(Monoid<M> monoid, F<E, M> func, E val) {
  775.                 if (fF.f(val)) {
  776.                     return func.f(val);
  777.                 } else {
  778.                     return monoid.zero();
  779.                 }
  780.             }
  781.         }));
  782.     }
  783.  
  784.     /**
  785.      * finds the last element
  786.      *
  787.      * @return the last element
  788.      */
  789.     public E last() {
  790.         final Monoid<Option<E>> m = Monoid.lastOptionMonoid();
  791.         final F<E, Option<E>> f = Option.some_();
  792.         return getInner().fm(m, f).valueE("Empty list!");
  793.     }
  794.  
  795.     /**
  796.      * Cuts this list down to the first "num" elements. Fast but unsafe with left infinities.
  797.      *
  798.      * @param num the number of elements to take
  799.      */
  800.     public void take(int num) {
  801.         setInner(getInner().transformCS((new TransformCSFunc<E, E, Integer>() {
  802.  
  803.             @Override
  804.             <M> M f(Monoid<M> m, F<E, M> f, E e, F2<M, Integer, M> c, Integer i) {
  805.                 if (i.intValue() > 0) {
  806.                     return c.f(f.f(e), (i.intValue()) - 1);
  807.                 } else {
  808.                     return m.zero();
  809.                 }
  810.             }
  811.         }), num));
  812.     }
  813.  
  814.     /**
  815.      * Cuts this list down to all except the first "num" elements.
  816.      *
  817.      * @param num the number of elements to drop
  818.      */
  819.     public void drop(int num) {
  820.         setInner(getInner().transformCS((new TransformCSFunc<E, E, Integer>() {
  821.  
  822.             @Override
  823.             <M> M f(Monoid<M> m, F<E, M> f, E e, F2<M, Integer, M> c, Integer i) {
  824.                 if (i.intValue() > 0) {
  825.                     return c.f(m.zero(), (i.intValue() - 1));
  826.                 } else {
  827.                     return c.f(f.f(e), 0);
  828.                 }
  829.             }
  830.         }), num));
  831.     }
  832.  
  833.     /**
  834.      * Cuts this list down to the first "num" elements. Somewhat slower than
  835.      * take() but safe with left infinities.
  836.      *
  837.      * @param num the number of elements to take
  838.      */
  839.     public void keepFirst(int num) {
  840.         final FMList<E> internal = new FMList<E>();
  841.         for (int j = 0; j < num; j++) {
  842.             internal.cons(get(j));
  843.         }
  844.         setInner(internal.getInner());
  845.     }
  846.  
  847.     /**
  848.      * Synonym for drop()
  849.      *
  850.      * @param num the number of elements to take
  851.      */
  852.     public void keepNotFirst(int num) {
  853.         drop(num);
  854.     }
  855.  
  856.     /**
  857.      * Cuts this list down to the last "num" elements. Somewhat slower than
  858.      * reverse(); take() but safe with right infinities.
  859.      *
  860.      * @param num the number of elements to take
  861.      */
  862.     public void keepLast(int num) {
  863.         final FMList<E> internal1 = clone();
  864.         internal1.reverse();
  865.         final FMList<E> internal2 = new FMList<E>();
  866.         for (int j = 0; j < num; j++) {
  867.             internal2.snoc(internal1.get(j));
  868.         }
  869.         setInner(internal2.getInner());
  870.     }
  871.  
  872.     /**
  873.      * Synonym for reverse(); drop(); reverse()
  874.      *
  875.      * @param num the number of elements to take
  876.      */
  877.     public void keepNotLast(int num) {
  878.         reverse();
  879.         drop(num);
  880.         reverse();
  881.     }
  882.  
  883.     /**
  884.      * Cuts this list down to all the elements before the first one that matches
  885.      * "filtFunc"
  886.      *
  887.      * @param filtFunc the predicate to search with
  888.      */
  889.     public void takeWhile(F<E, Boolean> filtFunc) {
  890.         final F<E, Boolean> p = filtFunc;
  891.         setInner(getInner().transformCS((new TransformCSFunc<E, E, Boolean>() {
  892.  
  893.             @Override
  894.             <M> M f(Monoid<M> m, F<E, M> f, E e, F2<M, Boolean, M> c, Boolean i) {
  895.                 if (p.f(e)) {
  896.                     return c.f(f.f(e), true);
  897.                 } else {
  898.                     return m.zero();
  899.                 }
  900.             }
  901.         }), true));
  902.     }
  903.  
  904.     /**
  905.      * Cuts this list down to the first element that matches "filtFunc" plus all
  906.      * the elements after that one
  907.      *
  908.      * @param filtFunc the predicate to search with
  909.      */
  910.     public void dropWhile(F<E, Boolean> filtFunc) {
  911.         final F<E, Boolean> p = filtFunc;
  912.         setInner(getInner().transformCS((new TransformCSFunc<E, E, Boolean>() {
  913.  
  914.             @Override
  915.             <M> M f(Monoid<M> m, F<E, M> f, E e, F2<M, Boolean, M> c, Boolean ok) {
  916.                 if (ok && p.f(e)) {
  917.                     return c.f(m.zero(), true);
  918.                 } else {
  919.                     return c.f(f.f(e), false);
  920.                 }
  921.             }
  922.         }), true));
  923.     }
  924.  
  925.     public <N> FMList<N> castElements() {
  926.         final F<E, N> cf = castFunc();
  927.         return map(cf);
  928.     }
  929.  
  930.     /**
  931.      * Gets the first element that matches filtFunc
  932.      *
  933.      * @param filtFunc the predicate to search with
  934.      * @return the element involved
  935.      * @throws NoSuchElementException if no element matches "filtFunc"
  936.      */
  937.     public E find(F<E, Boolean> filtFunc) throws NoSuchElementException {
  938.         final FMList<E> internal = clone();
  939.         internal.dropWhile(filtFunc);
  940.         if (internal.isEmpty()) {
  941.             throw new NoSuchElementException("no element matches the supplied predicate");
  942.         } else {
  943.             return internal.head();
  944.         }
  945.     }
  946.  
  947.     /**
  948.      * gets all except the first element
  949.      *
  950.      * @return the 'tail' of the list
  951.      */
  952.     public FMList<E> tail() {
  953.         final FMList<E> other = clone();
  954.         other.drop(1);
  955.         return other;
  956.     }
  957.  
  958.     /**
  959.      * gets all except the last element
  960.      *
  961.      * @return the 'init' of the list
  962.      */
  963.     public FMList<E> init() {
  964.         final FMList<E> other = this.clone();
  965.         other.reverse();
  966.         other.drop(1);
  967.         return other;
  968.     }
  969.  
  970.     /**
  971.      * reverses this list
  972.      */
  973.     public void reverse() {
  974.         final FM<E> i = getInner();
  975.         setInner(new FM<E>() {
  976.  
  977.             @Override
  978.             <X> X fm(Monoid<X> monoid, F<E, X> mapFunc) {
  979.                 return i.fm(dualMonoid(monoid), mapFunc);
  980.             }
  981.  
  982.             @Override
  983.             boolean couldBeFinite() {
  984.                 return i.couldBeFinite();
  985.             }
  986.         });
  987.     }
  988.  
  989.     @Override
  990.     public int size() {
  991.         F<E, Integer> cst1 = Function.constant(1);
  992.         return foldMap(Monoid.intAdditionMonoid, cst1).intValue();
  993.     }
  994.  
  995.     @Override
  996.     public boolean isEmpty() {
  997.         return size() == 0;
  998.     }
  999.  
  1000.     @Override
  1001.     public boolean contains(Object o) {
  1002.         final Object r = o;
  1003.         final FMList<E> testList = this.clone();
  1004.         testList.filter(new F<E, Boolean>() {
  1005.  
  1006.             @Override
  1007.             public Boolean f(E a) {
  1008.                 return (r == null ? a == null : r.equals(a));
  1009.             }
  1010.         });
  1011.         return !(testList.isEmpty());
  1012.     }
  1013.  
  1014.     @Override
  1015.     public Iterator<E> iterator() {
  1016.         final FMList<E> self = this;
  1017.         return new Iterator<E>() {
  1018.  
  1019.             private int currentIndex = 0;
  1020.  
  1021.             @Override
  1022.             public boolean hasNext() {
  1023.                 return currentIndex != self.size();
  1024.             }
  1025.  
  1026.             @Override
  1027.             public E next() {
  1028.                 if (hasNext()) {
  1029.                     currentIndex++;
  1030.                     return self.get(currentIndex);
  1031.                 } else {
  1032.                     throw new NoSuchElementException("this FMList is right-finite");
  1033.                 }
  1034.             }
  1035.  
  1036.             @Override
  1037.             public void remove() {
  1038.                 self.remove(currentIndex);
  1039.                 currentIndex--;
  1040.             }
  1041.         };
  1042.     }
  1043.  
  1044.     @Override
  1045.     public Object[] toArray() {
  1046.         final int s = size();
  1047.         final Object[] outArray = new Object[s];
  1048.         for (int i = 0; i < s; i++) {
  1049.             outArray[i] = get(i);
  1050.         }
  1051.         return outArray;
  1052.     }
  1053.  
  1054.     @Override
  1055.     @SuppressWarnings({"unchecked", "unchecked"})
  1056.     public <T> T[] toArray(T[] ts) {
  1057.         final int s1 = size();
  1058.         final int s2 = ts.length;
  1059.         if (s2 > s1) {
  1060.             final T[] outArray;
  1061.             outArray = ts;
  1062.             for (int i = 0; i < s1; i++) {
  1063.                 outArray[i] = (T) get(i);
  1064.             }
  1065.             return outArray;
  1066.         } else {
  1067.             final ArrayList<T> outList = new ArrayList<T>(s1);
  1068.             for (E x : this) {
  1069.                 outList.add((T) x);
  1070.             }
  1071.             return outList.toArray(ts);
  1072.         }
  1073.     }
  1074.  
  1075.     @Override
  1076.     public boolean add(E e) {
  1077.         this.snoc(e);
  1078.         return true;
  1079.     }
  1080.  
  1081.     @Override
  1082.     public boolean remove(Object o) {
  1083.         final Object r = o;
  1084.         final F<E, Boolean> filtFunc = new F<E, Boolean>() {
  1085.  
  1086.             @Override
  1087.             public Boolean f(E a) {
  1088.                 return !(r == null ? a == null : r.equals(a));
  1089.             }
  1090.         };
  1091.         final FMList<E> testList = clone();
  1092.         testList.filter(filtFunc);
  1093.         boolean answer = !(testList.isEmpty());
  1094.         if (answer) {
  1095.             final FMList<E> internal1 = clone();
  1096.             final FMList<E> internal2 = clone();
  1097.             internal1.takeWhile(filtFunc);
  1098.             internal2.dropWhile(filtFunc);
  1099.             internal2.tail();
  1100.             setInner(internal1.getInner().appendFM(internal2.getInner()));
  1101.         }
  1102.         return answer;
  1103.     }
  1104.  
  1105.     @Override
  1106.     public boolean containsAll(Collection<?> clctn) {
  1107.         final FMList<Object> c = new FMList<Object>(clctn);
  1108.         final FMList<E> self = this;
  1109.         return c.foldMap(Monoid.conjunctionMonoid, (new F<Object, Boolean>() {
  1110.  
  1111.             @Override
  1112.             @SuppressWarnings("unchecked")
  1113.             public Boolean f(Object a) {
  1114.                 return self.contains(a);
  1115.             }
  1116.         }));
  1117.     }
  1118.  
  1119.     @Override
  1120.     public boolean addAll(Collection<? extends E> clctn) {
  1121.         return addAll(0, clctn);
  1122.     }
  1123.  
  1124.     @Override
  1125.     public boolean addAll(int i, Collection<? extends E> clctn) {
  1126.         final FMList<E> alt1 = clone();
  1127.         final FMList<E> alt3 = clone();
  1128.         alt1.keepFirst(i);
  1129.         alt3.drop(i);
  1130.         final FMList<E> alt2 = new FMList<E>(clctn);
  1131.         setInner(alt1.getInner().appendFM(alt2.getInner()).appendFM(alt3.getInner()));
  1132.         return true;
  1133.     }
  1134.  
  1135.     /**
  1136.      * Monadic core operation
  1137.      *
  1138.      * @param <N> the final element type
  1139.      * @param bindFunc the function to bind this list to
  1140.      * @return the result of the binding
  1141.      */
  1142.     public <N> FMList<N> bind(F<E, FMList<N>> bindFunc) {
  1143.         final F<E, FMList<N>> g = bindFunc;
  1144.         return new FMList<N>(getInner().transform(new TransformFunc<N, E>() {
  1145.  
  1146.             @Override
  1147.             <M> M f(Monoid<M> monoid, F<N, M> func, E val) {
  1148.                 return g.f(val).foldMap(monoid, func);
  1149.             }
  1150.         }));
  1151.     }
  1152.  
  1153.     /**
  1154.      * Applicative core operation
  1155.      *
  1156.      * @param <N> the final element type
  1157.      * @param appFuncList the list of functions to apply over this list
  1158.      * @return the result of the application
  1159.      */
  1160.     public <N> FMList<N> apply(FMList<F<E, N>> appFuncList) {
  1161.         final FM<F<E, N>> gs = appFuncList.getInner();
  1162.         final FM<E> xs = getInner();
  1163.         return new FMList<N>(gs.transform(new TransformFunc<N, F<E, N>>() {
  1164.  
  1165.             @Override
  1166.             <M> M f(Monoid<M> monoid, F<N, M> func, F<E, N> val) {
  1167.                 return xs.fm(monoid, func.o(val));
  1168.             }
  1169.         }));
  1170.     }
  1171.  
  1172.     /**
  1173.      * Deconstructs this list into head() and tail()
  1174.      *
  1175.      * @return a tuple containing head() and tail()
  1176.      */
  1177.     public P2<E, FMList<E>> decons() {
  1178.         return P.p(head(), tail());
  1179.     }
  1180.  
  1181.     /**
  1182.      * Deconstructs this list into init() and last()
  1183.      *
  1184.      * @return a tuple containing init() and last()
  1185.      */
  1186.     public P2<FMList<E>, E> desnoc() {
  1187.         return P.p(init(), last());
  1188.     }
  1189.  
  1190.     /**
  1191.      * splits the list on the given index
  1192.      *
  1193.      * @param splitIndex the index after which to split the list
  1194.      * @return the split lists
  1195.      */
  1196.     public P2<FMList<E>, FMList<E>> split(int splitIndex) {
  1197.         final FMList<E> a = clone();
  1198.         final FMList<E> b = clone();
  1199.         a.keepFirst(splitIndex + 1);
  1200.         b.drop(splitIndex + 1);
  1201.         return P.p(a, b);
  1202.     }
  1203.  
  1204.     /**
  1205.      * Splits the list after the first element that matches "filtFunc"
  1206.      *
  1207.      * @param filtFunc the predicate by which to split the list
  1208.      * @return the split lists
  1209.      */
  1210.     public P2<FMList<E>, FMList<E>> splitOn(F<E, Boolean> filtFunc) {
  1211.         final FMList<E> a = clone();
  1212.         final FMList<E> b = clone();
  1213.         a.takeWhile(filtFunc);
  1214.         b.dropWhile(filtFunc);
  1215.         a.snoc(b.head());
  1216.         return P.p(a, b.tail());
  1217.     }
  1218.  
  1219.     /**
  1220.      * Produces a right-infinite list that contains the progressively iterated
  1221.      * application of "iterFunc" to "initialValue", starting with "initialValue"
  1222.      * itself
  1223.      *
  1224.      * @param <E>
  1225.      * @param iterFunc
  1226.      * @param initialValue
  1227.      * @return the infinite list
  1228.      */
  1229.     public static <E> FMList<E> iterate(F<E, E> iterFunc, E initialValue) {
  1230.         final F<E, E> f = iterFunc;
  1231.         final E x = initialValue;
  1232.         final FM<E> iterFM = new FM<E>() {
  1233.  
  1234.             @Override
  1235.             <X> X fm(Monoid<X> monoid, F<E, X> mapFunc) {
  1236.                 return monoid.sum(mapFunc.f(x), fm(monoid, mapFunc));
  1237.             }
  1238.  
  1239.             @Override
  1240.             boolean couldBeFinite() {
  1241.                 return false;
  1242.             }
  1243.         };
  1244.         return new FMList<E>(iterFM);
  1245.     }
  1246.  
  1247.     /**
  1248.      * cycleM()s a single element
  1249.      *
  1250.      * @param <E>
  1251.      * @param elem
  1252.      * @return the infinite list
  1253.      */
  1254.     public static <E> FMList<E> repeatM(E elem) {
  1255.         final FMList<E> result = new FMList<E>(elem);
  1256.         result.cycleM();
  1257.         return result;
  1258.     }
  1259.  
  1260.     /**
  1261.      * Repeats this list infinitely in the middle
  1262.      */
  1263.     public void cycleM() {
  1264.         final FM<E> l = getInner();
  1265.         final FMList<E> self = this;
  1266.         final FM<E> cycleFM = new FM<E>() {
  1267.  
  1268.             @Override
  1269.             <X> X fm(Monoid<X> monoid, F<E, X> mapFunc) {
  1270.                 final FMList<E> xx = self.clone();
  1271.                 xx.cycleM();
  1272.                 return (l.appendFM(xx.getInner()).appendFM(l)).fm(monoid, mapFunc);
  1273.             }
  1274.  
  1275.             @Override
  1276.             boolean couldBeFinite() {
  1277.                 return false;
  1278.             }
  1279.         };
  1280.         setInner(cycleFM);
  1281.     }
  1282.  
  1283.     /**
  1284.      * cycleR()s a single element
  1285.      *
  1286.      * @param <E>
  1287.      * @param elem
  1288.      * @return the infinite list
  1289.      */
  1290.     public static <E> FMList<E> repeatR(E elem) {
  1291.         final FMList<E> result = new FMList<E>(elem);
  1292.         result.cycleR();
  1293.         return result;
  1294.     }
  1295.  
  1296.     /**
  1297.      * Repeats this list infinitely to the right
  1298.      */
  1299.     public void cycleR() {
  1300.         final FM<E> l = getInner();
  1301.         final FMList<E> self = this;
  1302.         final FM<E> cycleFM = new FM<E>() {
  1303.  
  1304.             @Override
  1305.             <X> X fm(Monoid<X> monoid, F<E, X> mapFunc) {
  1306.                 final FMList<E> xx = self.clone();
  1307.                 xx.cycleR();
  1308.                 return ((xx.getInner()).appendFM(l)).fm(monoid, mapFunc);
  1309.             }
  1310.  
  1311.             @Override
  1312.             boolean couldBeFinite() {
  1313.                 return false;
  1314.             }
  1315.         };
  1316.         setInner(cycleFM);
  1317.     }
  1318.  
  1319.     /**
  1320.      * cycleL()s a single element
  1321.      *
  1322.      * @param <E>
  1323.      * @param elem
  1324.      * @return the infinite list
  1325.      */
  1326.     public static <E> FMList<E> repeatL(E elem) {
  1327.         final FMList<E> result = new FMList<E>(elem);
  1328.         result.cycleL();
  1329.         return result;
  1330.     }
  1331.  
  1332.     /**
  1333.      * Repeats this list infinitely to the left
  1334.      */
  1335.     public void cycleL() {
  1336.         final FM<E> l = getInner();
  1337.         final FMList<E> self = this;
  1338.         final FM<E> cycleFM = new FM<E>() {
  1339.  
  1340.             @Override
  1341.             <X> X fm(Monoid<X> monoid, F<E, X> mapFunc) {
  1342.                 final FMList<E> xx = self.clone();
  1343.                 xx.cycleL();
  1344.                 return (l.appendFM(xx.getInner())).fm(monoid, mapFunc);
  1345.             }
  1346.  
  1347.             @Override
  1348.             boolean couldBeFinite() {
  1349.                 return false;
  1350.             }
  1351.         };
  1352.         setInner(cycleFM);
  1353.     }
  1354.  
  1355.     /**
  1356.      * cycleB()s a single element
  1357.      *
  1358.      * @param <E>
  1359.      * @param elem
  1360.      * @return the infinite list
  1361.      */
  1362.     public static <E> FMList<E> repeatB(E elem) {
  1363.         final FMList<E> result = new FMList<E>(elem);
  1364.         result.cycleB();
  1365.         return result;
  1366.     }
  1367.  
  1368.     /**
  1369.      * Repeats this list infinitely to the left and right
  1370.      */
  1371.     public void cycleB() {
  1372.         final FM<E> l = getInner();
  1373.         final FMList<E> self = this;
  1374.         final FM<E> cycleFM = new FM<E>() {
  1375.  
  1376.             @Override
  1377.             <X> X fm(Monoid<X> monoid, F<E, X> mapFunc) {
  1378.                 final FMList<E> xx = self.clone();
  1379.                 xx.cycleB();
  1380.                 final FM<E> xi = xx.getInner();
  1381.                 return (xi.appendFM(l).appendFM(xi)).fm(monoid, mapFunc);
  1382.             }
  1383.  
  1384.             @Override
  1385.             boolean couldBeFinite() {
  1386.                 return false;
  1387.             }
  1388.         };
  1389.         setInner(cycleFM);
  1390.     }
  1391.  
  1392.     /**
  1393.      * Builds a list from a seed value. unfold() takes a seed and calls "bFunc"
  1394.      * on it. If the result is in right(), then it is appended to the prior. If
  1395.      * the result in in left(), then it is used in the core recursive call.
  1396.      *
  1397.      * @param <E>
  1398.      * @param <N>
  1399.      * @param bFunc
  1400.      * @param seedValue
  1401.      * @return the unfolded list
  1402.      */
  1403.     public static <E, N> FMList<E> unfold(F<N, FMList<Either<N, E>>> bFunc, N seedValue) {
  1404.         return new FMList<E>(FM.unfold(bFunc.andThen(new F<FMList<Either<N, E>>, FM<Either<N, E>>>() {
  1405.  
  1406.             @Override
  1407.             public FM<Either<N, E>> f(FMList<Either<N, E>> a) {
  1408.                 return a.getInner();
  1409.             }
  1410.         }), seedValue));
  1411.     }
  1412.  
  1413.     /**
  1414.      * right-biased Option-based version of unfold()
  1415.      *
  1416.      * @param <E> the final element type
  1417.      * @param <N> the seed type
  1418.      * @param bFunc the function to use for unfolding
  1419.      * @param seedValue the initial seed value
  1420.      * @return the unfolded list
  1421.      */
  1422.     public static <E, N> FMList<E> unfoldr(F<N, Option<P2<E, N>>> bFunc, N seedValue) {
  1423.         final F<N, Option<P2<E, N>>> g = bFunc;
  1424.         return unfold((new F<N, FMList<Either<N, E>>>() {
  1425.  
  1426.             @Override
  1427.             public FMList<Either<N, E>> f(N a) {
  1428.                 final Option<P2<E, N>> k = g.f(a);
  1429.                 if (k.isNone()) {
  1430.                     return new FMList<Either<N, E>>();
  1431.                 } else {
  1432.                     final P2<E, N> p = k.some();
  1433.                     final Either<N, E> va = Either.right(p._1());
  1434.                     final Either<N, E> vb = Either.left(p._2());
  1435.                     return new FMList<Either<N, E>>(va, vb);
  1436.                 }
  1437.             }
  1438.         }), seedValue);
  1439.     }
  1440.  
  1441.     /**
  1442.      * left-biased Option-based version of unfold()
  1443.      *
  1444.      * @param <E> the final element type
  1445.      * @param <N> the seed type
  1446.      * @param bFunc the function to use for unfolding
  1447.      * @param seedValue the initial seed value
  1448.      * @return the unfolded list
  1449.      */
  1450.     public static <E, N> FMList<E> unfoldl(F<N, Option<P2<E, N>>> bFunc, N seedValue) {
  1451.         FMList<E> result = unfoldr(bFunc, seedValue);
  1452.         result.reverse();
  1453.         return result;
  1454.     }
  1455.  
  1456.     @Override
  1457.     public boolean removeAll(Collection<?> clctn) {
  1458.         final FMList<Object> c = new FMList<Object>(clctn);
  1459.         final FMList<E> self = this;
  1460.         return c.foldMap(Monoid.conjunctionMonoid, (new F<Object, Boolean>() {
  1461.  
  1462.             @Override
  1463.             public Boolean f(Object a) {
  1464.                 return self.remove(a);
  1465.             }
  1466.         }));
  1467.     }
  1468.  
  1469.     @Override
  1470.     public boolean retainAll(Collection<?> clctn) {
  1471.         final FMList<Object> internal = (new FMList<Object>(clctn));
  1472.         internal.filter(new F<Object, Boolean>() {
  1473.  
  1474.             @Override
  1475.             public Boolean f(Object a) {
  1476.                 throw new UnsupportedOperationException("Not supported yet.");
  1477.             }
  1478.         });
  1479.         setInner(internal.map(new F<Object, E>() {
  1480.  
  1481.             @Override
  1482.             @SuppressWarnings("unchecked")
  1483.             public E f(Object a) {
  1484.                 return (E) a;
  1485.             }
  1486.         }).getInner());
  1487.         return true;
  1488.     }
  1489.  
  1490.     @Override
  1491.     public void clear() {
  1492.         FM<E> ii = FM.newFM();
  1493.         setInner(ii);
  1494.     }
  1495.  
  1496.     @Override
  1497.     public E get(int i) {
  1498.         final FMList<E> internal = clone();
  1499.         internal.drop(i);
  1500.         return internal.head();
  1501.     }
  1502.  
  1503.     @Override
  1504.     public E set(int i, E e) {
  1505.         final FMList<E> internal1 = clone();
  1506.         final FMList<E> internal2 = clone();
  1507.         internal1.take(i);
  1508.         internal2.drop(i + 1);
  1509.         final FM<E> i3 = FM.newFM(e);
  1510.         final E old = get(i);
  1511.         setInner(internal1.getInner().appendFM(i3).appendFM(internal2.getInner()));
  1512.         return old;
  1513.     }
  1514.  
  1515.     @Override
  1516.     public void add(int i, E e) {
  1517.         final FMList<E> internal1 = clone();
  1518.         final FMList<E> internal2 = clone();
  1519.         internal1.take(i);
  1520.         internal2.drop(i);
  1521.         final FM<E> i3 = FM.newFM(e);
  1522.         setInner(internal1.getInner().appendFM(i3).appendFM(internal2.getInner()));
  1523.     }
  1524.  
  1525.     @Override
  1526.     public E remove(int i) {
  1527.         final FMList<E> internal1 = clone();
  1528.         final FMList<E> internal2 = clone();
  1529.         internal1.take(i);
  1530.         internal2.drop(i + 1);
  1531.         final E old = get(i);
  1532.         setInner(internal1.getInner().appendFM(internal2.getInner()));
  1533.         return old;
  1534.     }
  1535.  
  1536.     public FMList<P2<Integer, E>> number() {
  1537.         final FMList<E> self = this;
  1538.         return self.tail().foldl((new F2<FMList<P2<Integer, E>>, E, FMList<P2<Integer, E>>>() {
  1539.  
  1540.             @Override
  1541.             public FMList<P2<Integer, E>> f(FMList<P2<Integer, E>> a, E b) {
  1542.                 final int k = a.last()._1().intValue();
  1543.                 a.snoc(P.p((k + 1), b));
  1544.                 return a;
  1545.             }
  1546.         }), (new FMList<P2<Integer, E>>(P.p(0, self.head()))));
  1547.     }
  1548.  
  1549.     @Override
  1550.     public int indexOf(Object o) {
  1551.         final FMList<P2<Integer, E>> internal = number();
  1552.         internal.retainAll(Collections.singletonList(o));
  1553.         if (internal.isEmpty()) {
  1554.             return -1;
  1555.         } else {
  1556.             return internal.head()._1().intValue();
  1557.         }
  1558.     }
  1559.  
  1560.     @Override
  1561.     public int lastIndexOf(Object o) {
  1562.         final FMList<P2<Integer, E>> internal = number();
  1563.         internal.retainAll(Collections.singletonList(o));
  1564.         if (internal.isEmpty()) {
  1565.             return -1;
  1566.         } else {
  1567.             return internal.last()._1().intValue();
  1568.         }
  1569.     }
  1570.  
  1571.     private static interface FMListIterator<E> extends ListIterator<E> {
  1572.  
  1573.         void setCurrentIndex(int i);
  1574.     }
  1575.  
  1576.     private FMListIterator<E> fmListIterator() {
  1577.         final FMList<E> self = this;
  1578.         return new FMListIterator<E>() {
  1579.  
  1580.             private int currentIndex = 0;
  1581.  
  1582.             @Override
  1583.             public boolean hasNext() {
  1584.                 return currentIndex != self.size();
  1585.             }
  1586.  
  1587.             @Override
  1588.             public E next() {
  1589.                 if (hasNext()) {
  1590.                     currentIndex++;
  1591.                     return self.get(currentIndex);
  1592.                 } else {
  1593.                     throw new NoSuchElementException("this FMList is right-finite");
  1594.                 }
  1595.             }
  1596.  
  1597.             @Override
  1598.             public void remove() {
  1599.                 self.remove(currentIndex);
  1600.                 currentIndex--;
  1601.             }
  1602.  
  1603.             @Override
  1604.             public boolean hasPrevious() {
  1605.                 return currentIndex != 0;
  1606.             }
  1607.  
  1608.             @Override
  1609.             public E previous() {
  1610.                 if (hasPrevious()) {
  1611.                     currentIndex--;
  1612.                     return self.get(currentIndex);
  1613.                 } else {
  1614.                     throw new NoSuchElementException("this FMList is left-finite");
  1615.                 }
  1616.             }
  1617.  
  1618.             @Override
  1619.             public int nextIndex() {
  1620.                 return currentIndex + 1;
  1621.             }
  1622.  
  1623.             @Override
  1624.             public int previousIndex() {
  1625.                 return currentIndex - 1;
  1626.             }
  1627.  
  1628.             @Override
  1629.             public void set(E e) {
  1630.                 self.set(currentIndex, e);
  1631.             }
  1632.  
  1633.             @Override
  1634.             public void add(E e) {
  1635.                 self.add(currentIndex, e);
  1636.                 currentIndex++;
  1637.             }
  1638.  
  1639.             @Override
  1640.             public void setCurrentIndex(int i) {
  1641.                 currentIndex = i;
  1642.             }
  1643.         };
  1644.     }
  1645.  
  1646.     @Override
  1647.     public ListIterator<E> listIterator() {
  1648.         return fmListIterator();
  1649.     }
  1650.  
  1651.     @Override
  1652.     public ListIterator<E> listIterator(int i) {
  1653.         final FMListIterator<E> li = fmListIterator();
  1654.         li.setCurrentIndex(i - 1);
  1655.         return li;
  1656.     }
  1657.  
  1658.     @Override
  1659.     public FMList<E> subList(int i, int i1) {
  1660.         FMList<E> internal = clone();
  1661.         internal.take(i);
  1662.         internal.drop(i1 - i);
  1663.         return internal;
  1664.     }
  1665.  
  1666.     @Override
  1667.     public void addFirst(E e) {
  1668.         cons(e);
  1669.     }
  1670.  
  1671.     @Override
  1672.     public void addLast(E e) {
  1673.         snoc(e);
  1674.     }
  1675.  
  1676.     @Override
  1677.     public boolean offerFirst(E e) {
  1678.         cons(e);
  1679.         return true;
  1680.     }
  1681.  
  1682.     @Override
  1683.     public boolean offerLast(E e) {
  1684.         snoc(e);
  1685.         return true;
  1686.     }
  1687.  
  1688.     @Override
  1689.     public E removeFirst() {
  1690.         E e = head();
  1691.         drop(1);
  1692.         return e;
  1693.     }
  1694.  
  1695.     @Override
  1696.     public E removeLast() {
  1697.         E e = last();
  1698.         take(size() - 1);
  1699.         return e;
  1700.     }
  1701.  
  1702.     @Override
  1703.     public E pollFirst() {
  1704.         if (isEmpty()) {
  1705.             return null;
  1706.         } else {
  1707.             return removeFirst();
  1708.         }
  1709.     }
  1710.  
  1711.     @Override
  1712.     public E pollLast() {
  1713.         if (isEmpty()) {
  1714.             return null;
  1715.         } else {
  1716.             return removeLast();
  1717.         }
  1718.     }
  1719.  
  1720.     @Override
  1721.     public E getFirst() {
  1722.         return head();
  1723.     }
  1724.  
  1725.     @Override
  1726.     public E getLast() {
  1727.         return last();
  1728.     }
  1729.  
  1730.     @Override
  1731.     public E peekFirst() {
  1732.         if (isEmpty()) {
  1733.             return null;
  1734.         } else {
  1735.             return getFirst();
  1736.         }
  1737.     }
  1738.  
  1739.     @Override
  1740.     public E peekLast() {
  1741.         if (isEmpty()) {
  1742.             return null;
  1743.         } else {
  1744.             return getLast();
  1745.         }
  1746.     }
  1747.  
  1748.     @Override
  1749.     public boolean removeFirstOccurrence(Object o) {
  1750.         return remove(o);
  1751.     }
  1752.  
  1753.     @Override
  1754.     public boolean removeLastOccurrence(Object o) {
  1755.         reverse();
  1756.         final boolean r = remove(o);
  1757.         reverse();
  1758.         return r;
  1759.     }
  1760.  
  1761.     @Override
  1762.     public boolean offer(E e) {
  1763.         return offerLast(e);
  1764.     }
  1765.  
  1766.     @Override
  1767.     public E remove() {
  1768.         return removeFirst();
  1769.     }
  1770.  
  1771.     @Override
  1772.     public E poll() {
  1773.         return pollFirst();
  1774.     }
  1775.  
  1776.     @Override
  1777.     public E element() {
  1778.         return getFirst();
  1779.     }
  1780.  
  1781.     @Override
  1782.     public E peek() {
  1783.         return peekFirst();
  1784.     }
  1785.  
  1786.     @Override
  1787.     public void push(E e) {
  1788.         addFirst(e);
  1789.     }
  1790.  
  1791.     @Override
  1792.     public E pop() {
  1793.         return removeFirst();
  1794.     }
  1795.  
  1796.     /**
  1797.      * Unseeded foldr()
  1798.      *
  1799.      * @param f the folding function
  1800.      * @return the final folded value
  1801.      * @throws NoSuchElementException if this list is empty
  1802.      */
  1803.     public E foldr1(F2<E, E, E> f) throws NoSuchElementException {
  1804.         if (isEmpty()) {
  1805.             throw new NoSuchElementException("cannot do an unseeded fold on an empty list");
  1806.         }
  1807.         return tail().foldr(f, head());
  1808.     }
  1809.  
  1810.     /**
  1811.      * First-class version of foldr1()
  1812.      *
  1813.      * @return the first-class function
  1814.      */
  1815.     public F<F2<E, E, E>, E> foldr1() {
  1816.         final FMList<E> self = this;
  1817.         return new F<F2<E, E, E>, E>() {
  1818.  
  1819.             @Override
  1820.             public E f(F2<E, E, E> a) {
  1821.                 return self.foldr1(a);
  1822.             }
  1823.         };
  1824.     }
  1825.  
  1826.     /**
  1827.      * Unseeded foldl()
  1828.      *
  1829.      * @param f the folding function
  1830.      * @return the final folded value
  1831.      * @throws NoSuchElementException if this list is empty
  1832.      */
  1833.     public E foldl1(F2<E, E, E> f) {
  1834.         if (isEmpty()) {
  1835.             throw new NoSuchElementException("cannot do an unseeded fold on an empty list");
  1836.         }
  1837.         return init().foldl(f, last());
  1838.     }
  1839.  
  1840.     /**
  1841.      * First-class version of foldl1()
  1842.      *
  1843.      * @return the first-class function
  1844.      */
  1845.     public F<F2<E, E, E>, E> foldl1() {
  1846.         final FMList<E> self = this;
  1847.         return new F<F2<E, E, E>, E>() {
  1848.  
  1849.             @Override
  1850.             public E f(F2<E, E, E> a) {
  1851.                 return self.foldl1(a);
  1852.             }
  1853.         };
  1854.     }
  1855.  
  1856.     /**
  1857.      * append()s all the inner lists
  1858.      *
  1859.      * @param <E> the inner element type
  1860.      * @param lli the multi-layer list
  1861.      * @return the joined list
  1862.      */
  1863.     public static <E> FMList<E> concat(FMList<FMList<E>> lli) {
  1864.         final Monoid<FMList<E>> m = fmListMonoid();
  1865.         return lli.fold(m);
  1866.     }
  1867.  
  1868.     /**
  1869.      * Gets the "&&" of all the booleans in "lli"
  1870.      *
  1871.      * @param lli the list to be folded
  1872.      * @return the final folded value
  1873.      * @throws InfiniteListException if "lli" is infinite
  1874.      */
  1875.     public static Boolean and(FMList<Boolean> lli) throws InfiniteListException {
  1876.         if (!(lli.couldBeFinite())) {
  1877.             throw new InfiniteListException(lli, "cannot fold an infinite list to a point");
  1878.         }
  1879.         final Monoid<Boolean> m = Monoid.conjunctionMonoid;
  1880.         return lli.fold(m);
  1881.     }
  1882.  
  1883.     /**
  1884.      * Gets the "||" of all the booleans in "lli"
  1885.      *
  1886.      * @param lli the list to be folded
  1887.      * @return the final folded value
  1888.      * @throws InfiniteListException if "lli" is infinite
  1889.      */
  1890.     public static Boolean or(FMList<Boolean> lli) throws InfiniteListException {
  1891.         if (!(lli.couldBeFinite())) {
  1892.             throw new InfiniteListException(lli, "cannot fold an infinite list to a point");
  1893.         }
  1894.         final Monoid<Boolean> m = Monoid.disjunctionMonoid;
  1895.         return lli.fold(m);
  1896.     }
  1897.  
  1898.     /**
  1899.      * map()s the list to booleans using "f", then "||"'s them
  1900.      *
  1901.      * @param f
  1902.      * @return the final folded value
  1903.      * @throws InfiniteListException if "lli" is infinite
  1904.      */
  1905.     public Boolean any(F<E, Boolean> f) throws InfiniteListException {
  1906.         if (!(couldBeFinite())) {
  1907.             throw new InfiniteListException(this, "cannot fold an infinite list to a point");
  1908.         }
  1909.         final Monoid<Boolean> m = Monoid.disjunctionMonoid;
  1910.         return foldMap(m, f);
  1911.     }
  1912.  
  1913.     /**
  1914.      * map()s the list to booleans using "f", then "&&"'s them
  1915.      *
  1916.      * @param f
  1917.      * @return the final folded value
  1918.      * @throws InfiniteListException if "lli" is infinite
  1919.      */
  1920.     public Boolean all(F<E, Boolean> f) throws InfiniteListException {
  1921.         if (!(couldBeFinite())) {
  1922.             throw new InfiniteListException(this, "cannot fold an infinite list to a point");
  1923.         }
  1924.         final Monoid<Boolean> m = Monoid.conjunctionMonoid;
  1925.         return foldMap(m, f);
  1926.     }
  1927.  
  1928.     /**
  1929.      * Gets the maximum value among all the "Comparable"'s in "lli"
  1930.      *
  1931.      * @param <E>
  1932.      * @param lli the list to be folded
  1933.      * @return the final folded value
  1934.      * @throws InfiniteListException if "lli" is infinite
  1935.      */
  1936.     public static <E extends Comparable<E>> E maximum(FMList<E> lli) throws InfiniteListException {
  1937.         if (!(lli.couldBeFinite())) {
  1938.             throw new InfiniteListException(lli, "cannot fold an infinite list to a point");
  1939.         }
  1940.         return lli.foldr1(new F2<E, E, E>() {
  1941.  
  1942.             @Override
  1943.             public E f(E a, E b) {
  1944.                 final int z = a.compareTo(b);
  1945.                 if (z <= 0) {
  1946.                     return b;
  1947.                 } else {
  1948.                     return a;
  1949.                 }
  1950.             }
  1951.         });
  1952.     }
  1953.  
  1954.     /**
  1955.      * Gets the minimum value among all the "Comparable"'s in "lli"
  1956.      *
  1957.      * @param <E>
  1958.      * @param lli the list to be folded
  1959.      * @return the final folded value
  1960.      * @throws InfiniteListException if "lli" is infinite
  1961.      */
  1962.     public static <E extends Comparable<E>> E minimum(FMList<E> lli) throws InfiniteListException {
  1963.         if (!(lli.couldBeFinite())) {
  1964.             throw new InfiniteListException(lli, "cannot fold an infinite list to a point");
  1965.         }
  1966.         return lli.foldr1(new F2<E, E, E>() {
  1967.  
  1968.             @Override
  1969.             public E f(E a, E b) {
  1970.                 final int z = a.compareTo(b);
  1971.                 if (z <= 0) {
  1972.                     return a;
  1973.                 } else {
  1974.                     return b;
  1975.                 }
  1976.             }
  1977.         });
  1978.     }
  1979.  
  1980.     /**
  1981.      * Gets the maximum value among all the values in the list
  1982.      *
  1983.      * @param cmp the ordering to use when comparing
  1984.      * @return the final folded value
  1985.      * @throws InfiniteListException if "lli" is infinite
  1986.      */
  1987.     public E maximum(Ord<E> cmp) throws InfiniteListException {
  1988.         if (!(couldBeFinite())) {
  1989.             throw new InfiniteListException(this, "cannot fold an infinite list to a point");
  1990.         }
  1991.         return foldr1(Function.uncurryF2(cmp.max));
  1992.     }
  1993.  
  1994.     /**
  1995.      * Gets the minimum value among all the values in the list
  1996.      *
  1997.      * @param cmp the ordering to use when comparing
  1998.      * @return the final folded value
  1999.      * @throws InfiniteListException if "lli" is infinite
  2000.      */
  2001.     public E minimum(Ord<E> cmp) throws InfiniteListException {
  2002.         if (!(couldBeFinite())) {
  2003.             throw new InfiniteListException(this, "cannot fold an infinite list to a point");
  2004.         }
  2005.         return foldr1(Function.uncurryF2(cmp.min));
  2006.     }
  2007.  
  2008.     /**
  2009.      * Gets the maximum value among all the values in the list
  2010.      *
  2011.      * @param cmp the comparator to use when comparing
  2012.      * @return the final folded value
  2013.      * @throws InfiniteListException if "lli" is infinite
  2014.      */
  2015.     public E maximum(Comparator<E> cmp) throws InfiniteListException {
  2016.         if (!(couldBeFinite())) {
  2017.             throw new InfiniteListException(this, "cannot fold an infinite list to a point");
  2018.         }
  2019.         final Comparator<E> k = cmp;
  2020.         return foldr1(new F2<E, E, E>() {
  2021.  
  2022.             @Override
  2023.             public E f(E a, E b) {
  2024.                 if (k.compare(a, b) < 0) {
  2025.                     return b;
  2026.                 } else {
  2027.                     return a;
  2028.                 }
  2029.             }
  2030.         });
  2031.     }
  2032.  
  2033.     /**
  2034.      * Gets the minimum value among all the values in the list
  2035.      *
  2036.      * @param cmp the comparator to use when comparing
  2037.      * @return the final folded value
  2038.      * @throws InfiniteListException if "lli" is infinite
  2039.      */
  2040.     public E minimum(Comparator<E> cmp) throws InfiniteListException {
  2041.         if (!(couldBeFinite())) {
  2042.             throw new InfiniteListException(this, "cannot fold an infinite list to a point");
  2043.         }
  2044.         final Comparator<E> k = cmp;
  2045.         return foldr1(new F2<E, E, E>() {
  2046.  
  2047.             @Override
  2048.             public E f(E a, E b) {
  2049.                 if (k.compare(a, b) < 0) {
  2050.                     return a;
  2051.                 } else {
  2052.                     return b;
  2053.                 }
  2054.             }
  2055.         });
  2056.     }
  2057.  
  2058.     @Override
  2059.     public Iterator<E> descendingIterator() {
  2060.         final FMList<E> self = this;
  2061.         return new Iterator<E>() {
  2062.  
  2063.             private int currentIndex = self.size();
  2064.  
  2065.             ;
  2066.  
  2067.             @Override
  2068.             public boolean hasNext() {
  2069.                 return currentIndex != 0;
  2070.             }
  2071.  
  2072.             @Override
  2073.             public E next() {
  2074.                 if (hasNext()) {
  2075.                     currentIndex--;
  2076.                     return self.get(currentIndex);
  2077.                 } else {
  2078.                     throw new NoSuchElementException("this FMList is left-finite");
  2079.                 }
  2080.             }
  2081.  
  2082.             @Override
  2083.             public void remove() {
  2084.                 self.remove(currentIndex);
  2085.                 currentIndex--;
  2086.             }
  2087.         };
  2088.     }
  2089.  
  2090.     FM<E> getInner() {
  2091.         return inner;
  2092.     }
  2093.  
  2094.     private void setInner(FM<E> inner) {
  2095.         this.inner = inner;
  2096.     }
  2097. }
clone this paste RAW Paste Data