001    package fj.data;
002    
003    import static fj.Bottom.error;
004    import fj.Effect;
005    import fj.F;
006    import fj.F2;
007    import fj.F3;
008    import fj.P;
009    import fj.P1;
010    import fj.P2;
011    import fj.Unit;
012    import static fj.Function.curry;
013    import static fj.Function.constant;
014    import static fj.Function.identity;
015    import static fj.Function.compose;
016    import static fj.P.p;
017    import static fj.P.p2;
018    import static fj.Unit.unit;
019    import static fj.data.Array.array;
020    import static fj.data.Array.mkArray;
021    import static fj.data.Option.none;
022    import static fj.data.Option.some;
023    import static fj.function.Booleans.not;
024    import static fj.pre.Ordering.GT;
025    import static fj.pre.Ord.intOrd;
026    import fj.pre.Ord;
027    import fj.pre.Equal;
028    import fj.pre.Monoid;
029    import fj.pre.Ordering;
030    
031    import java.util.AbstractCollection;
032    import java.util.Collection;
033    import java.util.Iterator;
034    import java.util.NoSuchElementException;
035    
036    /**
037     * Provides an in-memory, immutable, singly linked list.
038     *
039     * @version %build.number%<br>
040     *          <ul>
041     *          <li>$LastChangedRevision: 293 $</li>
042     *          <li>$LastChangedDate: 2010-01-17 13:16:41 +1000 (Sun, 17 Jan 2010) $</li>
043     *          </ul>
044     */
045    public abstract class List<A> implements Iterable<A> {
046      private List() {
047    
048      }
049    
050      /**
051       * Returns an iterator for this list. This method exists to permit the use in a <code>for</code>-each loop.
052       *
053       * @return A iterator for this list.
054       */
055      public Iterator<A> iterator() {
056        return toCollection().iterator();
057      }
058    
059      /**
060       * The first element of the linked list or fails for the empty list.
061       *
062       * @return The first element of the linked list or fails for the empty list.
063       */
064      public abstract A head();
065    
066      /**
067       * The list without the first element or fails for the empty list.
068       *
069       * @return The list without the first element or fails for the empty list.
070       */
071      public abstract List<A> tail();
072    
073      /**
074       * The length of this list.
075       *
076       * @return The length of this list.
077       */
078      public int length() {
079        return foldLeft(new F<Integer, F<A, Integer>>() {
080          public F<A, Integer> f(final Integer i) {
081            return new F<A, Integer>() {
082              public Integer f(final A a) {
083                return i + 1;
084              }
085            };
086          }
087        }, 0);
088      }
089    
090      /**
091       * Returns <code>true</code> if this list is empty, <code>false</code> otherwise.
092       *
093       * @return <code>true</code> if this list is empty, <code>false</code> otherwise.
094       */
095      public boolean isEmpty() {
096        return this instanceof Nil;
097      }
098    
099      /**
100       * Returns <code>false</code> if this list is empty, <code>true</code> otherwise.
101       *
102       * @return <code>false</code> if this list is empty, <code>true</code> otherwise.
103       */
104      public boolean isNotEmpty() {
105        return this instanceof Cons;
106      }
107    
108      /**
109       * Performs a reduction on this list using the given arguments.
110       *
111       * @param nil  The value to return if this list is empty.
112       * @param cons The function to apply to the head and tail of this list if it is not empty.
113       * @return A reduction on this list.
114       */
115      public <B> B list(final B nil, final F<A, F<List<A>, B>> cons) {
116        return isEmpty() ? nil : cons.f(head()).f(tail());
117      }
118    
119      /**
120       * Returns the head of this list if there is one or the given argument if this list is empty.
121       *
122       * @param a The argument to return if this list is empty.
123       * @return The head of this list if there is one or the given argument if this list is empty.
124       */
125      public A orHead(final P1<A> a) {
126        return isEmpty() ? a._1() : head();
127      }
128    
129      /**
130       * Returns the tail of this list if there is one or the given argument if this list is empty.
131       *
132       * @param as The argument to return if this list is empty.
133       * @return The tail of this list if there is one or the given argument if this list is empty.
134       */
135      public List<A> orTail(final P1<List<A>> as) {
136        return isEmpty() ? as._1() : tail();
137      }
138    
139      /**
140       * Returns an option projection of this list; <code>None</code> if empty, or the first element in
141       * <code>Some</code>.
142       *
143       * @return An option projection of this list.
144       */
145      public Option<A> toOption() {
146        return isEmpty() ? Option.<A>none() : some(head());
147      }
148    
149      /**
150       * Returns an either projection of this list; the given argument in <code>Left</code> if empty, or
151       * the first element in <code>Right</code>.
152       *
153       * @param x The value to return in left if this list is empty.
154       * @return An either projection of this list.
155       */
156      public <X> Either<X, A> toEither(final P1<X> x) {
157        return isEmpty() ? Either.<X, A>left(x._1()) : Either.<X, A>right(head());
158      }
159    
160      /**
161       * Returns a stream projection of this list.
162       *
163       * @return A stream projection of this list.
164       */
165      public Stream<A> toStream() {
166        final Stream<A> nil = Stream.nil();
167        return foldRight(new F<A, F<Stream<A>, Stream<A>>>() {
168          public F<Stream<A>, Stream<A>> f(final A a) {
169            return new F<Stream<A>, Stream<A>>() {
170              public Stream<A> f(final Stream<A> as) {
171                return as.cons(a);
172              }
173            };
174          }
175        }, nil);
176      }
177    
178      /**
179       * Returns a array projection of this list.
180       *
181       * @return A array projection of this list.
182       */
183      @SuppressWarnings({"unchecked"})
184      public Array<A> toArray() {
185        final Object[] a = new Object[length()];
186        List<A> x = this;
187        for (int i = 0; i < length(); i++) {
188          a[i] = x.head();
189          x = x.tail();
190        }
191    
192        return mkArray(a);
193      }
194    
195      /**
196       * Returns a array projection of this list.
197       *
198       * @param c The class type of the array to return.
199       * @return A array projection of this list.
200       */
201      @SuppressWarnings({"unchecked"})
202      public Array<A> toArray(final Class<A[]> c) {
203        final A[] a = (A[]) java.lang.reflect.Array.newInstance(c.getComponentType(), length());
204        List<A> x = this;
205        for (int i = 0; i < length(); i++) {
206          a[i] = x.head();
207          x = x.tail();
208        }
209    
210        return array(a);
211      }
212    
213      /**
214       * Prepends (cons) the given element to this list to product a new list.
215       *
216       * @param a The element to prepend.
217       * @return A new list with the given element at the head.
218       */
219      public List<A> cons(final A a) {
220        return new Cons<A>(a, this);
221      }
222    
223      /**
224       * Prepends (cons) the given element to this list to product a new list. This method is added to prevent conflict with
225       * overloads.
226       *
227       * @param a The element to prepend.
228       * @return A new list with the given element at the head.
229       */
230      public List<A> conss(final A a) {
231        return new Cons<A>(a, this);
232      }
233    
234      /**
235       * Maps the given function across this list.
236       *
237       * @param f The function to map across this list.
238       * @return A new list after the given function has been applied to each element.
239       */
240      public <B> List<B> map(final F<A, B> f) {
241        final Buffer<B> bs = Buffer.empty();
242    
243        for (List<A> xs = this; xs.isNotEmpty(); xs = xs.tail()) {
244          bs.snoc(f.f(xs.head()));
245        }
246    
247        return bs.toList();
248      }
249    
250      /**
251       * Performs a side-effect for each element of this list.
252       *
253       * @param f The side-effect to perform for the given element.
254       * @return The unit value.
255       */
256      public Unit foreach(final F<A, Unit> f) {
257        for (List<A> xs = this; xs.isNotEmpty(); xs = xs.tail()) {
258          f.f(xs.head());
259        }
260    
261        return unit();
262      }
263    
264      /**
265       * Performs a side-effect for each element of this list.
266       *
267       * @param f The side-effect to perform for the given element.
268       */
269      public void foreach(final Effect<A> f) {
270        for (List<A> xs = this; xs.isNotEmpty(); xs = xs.tail()) {
271          f.e(xs.head());
272        }
273      }
274    
275      /**
276       * Filters elements from this list by returning only elements which produce <code>true</code> when
277       * the given function is applied to them.
278       *
279       * @param f The predicate function to filter on.
280       * @return A new list whose elements all match the given predicate.
281       */
282      public List<A> filter(final F<A, Boolean> f) {
283        final Buffer<A> b = Buffer.empty();
284    
285        for (List<A> xs = this; xs.isNotEmpty(); xs = xs.tail()) {
286          final A h = xs.head();
287          if (f.f(h)) {
288            b.snoc(h);
289          }
290        }
291    
292        return b.toList();
293      }
294    
295      /**
296       * Filters elements from this list by returning only elements which produce <code>false</code> when
297       * the given function is applied to them.
298       *
299       * @param f The predicate function to filter on.
300       * @return A new list whose elements do not match the given predicate.
301       */
302      public List<A> removeAll(final F<A, Boolean> f) {
303        return filter(compose(not, f));
304      }
305    
306      /**
307       * Removes the first element that equals the given object.
308       * To remove all matches, use <code>removeAll(e.eq(a))</code>
309       *
310       * @param a The element to remove
311       * @param e An <code>Equals</code> instance for the element's type.
312       * @return A new list whose elements do not match the given predicate.
313       */
314      public List<A> delete(final A a, final Equal<A> e) {
315        final P2<List<A>, List<A>> p = span(compose(not, e.eq(a)));
316        return p._2().isEmpty() ? p._1() : p._1().append(p._2().tail());
317      }
318    
319      /**
320       * Returns the first elements of the head of this list that match the given predicate function.
321       *
322       * @param f The predicate function to apply on this list until it finds an element that does not
323       *          hold, or the list is exhausted.
324       * @return The first elements of the head of this list that match the given predicate function.
325       */
326      public List<A> takeWhile(final F<A, Boolean> f) {
327        final Buffer<A> b = Buffer.empty();
328        boolean taking = true;
329    
330        for (List<A> xs = this; xs.isNotEmpty() && taking; xs = xs.tail()) {
331          final A h = xs.head();
332          if (f.f(h)) {
333            b.snoc(h);
334          } else {
335            taking = false;
336          }
337        }
338    
339        return b.toList();
340      }
341    
342      /**
343       * Removes elements from the head of this list that do not match the given predicate function
344       * until an element is found that does match or the list is exhausted.
345       *
346       * @param f The predicate function to apply through this list.
347       * @return The list whose first element does not match the given predicate function.
348       */
349      public List<A> dropWhile(final F<A, Boolean> f) {
350        List<A> xs;
351    
352        //noinspection StatementWithEmptyBody
353        for (xs = this; xs.isNotEmpty() && f.f(xs.head()); xs = xs.tail()) ;
354    
355        return xs;
356      }
357    
358      /**
359       * Returns a tuple where the first element is the longest prefix of this list that satisfies
360       * the given predicate and the second element is the remainder of the list.
361       *
362       * @param p A predicate to be satisfied by a prefix of this list.
363       * @return A tuple where the first element is the longest prefix of this list that satisfies
364       *         the given predicate and the second element is the remainder of the list.
365       */
366      public P2<List<A>, List<A>> span(final F<A, Boolean> p) {
367        final Buffer<A> b = Buffer.empty();
368        for (List<A> xs = this; xs.isNotEmpty(); xs = xs.tail()) {
369          if (p.f(xs.head()))
370            b.snoc(xs.head());
371          else
372            return P.p(b.toList(), xs);
373        }
374        return P.p(b.toList(), List.<A>nil());
375      }
376    
377      /**
378       * Returns a tuple where the first element is the longest prefix of this list that does not satisfy
379       * the given predicate and the second element is the remainder of the list.
380       *
381       * @param p A predicate for an element to not satisfy by a prefix of this list.
382       * @return A tuple where the first element is the longest prefix of this list that does not satisfy
383       *         the given predicate and the second element is the remainder of the list.
384       */
385      public P2<List<A>, List<A>> breakk(final F<A, Boolean> p) {
386        return span(new F<A, Boolean>() {
387          public Boolean f(final A a) {
388            return !p.f(a);
389          }
390        });
391      }
392    
393      /**
394       * Groups elements according to the given equality implementation.
395       *
396       * @param e The equality implementation for the elements.
397       * @return A list of grouped elements.
398       */
399      public List<List<A>> group(final Equal<A> e) {
400        if (isEmpty())
401          return nil();
402        else {
403          final P2<List<A>, List<A>> z = tail().span(e.eq(head()));
404          return cons(z._1().cons(head()), z._2().group(e));
405        }
406      }
407    
408    
409      /**
410       * Binds the given function across each element of this list with a final join.
411       *
412       * @param f The function to apply to each element of this list.
413       * @return A new list after performing the map, then final join.
414       */
415      public <B> List<B> bind(final F<A, List<B>> f) {
416        final Buffer<B> b = Buffer.empty();
417    
418        for (List<A> xs = this; xs.isNotEmpty(); xs = xs.tail()) {
419          b.append(f.f(xs.head()));
420        }
421    
422        return b.toList();
423      }
424    
425      /**
426       * Binds the given function across each element of this list and the given list with a final
427       * join.
428       *
429       * @param lb A given list to bind the given function with.
430       * @param f  The function to apply to each element of this list and the given list.
431       * @return A new list after performing the map, then final join.
432       */
433      public <B, C> List<C> bind(final List<B> lb, final F<A, F<B, C>> f) {
434        return lb.apply(map(f));
435      }
436    
437      /**
438       * Binds the given function across each element of this list and the given list with a final
439       * join.
440       *
441       * @param lb A given list to bind the given function with.
442       * @param f  The function to apply to each element of this list and the given list.
443       * @return A new list after performing the map, then final join.
444       */
445      public <B, C> List<C> bind(final List<B> lb, final F2<A, B, C> f) {
446        return bind(lb, curry(f));
447      }
448    
449      /**
450       * Promotes the given function of arity-2 to a function on lists.
451       *
452       * @param f The functio to promote to a function on lists.
453       * @return The given function, promoted to operate on lists.
454       */
455      public static <A, B, C> F<List<A>, F<List<B>, List<C>>> liftM2(final F<A, F<B, C>> f) {
456        return curry(new F2<List<A>, List<B>, List<C>>() {
457          public List<C> f(final List<A> as, final List<B> bs) {
458            return as.bind(bs, f);
459          }
460        });
461      }
462    
463      /**
464       * Binds the given function across each element of this list and the given lists with a final
465       * join.
466       *
467       * @param lb A given list to bind the given function with.
468       * @param lc A given list to bind the given function with.
469       * @param f  The function to apply to each element of this list and the given lists.
470       * @return A new list after performing the map, then final join.
471       */
472      public <B, C, D> List<D> bind(final List<B> lb, final List<C> lc, final F<A, F<B, F<C, D>>> f) {
473        return lc.apply(bind(lb, f));
474      }
475    
476      /**
477       * Binds the given function across each element of this list and the given lists with a final
478       * join.
479       *
480       * @param lb A given list to bind the given function with.
481       * @param lc A given list to bind the given function with.
482       * @param ld A given list to bind the given function with.
483       * @param f  The function to apply to each element of this list and the given lists.
484       * @return A new list after performing the map, then final join.
485       */
486      public <B, C, D, E> List<E> bind(final List<B> lb, final List<C> lc, final List<D> ld,
487                                       final F<A, F<B, F<C, F<D, E>>>> f) {
488        return ld.apply(bind(lb, lc, f));
489      }
490    
491      /**
492       * Binds the given function across each element of this list and the given lists with a final
493       * join.
494       *
495       * @param lb A given list to bind the given function with.
496       * @param lc A given list to bind the given function with.
497       * @param ld A given list to bind the given function with.
498       * @param le A given list to bind the given function with.
499       * @param f  The function to apply to each element of this list and the given lists.
500       * @return A new list after performing the map, then final join.
501       */
502      public <B, C, D, E, F$> List<F$> bind(final List<B> lb, final List<C> lc, final List<D> ld, final List<E> le,
503                                            final F<A, F<B, F<C, F<D, F<E, F$>>>>> f) {
504        return le.apply(bind(lb, lc, ld, f));
505      }
506    
507      /**
508       * Binds the given function across each element of this list and the given lists with a final
509       * join.
510       *
511       * @param lb A given list to bind the given function with.
512       * @param lc A given list to bind the given function with.
513       * @param ld A given list to bind the given function with.
514       * @param le A given list to bind the given function with.
515       * @param lf A given list to bind the given function with.
516       * @param f  The function to apply to each element of this list and the given lists.
517       * @return A new list after performing the map, then final join.
518       */
519      public <B, C, D, E, F$, G> List<G> bind(final List<B> lb, final List<C> lc, final List<D> ld, final List<E> le,
520                                              final List<F$> lf, final F<A, F<B, F<C, F<D, F<E, F<F$, G>>>>>> f) {
521        return lf.apply(bind(lb, lc, ld, le, f));
522      }
523    
524      /**
525       * Binds the given function across each element of this list and the given lists with a final
526       * join.
527       *
528       * @param lb A given list to bind the given function with.
529       * @param lc A given list to bind the given function with.
530       * @param ld A given list to bind the given function with.
531       * @param le A given list to bind the given function with.
532       * @param lf A given list to bind the given function with.
533       * @param lg A given list to bind the given function with.
534       * @param f  The function to apply to each element of this list and the given lists.
535       * @return A new list after performing the map, then final join.
536       */
537      public <B, C, D, E, F$, G, H> List<H> bind(final List<B> lb, final List<C> lc, final List<D> ld, final List<E> le,
538                                                 final List<F$> lf, final List<G> lg,
539                                                 final F<A, F<B, F<C, F<D, F<E, F<F$, F<G, H>>>>>>> f) {
540        return lg.apply(bind(lb, lc, ld, le, lf, f));
541      }
542    
543      /**
544       * Binds the given function across each element of this list and the given lists with a final
545       * join.
546       *
547       * @param lb A given list to bind the given function with.
548       * @param lc A given list to bind the given function with.
549       * @param ld A given list to bind the given function with.
550       * @param le A given list to bind the given function with.
551       * @param lf A given list to bind the given function with.
552       * @param lg A given list to bind the given function with.
553       * @param lh A given list to bind the given function with.
554       * @param f  The function to apply to each element of this list and the given lists.
555       * @return A new list after performing the map, then final join.
556       */
557      public <B, C, D, E, F$, G, H, I> List<I> bind(final List<B> lb, final List<C> lc, final List<D> ld, final List<E> le,
558                                                    final List<F$> lf, final List<G> lg, final List<H> lh,
559                                                    final F<A, F<B, F<C, F<D, F<E, F<F$, F<G, F<H, I>>>>>>>> f) {
560        return lh.apply(bind(lb, lc, ld, le, lf, lg, f));
561      }
562    
563      /**
564       * Performs a bind across each list element, but ignores the element value each time.
565       *
566       * @param bs The list to apply in the final join.
567       * @return A new list after the final join.
568       */
569      public <B> List<B> sequence(final List<B> bs) {
570        final F<A, List<B>> c = constant(bs);
571        return bind(c);
572      }
573    
574      /**
575       * Performs function application within a list (applicative functor pattern).
576       *
577       * @param lf The list of functions to apply.
578       * @return A new list after applying the given list of functions through this list.
579       */
580      public <B> List<B> apply(final List<F<A, B>> lf) {
581        return lf.bind(new F<F<A, B>, List<B>>() {
582          public List<B> f(final F<A, B> f) {
583            return map(f);
584          }
585        });
586      }
587    
588      /**
589       * Appends the given list to this list.
590       *
591       * @param as The list to append to this one.
592       * @return A new list that has appended the given list.
593       */
594      public List<A> append(final List<A> as) {
595        return Buffer.fromList(this).append(as).toList();
596      }
597    
598      /**
599       * Performs a right-fold reduction across this list. This function uses O(length) stack space.
600       *
601       * @param f The function to apply on each element of the list.
602       * @param b The beginning value to start the application from.
603       * @return The final result after the right-fold reduction.
604       */
605      public <B> B foldRight(final F<A, F<B, B>> f, final B b) {
606        return isEmpty() ? b : f.f(head()).f(tail().foldRight(f, b));
607      }
608    
609      /**
610       * Performs a right-fold reduction across this list. This function uses O(length) stack space.
611       *
612       * @param f The function to apply on each element of the list.
613       * @param b The beginning value to start the application from.
614       * @return The final result after the right-fold reduction.
615       */
616      public <B> B foldRight(final F2<A, B, B> f, final B b) {
617        return foldRight(curry(f), b);
618      }
619    
620      /**
621       * Performs a left-fold reduction across this list. This function runs in constant space.
622       *
623       * @param f The function to apply on each element of the list.
624       * @param b The beginning value to start the application from.
625       * @return The final result after the left-fold reduction.
626       */
627      public <B> B foldLeft(final F<B, F<A, B>> f, final B b) {
628        B x = b;
629    
630        for (List<A> xs = this; !xs.isEmpty(); xs = xs.tail()) {
631          x = f.f(x).f(xs.head());
632        }
633    
634        return x;
635      }
636    
637      /**
638       * Performs a left-fold reduction across this list. This function runs in constant space.
639       *
640       * @param f The function to apply on each element of the list.
641       * @param b The beginning value to start the application from.
642       * @return The final result after the left-fold reduction.
643       */
644      public <B> B foldLeft(final F2<B, A, B> f, final B b) {
645        return foldLeft(curry(f), b);
646      }
647    
648      /**
649       * Takes the first 2 elements of the list and applies the function to them,
650       * then applies the function to the result and the third element and so on.
651       *
652       * @param f The function to apply on each element of the list.
653       * @return The final result after the left-fold reduction.
654       */
655      public A foldLeft1(final F2<A, A, A> f) {
656        return foldLeft1(curry(f));
657      }
658    
659      /**
660       * Takes the first 2 elements of the list and applies the function to them,
661       * then applies the function to the result and the third element and so on.
662       *
663       * @param f The function to apply on each element of the list.
664       * @return The final result after the left-fold reduction.
665       */
666      public A foldLeft1(final F<A, F<A, A>> f) {
667        if (isEmpty())
668          throw error("Undefined: foldLeft1 on empty list");
669        return tail().foldLeft(f, head());
670      }
671    
672      /**
673       * Reverse this list in constant stack space.
674       *
675       * @return A new list that is the reverse of this one.
676       */
677      public List<A> reverse() {
678        return foldLeft(new F<List<A>, F<A, List<A>>>() {
679          public F<A, List<A>> f(final List<A> as) {
680            return new F<A, List<A>>() {
681              public List<A> f(final A a) {
682                return cons(a, as);
683              }
684            };
685          }
686        }, List.<A>nil());
687      }
688    
689      /**
690       * Returns the element at the given index if it exists, fails otherwise.
691       *
692       * @param i The index at which to get the element to return.
693       * @return The element at the given index if it exists, fails otherwise.
694       */
695      public A index(final int i) {
696        if (i < 0 || i > length() - 1)
697          throw error("index " + i + " out of range on list with length " + length());
698        else {
699          List<A> xs = this;
700    
701          for (int c = 0; c < i; c++) {
702            xs = xs.tail();
703          }
704    
705          return xs.head();
706        }
707      }
708    
709      /**
710       * Takes the given number of elements from the head of this list if they are available.
711       *
712       * @param i The maximum number of elements to take from this list.
713       * @return A new list with a length the same, or less than, this list.
714       */
715      public List<A> take(final int i) {
716        return i <= 0 || isEmpty() ? List.<A>nil() : cons(head(), tail().take(i - 1));
717      }
718    
719      /**
720       * Drops the given number of elements from the head of this list if they are available.
721       *
722       * @param i The number of elements to drop from the head of this list.
723       * @return A list with a length the same, or less than, this list.
724       */
725      public List<A> drop(final int i) {
726        int c = 0;
727    
728        List<A> xs = this;
729    
730        //noinspection ForLoopWithMissingComponent,StatementWithEmptyBody
731        for (; xs.isNotEmpty() && c < i; xs = xs.tail())
732          c++;
733    
734        return xs;
735      }
736    
737      /**
738       * Splits this list into two lists at the given index. If the index goes out of bounds, then it is
739       * normalised so that this function never fails.
740       *
741       * @param i The index at which to split this list in two parts.
742       * @return A pair of lists split at the given index of this list.
743       */
744      public P2<List<A>, List<A>> splitAt(final int i) {
745        P2<List<A>, List<A>> s = p(List.<A>nil(), List.<A>nil());
746    
747        int c = 0;
748        for (List<A> xs = this; xs.isNotEmpty(); xs = xs.tail()) {
749          final A h = xs.head();
750          s = c < i ? s.map1(new F<List<A>, List<A>>() {
751            public List<A> f(final List<A> as) {
752              return as.snoc(h);
753            }
754          }) : s.map2(new F<List<A>, List<A>>() {
755            public List<A> f(final List<A> as) {
756              return as.snoc(h);
757            }
758          });
759          c++;
760        }
761    
762        return s;
763      }
764    
765      /**
766       * Splits this list into lists of the given size. If the size of this list is not evenly divisible by
767       * the given number, the last partition will contain the remainder.
768       *
769       * @param n The size of the partitions into which to split this list.
770       * @return A list of sublists of this list, of at most the given size.
771       */
772      public List<List<A>> partition(final int n) {
773        if (n < 1)
774          throw error("Can't create list partitions shorter than 1 element long.");
775        if (isEmpty())
776          throw error("Partition on empty list.");
777        return unfold(new F<List<A>, Option<P2<List<A>, List<A>>>>() {
778          public Option<P2<List<A>, List<A>>> f(final List<A> as) {
779            return as.isEmpty() ? Option.<P2<List<A>, List<A>>>none() : some(as.splitAt(n));
780          }
781        }, this);
782      }
783    
784      /**
785       * Returns the list of initial segments of this list, shortest first.
786       *
787       * @return The list of initial segments of this list, shortest first.
788       */
789      public List<List<A>> inits() {
790        List<List<A>> s = single(List.<A>nil());
791        if (isNotEmpty())
792          s = s.append(tail().inits().map(List.<A>cons().f(head())));
793        return s;
794      }
795    
796      /**
797       * Returns the list of final segments of this list, longest first.
798       *
799       * @return The list of final segments of this list, longest first.
800       */
801      public List<List<A>> tails() {
802        if (isEmpty())
803          return single(List.<A>nil());
804        else
805          return cons(this, tail().tails());
806      }
807    
808      /**
809       * Sorts this list using the given order over elements using a <em>merge sort</em> algorithm.
810       *
811       * @param o The order over the elements of this list.
812       * @return A sorted list according to the given order.
813       */
814      public List<A> sort(final Ord<A> o) {
815        if (isEmpty())
816          return nil();
817        else if (tail().isEmpty())
818          return this;
819        else {
820          final class Merge<A> {
821            List<A> merge(final List<A> xs, final List<A> ys, final Ord<A> o) {
822              return xs.isEmpty() ?
823                     ys :
824                     ys.isEmpty() ?
825                     xs :
826                     o.isLessThan(xs.head(), ys.head()) ?
827                     cons(xs.head(), merge(xs.tail(), ys, o)) :
828                     cons(ys.head(), merge(xs, ys.tail(), o));
829            }
830          }
831    
832          final P2<List<A>, List<A>> s = splitAt(length() / 2);
833          return new Merge<A>().merge(s._1().sort(o), s._2().sort(o), o);
834        }
835      }
836    
837      /**
838       * Zips this list with the given list using the given function to produce a new list. If this list
839       * and the given list have different lengths, then the longer list is normalised so this function
840       * never fails.
841       *
842       * @param bs The list to zip this list with.
843       * @param f  The function to zip this list and the given list with.
844       * @return A new list with a length the same as the shortest of this list and the given list.
845       */
846      public <B, C> List<C> zipWith(final List<B> bs, final F<A, F<B, C>> f) {
847        return isEmpty() || bs.isEmpty() ? List.<C>nil() : cons(f.f(head()).f(bs.head()), tail().zipWith(bs.tail(), f));
848      }
849    
850      /**
851       * Zips this list with the given list using the given function to produce a new list. If this list
852       * and the given list have different lengths, then the longer list is normalised so this function
853       * never fails.
854       *
855       * @param bs The list to zip this list with.
856       * @param f  The function to zip this list and the given list with.
857       * @return A new list with a length the same as the shortest of this list and the given list.
858       */
859      public <B, C> List<C> zipWith(final List<B> bs, final F2<A, B, C> f) {
860        return zipWith(bs, curry(f));
861      }
862    
863      /**
864       * Provides a first-class version of zipWith
865       *
866       * @return The first-class version of zipWith
867       */
868      public static <A, B, C> F<List<A>, F<List<B>, F<F<A, F<B, C>>, List<C>>>> zipWith() {
869        return curry(new F3<List<A>, List<B>, F<A, F<B, C>>, List<C>>() {
870          public List<C> f(final List<A> as, final List<B> bs, final F<A, F<B, C>> f) {
871            return as.zipWith(bs, f);
872          }
873        });
874      }
875    
876      /**
877       * Zips this list with the given list to produce a list of pairs. If this list and the given list
878       * have different lengths, then the longer list is normalised so this function never fails.
879       *
880       * @param bs The list to zip this list with.
881       * @return A new list with a length the same as the shortest of this list and the given list.
882       */
883      public <B> List<P2<A, B>> zip(final List<B> bs) {
884        final F<A, F<B, P2<A, B>>> __2 = p2();
885        return zipWith(bs, __2);
886      }
887    
888      /**
889       * The first-class version of the zip function.
890       *
891       * @return A function that zips the given lists to produce a list of pairs.
892       */
893      public static <A, B> F<List<A>, F<List<B>, List<P2<A, B>>>> zip() {
894        return curry(new F2<List<A>, List<B>, List<P2<A, B>>>() {
895          public List<P2<A, B>> f(final List<A> as, final List<B> bs) {
896            return as.zip(bs);
897          }
898        });
899      }
900    
901      /**
902       * Zips this list with the index of its element as a pair.
903       *
904       * @return A new list with the same length as this list.
905       */
906      public List<P2<A, Integer>> zipIndex() {
907        return zipWith(range(0, length()), new F<A, F<Integer, P2<A, Integer>>>() {
908          public F<Integer, P2<A, Integer>> f(final A a) {
909            return new F<Integer, P2<A, Integer>>() {
910              public P2<A, Integer> f(final Integer i) {
911                return p(a, i);
912              }
913            };
914          }
915        });
916      }
917    
918      /**
919       * Appends (snoc) the given element to this list to produce a new list.
920       *
921       * @param a The element to append to this list.
922       * @return A new list with the given element appended.
923       */
924      public List<A> snoc(final A a) {
925        return Buffer.fromList(this).snoc(a).toList();
926      }
927    
928      /**
929       * Returns <code>true</code> if the predicate holds for all of the elements of this list,
930       * <code>false</code> otherwise (<code>true</code> for the empty list).
931       *
932       * @param f The predicate function to test on each element of this list.
933       * @return <code>true</code> if the predicate holds for all of the elements of this list,
934       *         <code>false</code> otherwise.
935       */
936      public boolean forall(final F<A, Boolean> f) {
937        return isEmpty() || f.f(head()) && tail().forall(f);
938      }
939    
940      /**
941       * Returns <code>true</code> if the predicate holds for at least one of the elements of this list,
942       * <code>false</code> otherwise (<code>false</code> for the empty list).
943       *
944       * @param f The predicate function to test on the elements of this list.
945       * @return <code>true</code> if the predicate holds for at least one of the elements of this
946       *         list.
947       */
948      public boolean exists(final F<A, Boolean> f) {
949        return find(f).isSome();
950      }
951    
952      /**
953       * Finds the first occurrence of an element that matches the given predicate or no value if no
954       * elements match.
955       *
956       * @param f The predicate function to test on elements of this list.
957       * @return The first occurrence of an element that matches the given predicate or no value if no
958       *         elements match.
959       */
960      public Option<A> find(final F<A, Boolean> f) {
961        for (List<A> as = this; as.isNotEmpty(); as = as.tail()) {
962          if (f.f(as.head()))
963            return some(as.head());
964        }
965    
966        return none();
967      }
968    
969      /**
970       * Intersperses the given argument between each element of this list.
971       *
972       * @param a The separator to intersperse in this list.
973       * @return A list with the given separator interspersed.
974       */
975      public List<A> intersperse(final A a) {
976        return isEmpty() || tail().isEmpty() ?
977               this :
978               cons(head(), cons(a, tail().intersperse(a)));
979      }
980    
981      /**
982       * Intersperses this list through the given list then joins the results.
983       *
984       * @param as The list to intersperse through.
985       * @return This list through the given list then joins the results.
986       */
987      @SuppressWarnings({"unchecked"})
988      public List<A> intercalate(final List<List<A>> as) {
989        return join(as.intersperse(this));
990      }
991    
992      /**
993       * Removes duplicates according to object equality.
994       *
995       * @return A list without duplicates according to object equality.
996       */
997      public List<A> nub() {
998        return nub(Equal.<A>anyEqual());
999      }
1000    
1001      /**
1002       * Removes duplicates according to the given equality. Warning: O(n^2).
1003       *
1004       * @param eq Equality over the elements.
1005       * @return A list without duplicates.
1006       */
1007      public List<A> nub(final Equal<A> eq) {
1008        return isEmpty() ? this : cons(head(), tail().filter(new F<A, Boolean>() {
1009          public Boolean f(final A a) {
1010            return !eq.eq(a, head());
1011          }
1012        }).nub(eq));
1013      }
1014    
1015      /**
1016       * Removes duplicates according to the given ordering. This function is O(n).
1017       *
1018       * @param o An ordering for the elements.
1019       * @return A list without duplicates.
1020       */
1021      public List<A> nub(final Ord<A> o) {
1022        return sort(o).group(o.equal()).map(List.<A>head_());
1023      }
1024    
1025      /**
1026       * First-class head function.
1027       *
1028       * @return A function that gets the head of a given list.
1029       */
1030      public static <A> F<List<A>, A> head_() {
1031        return new F<List<A>, A>() {
1032          public A f(final List<A> list) {
1033            return list.head();
1034          }
1035        };
1036      }
1037    
1038      /**
1039       * First-class tail function.
1040       *
1041       * @return A function that gets the tail of a given list.
1042       */
1043      public static <A> F<List<A>, List<A>> tail_() {
1044        return new F<List<A>, List<A>>() {
1045          public List<A> f(final List<A> list) {
1046            return list.tail();
1047          }
1048        };
1049      }
1050    
1051      /**
1052       * Returns a new list of all the items in this list that do not appear in the given list.
1053       *
1054       * @param eq an equality for the items of the lists.
1055       * @param xs a list to subtract from this list.
1056       * @return a list of all the items in this list that do not appear in the given list.
1057       */
1058      public List<A> minus(final Equal<A> eq, final List<A> xs) {
1059        return removeAll(compose(Monoid.disjunctionMonoid.sumLeft(), xs.mapM(curry(eq.eq()))));
1060      }
1061    
1062      /**
1063       * Maps the given function of arity-2 across this list and returns a function that applies all the resulting
1064       * functions to a given argument.
1065       *
1066       * @param f A function of arity-2
1067       * @return A function that, when given an argument, applies the given function to that argument and every element
1068       *         in this list.
1069       */
1070      public <B, C> F<B, List<C>> mapM(final F<A, F<B, C>> f) {
1071        return List.sequence(map(f));
1072      }
1073    
1074      /**
1075       * Returns the index of the first element in this list which is equal (by the given equality) to the
1076       * query element, or None if there is no such element.
1077       *
1078       * @param e An equality for this list's elements.
1079       * @param a A query element.
1080       * @return The index of the first element in this list which is equal (by the given equality) to the
1081       *         query element, or None if there is no such element.
1082       */
1083      public Option<Integer> elementIndex(final Equal<A> e, final A a) {
1084        return lookup(e, zipIndex(), a);
1085      }
1086    
1087      /**
1088       * Returns the last element of this list. Undefined for the empty list.
1089       *
1090       * @return The last element of this list or throws an error if this list is empty.
1091       */
1092      public A last() {
1093        A a = head();
1094        for (List<A> xs = tail(); xs.isNotEmpty(); xs = xs.tail())
1095          a = xs.head();
1096        return a;
1097      }
1098    
1099      /**
1100       * Inserts the given element before the first element that is greater than or equal to it according
1101       * to the given ordering.
1102       *
1103       * @param f An ordering function to compare elements.
1104       * @param x The element to insert.
1105       * @return A new list with the given element inserted before the first element that is greater than or equal to
1106       *         it according to the given ordering.
1107       */
1108      public List<A> insertBy(final F<A, F<A, Ordering>> f, final A x) {
1109        List<A> ys = this;
1110        Buffer<A> xs = Buffer.empty();
1111        while (ys.isNotEmpty() && f.f(x).f(ys.head()) == GT) {
1112          xs = xs.snoc(ys.head());
1113          ys = ys.tail();
1114        }
1115        return xs.append(ys.cons(x)).toList();
1116      }
1117    
1118      /**
1119       * Returns the most common element in this list.
1120       *
1121       * @param o An ordering for the elements of the list.
1122       * @return The most common element in this list.
1123       */
1124      public A mode(final Ord<A> o) {
1125        return sort(o).group(o.equal()).maximum(intOrd.comap(List.<A>length_())).head();
1126      }
1127    
1128      /**
1129       * First-class length.
1130       *
1131       * @return A function that gets the length of a given list.
1132       */
1133      public static <A> F<List<A>, Integer> length_() {
1134        return new F<List<A>, Integer>() {
1135          public Integer f(final List<A> a) {
1136            return a.length();
1137          }
1138        };
1139      }
1140    
1141      /**
1142       * Returns the maximum element in this list according to the given ordering.
1143       *
1144       * @param o An ordering for the elements of the list.
1145       * @return The maximum element in this list according to the given ordering.
1146       */
1147      public A maximum(final Ord<A> o) {
1148        return foldLeft1(o.max);
1149      }
1150    
1151      /**
1152       * Returns the minimum element in this list according to the given ordering.
1153       *
1154       * @param o An ordering for the elements of the list.
1155       * @return The minimum element in this list according to the given ordering.
1156       */
1157      public A minimum(final Ord<A> o) {
1158        return foldLeft1(o.min);
1159      }
1160    
1161      /**
1162       * Projects an immutable collection of this list.
1163       *
1164       * @return An immutable collection of this list.
1165       */
1166      public Collection<A> toCollection() {
1167        return new AbstractCollection<A>() {
1168          public Iterator<A> iterator() {
1169            return new Iterator<A>() {
1170              private List<A> xs = List.this;
1171    
1172              public boolean hasNext() {
1173                return xs.isNotEmpty();
1174              }
1175    
1176              public A next() {
1177                if (xs.isEmpty())
1178                  throw new NoSuchElementException();
1179                else {
1180                  final A a = xs.head();
1181                  xs = xs.tail();
1182                  return a;
1183                }
1184              }
1185    
1186              public void remove() {
1187                throw new UnsupportedOperationException();
1188              }
1189            };
1190          }
1191    
1192          public int size() {
1193            return length();
1194          }
1195        };
1196      }
1197    
1198      private static final class Nil<A> extends List<A> {
1199        public A head() {
1200          throw error("head on empty list");
1201        }
1202    
1203        public List<A> tail() {
1204          throw error("tail on empty list");
1205        }
1206      }
1207    
1208      private static final class Cons<A> extends List<A> {
1209        private final A head;
1210        private List<A> tail;
1211    
1212        Cons(final A head, final List<A> tail) {
1213          this.head = head;
1214          this.tail = tail;
1215        }
1216    
1217        public A head() {
1218          return head;
1219        }
1220    
1221        public List<A> tail() {
1222          return tail;
1223        }
1224    
1225        private void tail(final List<A> tail) {
1226          this.tail = tail;
1227        }
1228      }
1229    
1230      /**
1231       * Constructs a list from the given elements.
1232       *
1233       * @param as The elements to construct a list with.
1234       * @return A list with the given elements.
1235       */
1236      public static <A> List<A> list(final A... as) {
1237        return array(as).toList();
1238      }
1239    
1240      /**
1241       * Returns an empty list.
1242       *
1243       * @return An empty list.
1244       */
1245      public static <A> List<A> nil() {
1246        return new Nil<A>();
1247      }
1248    
1249      /**
1250       * Returns a function that prepends (cons) an element to a list to produce a new list.
1251       *
1252       * @return A function that prepends (cons) an element to a list to produce a new list.
1253       */
1254      public static <A> F<A, F<List<A>, List<A>>> cons() {
1255        return new F<A, F<List<A>, List<A>>>() {
1256          public F<List<A>, List<A>> f(final A a) {
1257            return new F<List<A>, List<A>>() {
1258              public List<A> f(final List<A> tail) {
1259                return cons(a, tail);
1260              }
1261            };
1262          }
1263        };
1264      }
1265    
1266      /**
1267       * Returns a function that prepends a value to the given list.
1268       *
1269       * @param tail The list to prepend to.
1270       * @return A function that prepends a value to the given list.
1271       */
1272      public static <A> F<A, List<A>> cons(final List<A> tail) {
1273        return new F<A, List<A>>() {
1274          public List<A> f(final A a) {
1275            return tail.cons(a);
1276          }
1277        };
1278      }
1279    
1280      /**
1281       * Returns a function that prepends the given value to a list.
1282       *
1283       * @param a The value to prepend to a list.
1284       * @return A function that prepends the given value to a list.
1285       */
1286      public static <A> F<List<A>, List<A>> cons_(final A a) {
1287        return new F<List<A>, List<A>>() {
1288          public List<A> f(final List<A> as) {
1289            return as.cons(a);
1290          }
1291        };
1292      }
1293    
1294      /**
1295       * Prepends the given head element to the given tail element to produce a new list.
1296       *
1297       * @param head The element to prepend.
1298       * @param tail The list to prepend to.
1299       * @return The list with the given element prepended.
1300       */
1301      public static <A> List<A> cons(final A head, final List<A> tail) {
1302        return new Cons<A>(head, tail);
1303      }
1304    
1305      /**
1306       * Returns a function that determines whether a given list is empty.
1307       *
1308       * @return A function that determines whether a given list is empty.
1309       */
1310      public static <A> F<List<A>, Boolean> isEmpty_() {
1311        return new F<List<A>, Boolean>() {
1312          public Boolean f(final List<A> as) {
1313            return as.isEmpty();
1314          }
1315        };
1316      }
1317    
1318      /**
1319       * Returns a function that determines whether a given list is not empty.
1320       *
1321       * @return A function that determines whether a given list is not empty.
1322       */
1323      public static <A> F<List<A>, Boolean> isNotEmpty_() {
1324        return new F<List<A>, Boolean>() {
1325          public Boolean f(final List<A> as) {
1326            return as.isNotEmpty();
1327          }
1328        };
1329      }
1330    
1331      /**
1332       * Joins the given list of lists using a bind operation.
1333       *
1334       * @param o The list of lists to join.
1335       * @return A new list that is the join of the given lists.
1336       */
1337      public static <A> List<A> join(final List<List<A>> o) {
1338        final F<List<A>, List<A>> id = identity();
1339        return o.bind(id);
1340      }
1341    
1342      /**
1343       * A first-class version of join
1344       *
1345       * @return A function that joins a list of lists using a bind operation.
1346       */
1347      public static <A> F<List<List<A>>, List<A>> join() {
1348        return new F<List<List<A>>, List<A>>() {
1349          public List<A> f(final List<List<A>> as) {
1350            return join(as);
1351          }
1352        };
1353      }
1354    
1355      /**
1356       * Unfolds across the given function starting at the given value to produce a list.
1357       *
1358       * @param f The function to unfold across.
1359       * @param b The start value to begin the unfold.
1360       * @return A new list that is a result of unfolding until the function does not produce a value.
1361       */
1362      public static <A, B> List<A> unfold(final F<B, Option<P2<A, B>>> f, final B b) {
1363        Buffer<A> buf = Buffer.empty();
1364        for (Option<P2<A, B>> o = f.f(b); o.isSome(); o = f.f(o.some()._2())) {
1365          buf = buf.snoc(o.some()._1());
1366        }
1367        return buf.toList();
1368      }
1369    
1370      /**
1371       * Transforms a list of pairs into a list of first components and a list of second components.
1372       *
1373       * @param xs The list of pairs to transform.sp
1374       * @return A list of first components and a list of second components.
1375       */
1376      public static <A, B> P2<List<A>, List<B>> unzip(final List<P2<A, B>> xs) {
1377        Buffer<A> ba = Buffer.empty();
1378        Buffer<B> bb = Buffer.empty();
1379        for (final P2<A, B> p : xs) {
1380          ba = ba.snoc(p._1());
1381          bb = bb.snoc(p._2());
1382        }
1383        return P.p(ba.toList(), bb.toList());
1384      }
1385    
1386      /**
1387       * Returns a list of the given value replicated the given number of times.
1388       *
1389       * @param n The number of times to replicate the given value.
1390       * @param a The value to replicate.
1391       * @return A list of the given value replicated the given number of times.
1392       */
1393      public static <A> List<A> replicate(final int n, final A a) {
1394        return n <= 0 ? List.<A>nil() : replicate(n - 1, a).cons(a);
1395      }
1396    
1397      /**
1398       * Returns a list of integers from the given <code>from</code> value (inclusive) to the given
1399       * <code>to</code> value (exclusive).
1400       *
1401       * @param from The minimum value for the list (inclusive).
1402       * @param to   The maximum value for the list (exclusive).
1403       * @return A list of integers from the given <code>from</code> value (inclusive) to the given
1404       *         <code>to</code> value (exclusive).
1405       */
1406      public static List<Integer> range(final int from, final int to) {
1407        return from >= to ? List.<Integer>nil() : cons(from, range(from + 1, to));
1408      }
1409    
1410      /**
1411       * Returns a list of characters from the given string. The inverse of this function is {@link
1412       * #asString(List)}.
1413       *
1414       * @param s The string to produce the list of characters from.
1415       * @return A list of characters from the given string.
1416       */
1417      public static List<Character> fromString(final String s) {
1418        List<Character> cs = nil();
1419    
1420        for (int i = s.length() - 1; i >= 0; i--)
1421          cs = cons(s.charAt(i), cs);
1422    
1423        return cs;
1424      }
1425    
1426      /**
1427       * A first-class <code>fromString</code>.
1428       *
1429       * @return A first-class <code>fromString</code>.
1430       */
1431      public static F<String, List<Character>> fromString() {
1432        return new F<String, List<Character>>() {
1433          public List<Character> f(final String s) {
1434            return fromString(s);
1435          }
1436        };
1437      }
1438    
1439      /**
1440       * Returns a string from the given list of characters. The invers of this function is {@link
1441       * #fromString(String)}.
1442       *
1443       * @param cs The list of characters to produce the string from.
1444       * @return A string from the given list of characters.
1445       */
1446      public static String asString(final List<Character> cs) {
1447        final StringBuilder sb = new StringBuilder();
1448    
1449        cs.foreach(new F<Character, Unit>() {
1450          public Unit f(final Character c) {
1451            sb.append(c);
1452            return unit();
1453          }
1454        });
1455        return sb.toString();
1456      }
1457    
1458      /**
1459       * A first-class <code>asString</code>.
1460       *
1461       * @return A first-class <code>asString</code>.
1462       */
1463      public static F<List<Character>, String> asString() {
1464        return new F<List<Character>, String>() {
1465          public String f(final List<Character> cs) {
1466            return asString(cs);
1467          }
1468        };
1469      }
1470    
1471      /**
1472       * Returns a list of one element containing the given value.
1473       *
1474       * @param a The value for the head of the returned list.
1475       * @return A list of one element containing the given value.
1476       */
1477      public static <A> List<A> single(final A a) {
1478        return cons(a, List.<A>nil());
1479      }
1480    
1481      /**
1482       * Creates a list where the first item is calculated by applying the function on the third argument,
1483       * the second item by applying the function on the previous result and so on.
1484       *
1485       * @param f The function to iterate with.
1486       * @param p The predicate which must be true for the next item in order to continue the iteration.
1487       * @param a The input to the first iteration.
1488       * @return A list where the first item is calculated by applying the function on the third argument,
1489       *         the second item by applying the function on the previous result and so on.
1490       */
1491      public static <A> List<A> iterateWhile(final F<A, A> f, final F<A, Boolean> p, final A a) {
1492        return unfold(
1493            new F<A, Option<P2<A, A>>>() {
1494              public Option<P2<A, A>> f(final A o) {
1495                return Option.iif(new F<P2<A, A>, Boolean>() {
1496                  public Boolean f(final P2<A, A> p2) {
1497                    return p.f(o);
1498                  }
1499                }, P.p(o, f.f(o)));
1500              }
1501            }
1502            , a);
1503      }
1504    
1505      /**
1506       * Returns an associated value with the given key in the list of pairs.
1507       *
1508       * @param e The test for equality on keys.
1509       * @param x The list of pairs to search.
1510       * @param a The key value to find the associated value of.
1511       * @return An associated value with the given key in the list of pairs.
1512       */
1513      public static <A, B> Option<B> lookup(final Equal<A> e, final List<P2<A, B>> x, final A a) {
1514        return x.find(new F<P2<A, B>, Boolean>() {
1515          public Boolean f(final P2<A, B> p) {
1516            return e.eq(p._1(), a);
1517          }
1518        }).map(P2.<A, B>__2());
1519      }
1520    
1521      /**
1522       * Returns a partially applied version of {@link #lookup(Equal, List, Object)}.
1523       *
1524       * @param e The test for equality on keys.
1525       * @return A partially applied version of {@link #lookup(Equal, List, Object)}.
1526       */
1527      public static <A, B> F2<List<P2<A, B>>, A, Option<B>> lookup(final Equal<A> e) {
1528        return new F2<List<P2<A, B>>, A, Option<B>>() {
1529          public Option<B> f(final List<P2<A, B>> x, final A a) {
1530            return lookup(e, x, a);
1531          }
1532        };
1533      }
1534    
1535      /**
1536       * Provides a first-class version of bind()
1537       *
1538       * @return The bind function for lists.
1539       */
1540      public static <A, B> F<F<A, List<B>>, F<List<A>, List<B>>> bind_() {
1541        return curry(new F2<F<A, List<B>>, List<A>, List<B>>() {
1542          public List<B> f(final F<A, List<B>> f, final List<A> as) {
1543            return as.bind(f);
1544          }
1545        });
1546      }
1547    
1548      /**
1549       * Provides a first-class version of map()
1550       *
1551       * @return The map function for lists.
1552       */
1553      public static <A, B> F<F<A, B>, F<List<A>, List<B>>> map_() {
1554        return curry(new F2<F<A, B>, List<A>, List<B>>() {
1555          public List<B> f(final F<A, B> f, final List<A> as) {
1556            return as.map(f);
1557          }
1558        });
1559      }
1560    
1561      /**
1562       * Turn a list of functions into a function returning a list.
1563       *
1564       * @param fs The list of functions to sequence into a single function that returns a list.
1565       * @return A function that, when given an argument, applies all the functions in the given list to it
1566       *         and returns a list of the results.
1567       */
1568      public static <A, B> F<B, List<A>> sequence(final List<F<B, A>> fs) {
1569        return fs.foldRight(fj.Function.<A, List<A>, List<A>, B>lift(List.<A>cons()), fj.Function
1570            .<B, List<A>>constant(List.<A>nil()));
1571      }
1572    
1573      /**
1574       * Provides a first-class version of foldLeft.
1575       *
1576       * @return The left fold function for lists.
1577       */
1578      public static <A, B> F<F<B, F<A, B>>, F<B, F<List<A>, B>>> foldLeft() {
1579        return curry(new F3<F<B, F<A, B>>, B, List<A>, B>() {
1580          public B f(final F<B, F<A, B>> f, final B b, final List<A> as) {
1581            return as.foldLeft(f, b);
1582          }
1583        });
1584      }
1585    
1586      /**
1587       * Provides a first-class version of take.
1588       *
1589       * @return First-class version of take.
1590       */
1591      public static <A> F<Integer, F<List<A>, List<A>>> take() {
1592        return curry(new F2<Integer, List<A>, List<A>>() {
1593          public List<A> f(final Integer n, final List<A> as) {
1594            return as.take(n);
1595          }
1596        });
1597      }
1598    
1599      /**
1600       * Takes the given iterable to a list.
1601       *
1602       * @param i The iterable to take to a list.
1603       * @return A list from the given iterable.
1604       */
1605      public static <A> List<A> iterableList(final Iterable<A> i) {
1606        final Buffer<A> bs = Buffer.empty();
1607    
1608        for (final A a : i)
1609          bs.snoc(a);
1610    
1611        return bs.toList();
1612      }
1613    
1614    
1615      /**
1616       * A mutable, singly linked list. This structure should be used <em>very</em> sparingly, in favour
1617       * of the {@link List immutable singly linked list structure}.
1618       */
1619      public static final class Buffer<A> implements Iterable<A> {
1620        private List<A> start = nil();
1621        private Cons<A> tail;
1622        private boolean exported;
1623    
1624        /**
1625         * Returns an iterator for this buffer. This method exists to permit the use in a <code>for</code>-each loop.
1626         *
1627         * @return A iterator for this buffer.
1628         */
1629        public Iterator<A> iterator() {
1630          return start.iterator();
1631        }
1632    
1633        /**
1634         * Appends (snoc) the given element to this buffer to produce a new buffer.
1635         *
1636         * @param a The element to append to this buffer.
1637         * @return A new buffer with the given element appended.
1638         */
1639        public Buffer<A> snoc(final A a) {
1640          if (exported)
1641            copy();
1642    
1643          final Cons<A> t = new Cons<A>(a, List.<A>nil());
1644    
1645          if (tail == null)
1646            start = t;
1647          else
1648            tail.tail(t);
1649    
1650          tail = t;
1651    
1652          return this;
1653        }
1654    
1655        /**
1656         * Appends the given buffer to this buffer.
1657         *
1658         * @param as The buffer to append to this one.
1659         * @return A new buffer that has appended the given buffer.
1660         */
1661        public Buffer<A> append(final List<A> as) {
1662          for (List<A> xs = as; xs.isNotEmpty(); xs = xs.tail())
1663            snoc(xs.head());
1664    
1665          return this;
1666        }
1667    
1668        /**
1669         * Returns an immutable list projection of this buffer. Modifications to the underlying buffer
1670         * will <em>not</em> be reflected in returned lists.
1671         *
1672         * @return An immutable list projection of this buffer.
1673         */
1674        public List<A> toList() {
1675          exported = !start.isEmpty();
1676          return start;
1677        }
1678    
1679        /**
1680         * Projects an immutable collection of this buffer.
1681         *
1682         * @return An immutable collection of this buffer.
1683         */
1684        public Collection<A> toCollection() {
1685          return start.toCollection();
1686        }
1687    
1688        /**
1689         * An empty buffer.
1690         *
1691         * @return An empty buffer.
1692         */
1693        public static <A> Buffer<A> empty() {
1694          return new Buffer<A>();
1695        }
1696    
1697        /**
1698         * Constructs a buffer from the given list.
1699         *
1700         * @param as The list to construct a buffer with.
1701         * @return A buffer from the given list.
1702         */
1703        public static <A> Buffer<A> fromList(final List<A> as) {
1704          final Buffer<A> b = new Buffer<A>();
1705    
1706          for (List<A> xs = as; xs.isNotEmpty(); xs = xs.tail())
1707            b.snoc(xs.head());
1708    
1709          return b;
1710        }
1711    
1712        /**
1713         * Takes the given iterable to a buffer.
1714         *
1715         * @param i The iterable to take to a buffer.
1716         * @return A buffer from the given iterable.
1717         */
1718        public static <A> Buffer<A> iterableBuffer(final Iterable<A> i) {
1719          final Buffer<A> b = Buffer.empty();
1720    
1721          for (final A a : i)
1722            b.snoc(a);
1723    
1724          return b;
1725        }
1726    
1727        private void copy() {
1728          List<A> s = start;
1729          final Cons<A> t = tail;
1730          start = nil();
1731          exported = false;
1732          while (s != t) {
1733            snoc(s.head());
1734            s = s.tail();
1735          }
1736    
1737          if (t != null)
1738            snoc(t.head());
1739        }
1740      }
1741    }