package fj.data;

import static fj.Bottom.error;

import fj.F0;

import fj.F2Functions;

import fj.Equal;

import fj.F;

import fj.F2;

import fj.Function;

import fj.Hash;

import fj.Monoid;

import fj.Ord;

import fj.P;

import fj.P1;

import fj.P2;

import fj.Show;

import fj.Unit;

import static fj.Function.*;

import static fj.P.p;

import static fj.P.p2;

import static fj.Unit.unit;

import static fj.data.Array.mkArray;

import static fj.data.List.Buffer.*;

import static fj.data.Option.none;

import static fj.data.Option.some;

import static fj.data.optic.Optional.optional;

import static fj.data.optic.Prism.prism;

import static fj.data.vector.V.v;

import static fj.function.Booleans.not;

import static fj.Ordering.GT;

import static fj.Ord.intOrd;

import fj.Ordering;

import fj.control.Trampoline;

import fj.control.parallel.Promise;

import fj.control.parallel.Strategy;

import fj.data.optic.Optional;

import fj.data.optic.PTraversal;

import fj.data.optic.Prism;

import fj.data.optic.Traversal;

import fj.data.vector.V2;

import fj.function.Effect1;

import java.util.AbstractCollection;

import java.util.Collection;

import java.util.Iterator;

import java.util.NoSuchElementException;

/**

* Provides an in-memory, immutable, singly linked list.

*

* @version %build.number%

*/

public abstract class List<A> implements Iterable<A> {

private List() {

}

/**

* Returns an iterator for this list. This method exists to permit the use in a <code>for</code>-each loop.

*

* @return A iterator for this list.

*/

public final Iterator<A> iterator() {

return toCollection().iterator();

}

/**

* The first element of the linked list or fails for the empty list.

*

* @return The first element of the linked list or fails for the empty list.

*/

public abstract A head();

/**

* The list without the first element or fails for the empty list.

*

* @return The list without the first element or fails for the empty list.

*/

public abstract List<A> tail();

/**

* The length of this list.

*

* @return The length of this list.

*/

public final int length() {

// WARNING: In JDK 8, update 25 (current version) the following code triggers an internal JDK compiler error, likely due to https://bugs.openjdk.java.net/browse/JDK-8062253. The code below is a workaround for this compiler bug.

// return foldLeft(i -> a -> i + 1, 0);

F2<Integer, A, Integer> f = (i, a) -> i + 1;

return foldLeft(f, 0);

}

/**

* Returns <code>true</code> if this list is empty, <code>false</code> otherwise.

*

* @return <code>true</code> if this list is empty, <code>false</code> otherwise.

*/

public final boolean isEmpty() {

return this instanceof Nil;

}

/**

* Returns <code>false</code> if this list is empty, <code>true</code> otherwise.

*

* @return <code>false</code> if this list is empty, <code>true</code> otherwise.

*/

public final boolean isNotEmpty() {

return this instanceof Cons;

}

/**

* Performs a reduction on this list using the given arguments.

*

* @param nil The value to return if this list is empty.

* @param cons The function to apply to the head and tail of this list if it is not empty.

* @return A reduction on this list.

*/

public final <B> B list(final B nil, final F<A, F<List<A>, B>> cons) {

return isEmpty() ? nil : cons.f(head()).f(tail());

}

/**

* Returns the head of this list if there is one or the given argument if this list is empty.

*

* @param a The argument to return if this list is empty.

* @return The head of this list if there is one or the given argument if this list is empty.

*/

public final A orHead(final F0<A> a) {

return isEmpty() ? a.f() : head();

}

/**

* Returns the tail of this list if there is one or the given argument if this list is empty.

*

* @param as The argument to return if this list is empty.

* @return The tail of this list if there is one or the given argument if this list is empty.

*/

public final List<A> orTail(final F0<List<A>> as) {

return isEmpty() ? as.f() : tail();

}

/**

* Returns an option projection of this list; <code>None</code> if empty, or the first element in

* <code>Some</code>. Equivalent to {@link #headOption()}.

*

* @return An option projection of this list.

*/

public final Option<A> toOption() {

return isEmpty() ? Option.<A>none() : some(head());

}

/**

* Returns an either projection of this list; the given argument in <code>Left</code> if empty, or

* the first element in <code>Right</code>.

*

* @param x The value to return in left if this list is empty.

* @return An either projection of this list.

*/

public final <X> Either<X, A> toEither(final F0<X> x) {

return isEmpty() ? Either.<X, A>left(x.f()) : Either.<X, A>right(head());

}

/**

* Returns a stream projection of this list.

*

* @return A stream projection of this list.

*/

public final Stream<A> toStream() {

return isEmpty() ? Stream.nil() : Stream.cons(head(), () -> tail().toStream());

}

/**

* Returns a array projection of this list.

*

* @return A array projection of this list.

*/

@SuppressWarnings({"unchecked"})

public final Array<A> toArray() {

final int length = length();

final Object[] a = new Object[length];

List<A> x = this;

for (int i = 0; i < length; i++) {

a[i] = x.head();

x = x.tail();

}

return mkArray(a);

}

/**

* Returns a array projection of this list.

*

* @param c The class type of the array to return.

* @return A array projection of this list.

*/

@SuppressWarnings({"unchecked", "UnnecessaryFullyQualifiedName"})

public final Array<A> toArray(final Class<A[]> c) {

final A[] a = (A[]) java.lang.reflect.Array.newInstance(c.getComponentType(), length());

List<A> x = this;

for (int i = 0; i < length(); i++) {

a[i] = x.head();

x = x.tail();

}

return Array.array(a);

}

/**

* Returns an array from this list.

*

* @param c The class type of the array to return.

* @return An array from this list.

*/

public final A[] array(final Class<A[]> c) {

return toArray(c).array(c);

}

/**

* Prepends (cons) the given element to this list to product a new list.

*

* @param a The element to prepend.

* @return A new list with the given element at the head.

*/

public final List<A> cons(final A a) {

return new Cons<A>(a, this);

}

/**

* Prepends (cons) the given element to this list to product a new list. This method is added to prevent conflict with

* overloads.

*

* @param a The element to prepend.

* @return A new list with the given element at the head.

*/

public final List<A> conss(final A a) {

return new Cons<A>(a, this);

}

/**

* Maps the given function across this list.

*

* @param f The function to map across this list.

* @return A new list after the given function has been applied to each element.

*/

public final <B> List<B> map(final F<A, B> f) {

final Buffer<B> bs = empty();

for (List<A> xs = this; xs.isNotEmpty(); xs = xs.tail()) {

bs.snoc(f.f(xs.head()));

}

return bs.toList();

}

/**

* Performs a side-effect for each element of this list.

*

* @param f The side-effect to perform for the given element.

* @return The unit value.

*/

public final Unit foreach(final F<A, Unit> f) {

for (List<A> xs = this; xs.isNotEmpty(); xs = xs.tail()) {

f.f(xs.head());

}

return unit();

}

/**

* Performs a side-effect for each element of this list.

*

* @param f The side-effect to perform for the given element.

*/

public final void foreachDoEffect(final Effect1<A> f) {

for (List<A> xs = this; xs.isNotEmpty(); xs = xs.tail()) {

f.f(xs.head());

}

}

/**

* Filters elements from this list by returning only elements which produce <code>true</code> when

* the given function is applied to them.

*

* @param f The predicate function to filter on.

* @return A new list whose elements all match the given predicate.

*/

public final List<A> filter(final F<A, Boolean> f) {

final Buffer<A> b = empty();

for (List<A> xs = this; xs.isNotEmpty(); xs = xs.tail()) {

final A h = xs.head();

if (f.f(h)) {

b.snoc(h);

}

}

return b.toList();

}

/**

* Filters elements from this list by returning only elements which produce <code>false</code> when

* the given function is applied to them.

*

* @param f The predicate function to filter on.

* @return A new list whose elements do not match the given predicate.

*/

public final List<A> removeAll(final F<A, Boolean> f) {

return filter(compose(not, f));

}

/**

* Removes the first element that equals the given object.

* To remove all matches, use <code>removeAll(e.eq(a))</code>

*

* @param a The element to remove

* @param e An <code>Equals</code> instance for the element's type.

* @return A new list whose elements do not match the given predicate.

*/

public final List<A> delete(final A a, final Equal<A> e) {

final P2<List<A>, List<A>> p = span(compose(not, e.eq(a)));

return p._2().isEmpty() ? p._1() : p._1().append(p._2().tail());

}

/**

* Returns the first elements of the head of this list that match the given predicate function.

*

* @param f The predicate function to apply on this list until it finds an element that does not

* hold, or the list is exhausted.

* @return The first elements of the head of this list that match the given predicate function.

*/

public final List<A> takeWhile(final F<A, Boolean> f) {

final Buffer<A> b = empty();

boolean taking = true;

for (List<A> xs = this; xs.isNotEmpty() && taking; xs = xs.tail()) {

final A h = xs.head();

if (f.f(h)) {

b.snoc(h);

} else {

taking = false;

}

}

return b.toList();

}

/**

* Removes elements from the head of this list that do not match the given predicate function

* until an element is found that does match or the list is exhausted.

*

* @param f The predicate function to apply through this list.

* @return The list whose first element does not match the given predicate function.

*/

public final List<A> dropWhile(final F<A, Boolean> f) {

List<A> xs;

//noinspection StatementWithEmptyBody

for (xs = this; xs.isNotEmpty() && f.f(xs.head()); xs = xs.tail()) ;

return xs;

}

/**

* Returns a tuple where the first element is the longest prefix of this list that satisfies

* the given predicate and the second element is the remainder of the list.

*

* @param p A predicate to be satisfied by a prefix of this list.

* @return A tuple where the first element is the longest prefix of this list that satisfies

* the given predicate and the second element is the remainder of the list.

*/

public final P2<List<A>, List<A>> span(final F<A, Boolean> p) {

final Buffer<A> b = empty();

for (List<A> xs = this; xs.isNotEmpty(); xs = xs.tail()) {

if (p.f(xs.head()))

b.snoc(xs.head());

else

return P.p(b.toList(), xs);

}

return P.p(b.toList(), List.<A>nil());

}

/**

* Returns a tuple where the first element is the longest prefix of this list that does not satisfy

* the given predicate and the second element is the remainder of the list.

*

* @param p A predicate for an element to not satisfy by a prefix of this list.

* @return A tuple where the first element is the longest prefix of this list that does not satisfy

* the given predicate and the second element is the remainder of the list.

*/

public final P2<List<A>, List<A>> breakk(final F<A, Boolean> p) {

return span(a -> !p.f(a));

}

/**

* Groups elements according to the given equality implementation by longest

* sequence of equal elements.

*

* @param e The equality implementation for the elements.

* @return A list of grouped elements.

*/

public final List<List<A>> group(final Equal<A> e) {

if (isEmpty())

return nil();

else {

final P2<List<A>, List<A>> z = tail().span(e.eq(head()));

return cons(z._1().cons(head()), z._2().group(e));

}

}

/**

* Binds the given function across each element of this list with a final join.

*

* @param f The function to apply to each element of this list.

* @return A new list after performing the map, then final join.

*/

public final <B> List<B> bind(final F<A, List<B>> f) {

final Buffer<B> b = empty();

for (List<A> xs = this; xs.isNotEmpty(); xs = xs.tail()) {

b.append(f.f(xs.head()));

}

return b.toList();

}

/**

* Binds the given function across each element of this list and the given list with a final

* join.

*

* @param lb A given list to bind the given function with.

* @param f The function to apply to each element of this list and the given list.

* @return A new list after performing the map, then final join.

*/

public final <B, C> List<C> bind(final List<B> lb, final F<A, F<B, C>> f) {

return lb.apply(map(f));

}

/**

* Binds the given function across each element of this list and the given list with a final

* join.

*

* @param lb A given list to bind the given function with.

* @param f The function to apply to each element of this list and the given list.

* @return A new list after performing the map, then final join.

*/

public final <B, C> List<C> bind(final List<B> lb, final F2<A, B, C> f) {

return bind(lb, curry(f));

}

/**

* Promotes the given function of arity-2 to a function on lists.

*

* @param f The function to promote to a function on lists.

* @return The given function, promoted to operate on lists.

*/

public static <A, B, C> F<List<A>, F<List<B>, List<C>>> liftM2(final F<A, F<B, C>> f) {

return curry((as, bs) -> as.bind(bs, f));

}

/**

* Binds the given function across each element of this list and the given lists with a final

* join.

*

* @param lb A given list to bind the given function with.

* @param lc A given list to bind the given function with.

* @param f The function to apply to each element of this list and the given lists.

* @return A new list after performing the map, then final join.

*/

public final <B, C, D> List<D> bind(final List<B> lb, final List<C> lc, final F<A, F<B, F<C, D>>> f) {

return lc.apply(bind(lb, f));

}

/**

* Binds the given function across each element of this list and the given lists with a final

* join.

*

* @param lb A given list to bind the given function with.

* @param lc A given list to bind the given function with.

* @param ld A given list to bind the given function with.

* @param f The function to apply to each element of this list and the given lists.

* @return A new list after performing the map, then final join.

*/

public final <B, C, D, E> List<E> bind(final List<B> lb, final List<C> lc, final List<D> ld,

final F<A, F<B, F<C, F<D, E>>>> f) {

return ld.apply(bind(lb, lc, f));

}

/**

* Binds the given function across each element of this list and the given lists with a final

* join.

*

* @param lb A given list to bind the given function with.

* @param lc A given list to bind the given function with.

* @param ld A given list to bind the given function with.

* @param le A given list to bind the given function with.

* @param f The function to apply to each element of this list and the given lists.

* @return A new list after performing the map, then final join.

*/

public final <B, C, D, E, F$> List<F$> bind(final List<B> lb, final List<C> lc, final List<D> ld, final List<E> le,

final F<A, F<B, F<C, F<D, F<E, F$>>>>> f) {

return le.apply(bind(lb, lc, ld, f));

}

/**

* Binds the given function across each element of this list and the given lists with a final

* join.

*

* @param lb A given list to bind the given function with.

* @param lc A given list to bind the given function with.

* @param ld A given list to bind the given function with.

* @param le A given list to bind the given function with.

* @param lf A given list to bind the given function with.

* @param f The function to apply to each element of this list and the given lists.

* @return A new list after performing the map, then final join.

*/

public final <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,

final List<F$> lf, final F<A, F<B, F<C, F<D, F<E, F<F$, G>>>>>> f) {

return lf.apply(bind(lb, lc, ld, le, f));

}

/**

* Binds the given function across each element of this list and the given lists with a final

* join.

*

* @param lb A given list to bind the given function with.

* @param lc A given list to bind the given function with.

* @param ld A given list to bind the given function with.

* @param le A given list to bind the given function with.

* @param lf A given list to bind the given function with.

* @param lg A given list to bind the given function with.

* @param f The function to apply to each element of this list and the given lists.

* @return A new list after performing the map, then final join.

*/

public final <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,

final List<F$> lf, final List<G> lg,

final F<A, F<B, F<C, F<D, F<E, F<F$, F<G, H>>>>>>> f) {

return lg.apply(bind(lb, lc, ld, le, lf, f));

}

/**

* Binds the given function across each element of this list and the given lists with a final

* join.

*

* @param lb A given list to bind the given function with.

* @param lc A given list to bind the given function with.

* @param ld A given list to bind the given function with.

* @param le A given list to bind the given function with.

* @param lf A given list to bind the given function with.

* @param lg A given list to bind the given function with.

* @param lh A given list to bind the given function with.

* @param f The function to apply to each element of this list and the given lists.

* @return A new list after performing the map, then final join.

*/

public final <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,

final List<F$> lf, final List<G> lg, final List<H> lh,

final F<A, F<B, F<C, F<D, F<E, F<F$, F<G, F<H, I>>>>>>>> f) {

return lh.apply(bind(lb, lc, ld, le, lf, lg, f));

}

/**

* Performs a bind across each list element, but ignores the element value each time.

*

* @param bs The list to apply in the final join.

* @return A new list after the final join.

*/

public final <B> List<B> sequence(final List<B> bs) {

final F<A, List<B>> c = constant(bs);

return bind(c);

}

/**

* Traverses through the List with the given function

*

* @param f The function that produces Option value

* @return none if applying f returns none to any element of the list or f mapped list in some .

*/

public <B> Option<List<B>> traverseOption(final F<A, Option<B>> f) {

return foldRight(

(a, obs) -> f.f(a).bind(o -> obs.map(os -> os.cons(o))),

Option.some(List.<B>nil())

);

}

/**

* Traverse through the List with given function.

*

* @param f The function that produces Either value.

* @return error in left or f mapped list in right.

*/

public <B, E> Either<E, List<B>> traverseEither(final F<A, Either<E, B>> f) {

return foldRight(

(a, acc) -> f.f(a).right().bind(e -> acc.right().map(es -> es.cons(e))),

Either.<E, List<B>>right(List.<B>nil())

);

}

public <B> Stream<List<B>> traverseStream(final F<A, Stream<B>> f) {

return foldRight(

(a, acc) -> f.f(a).bind(s -> acc.map(ss -> ss.cons(s))),

Stream.<List<B>>nil()

);

}

public <B> P1<List<B>> traverseP1(final F<A, P1<B>> f){

return foldRight(

(a, acc) -> f.f(a).bind(b -> acc.map(bs -> bs.cons(b))),

P.p(List.<B>nil())

);

}

public <B> IO<List<B>> traverseIO(F<A, IO<B>> f) {

return this.foldRight(

(a, acc) -> IOFunctions.bind(acc, (bs) -> IOFunctions.map(f.f(a), b -> bs.cons(b))),

IOFunctions.unit(List.<B>nil())

);

}

public <C, B> F<C, List<B>> traverseF(F<A, F<C, B>> f) {

return this.foldRight(

(a, acc) -> Function.bind(acc,

(bs) -> Function.<C, B, List<B>> compose(b -> bs.cons(b), f.f(a))),

Function.constant(List.<B> nil())

);

}

public <B> Trampoline<List<B>> traverseTrampoline(final F<A, Trampoline<B>> f) {

return foldRight(

(a, acc) -> f.f(a).bind(b -> acc.map(bs -> bs.cons(b))),

Trampoline.pure(List.<B> nil()));

}

public <B> Promise<List<B>> traversePromise(final F<A, Promise<B>> f) {

return foldRight(

(a, acc) -> f.f(a).bind(b -> acc.fmap(bs -> bs.cons(b))),

Promise.promise(Strategy.idStrategy(), p(List.<B> nil())));

}

public <B> List<List<B>> traverseList(final F<A, List<B>> f) {

return foldRight(

(a, acc) -> f.f(a).bind(b -> acc.map(bs -> bs.cons(b))),

List.single(List.<B> nil()));

}

public <E, B> Validation<E, List<B>> traverseValidation(final F<A, Validation<E, B>> f) {

return foldRight(

(a, acc) -> f.f(a).bind(b -> acc.map(bs -> bs.cons(b))),

Validation.success(List.<B> nil()));

}

public <B> V2<List<B>> traverseV2(final F<A, V2<B>> f) {

return foldRight(

(a, acc) -> acc.apply(f.f(a).<F<List<B>, List<B>>> map(e -> es -> es.cons(e))),

v(List.<B> nil(), List.<B> nil()));

}

/**

* Performs function application within a list (applicative functor pattern).

*

* @param lf The list of functions to apply.

* @return A new list after applying the given list of functions through this list.

*/

public final <B> List<B> apply(final List<F<A, B>> lf) {

return lf.bind(f -> map(f));

}

/**

* Appends the given list to this list.

*

* @param as The list to append to this one.

* @return A new list that has appended the given list.

*/

public final List<A> append(final List<A> as) {

return Buffer.fromList(this).prependToList(as);

}

/**

* Performs a right-fold reduction across this list.

*

* @param f The function to apply on each element of the list.

* @param b The beginning value to start the application from.

* @return The final result after the right-fold reduction.

*/

public final <B> B foldRight(final F<A, F<B, B>> f, final B b) {

return reverse().foldLeft(flip(f), b);

}

/**

* Performs a right-fold reduction across this list. This function uses O(length) stack space.

*

* @param f The function to apply on each element of the list.

* @param b The beginning value to start the application from.

* @return The final result after the right-fold reduction.

*/

public final <B> B foldRight(final F2<A, B, B> f, final B b) {

return foldRight(curry(f), b);

}

/**

* Performs a right-fold reduction across this list in O(1) stack space.

* @param f The function to apply on each element of the list.

* @param b The beginning value to start the application from.

* @return A Trampoline containing the final result after the right-fold reduction.

*/

public final <B> Trampoline<B> foldRightC(final F2<A, B, B> f, final B b) {

return Trampoline.suspend(P.lazy(() -> isEmpty() ? Trampoline.pure(b) : tail().foldRightC(f, b).map(F2Functions.f(f, head()))));

}

/**

* Performs a left-fold reduction across this list. This function runs in constant space.

*

* @param f The function to apply on each element of the list.

* @param b The beginning value to start the application from.

* @return The final result after the left-fold reduction.

*/

public final <B> B foldLeft(final F<B, F<A, B>> f, final B b) {

B x = b;

for (List<A> xs = this; !xs.isEmpty(); xs = xs.tail()) {

x = f.f(x).f(xs.head());

}

return x;

}

/**

* Performs a left-fold reduction across this list. This function runs in constant space.

*

* @param f The function to apply on each element of the list.

* @param b The beginning value to start the application from.

* @return The final result after the left-fold reduction.

*/

public final <B> B foldLeft(final F2<B, A, B> f, final B b) {

return foldLeft(curry(f), b);

}

/**

* Takes the first 2 elements of the list and applies the function to them,

* then applies the function to the result and the third element and so on.

*

* @param f The function to apply on each element of the list.

* @return The final result after the left-fold reduction.

*/

public final A foldLeft1(final F2<A, A, A> f) {

return foldLeft1(curry(f));

}

/**

* Takes the first 2 elements of the list and applies the function to them,

* then applies the function to the result and the third element and so on.

*

* @param f The function to apply on each element of the list.

* @return The final result after the left-fold reduction.

*/

public final A foldLeft1(final F<A, F<A, A>> f) {

if (isEmpty())

throw error("Undefined: foldLeft1 on empty list");

return tail().foldLeft(f, head());

}

/**

* Reverse this list in constant stack space.

*

* @return A new list that is the reverse of this one.

*/

public final List<A> reverse() {

return foldLeft(as -> a -> cons(a, as), List.<A>nil());

}

/**

* Returns the element at the given index if it exists, fails otherwise.

*

* @param i The index at which to get the element to return.

* @return The element at the given index if it exists, fails otherwise.

*/

public final A index(final int i) {

if (i < 0 || i > length() - 1)

throw error("index " + i + " out of range on list with length " + length());

else {

List<A> xs = this;

for (int c = 0; c < i; c++) {

xs = xs.tail();

}

return xs.head();

}

}

/**

* Takes the given number of elements from the head of this list if they are available.

*

* @param i The maximum number of elements to take from this list.

* @return A new list with a length the same, or less than, this list.

*/

public final List<A> take(final int i) {

return i <= 0 || isEmpty() ? List.<A>nil() : cons(head(), tail().take(i - 1));

}

/**

* Drops the given number of elements from the head of this list if they are available.

*

* @param i The number of elements to drop from the head of this list.

* @return A list with a length the same, or less than, this list.

*/

public final List<A> drop(final int i) {

int c = 0;

List<A> xs = this;

for (; xs.isNotEmpty() && c < i; xs = xs.tail())

c++;

return xs;

}

/**

* Splits this list into two lists at the given index. If the index goes out of bounds, then it is

* normalised so that this function never fails.

*

* @param i The index at which to split this list in two parts.

* @return A pair of lists split at the given index of this list.

*/

public final P2<List<A>, List<A>> splitAt(final int i) {

P2<List<A>, List<A>> s = p(List.<A>nil(), List.<A>nil());

int c = 0;

for (List<A> xs = this; xs.isNotEmpty(); xs = xs.tail()) {

final A h = xs.head();

s = c < i ? s.map1(as -> as.snoc(h)) : s.map2(as1 -> as1.snoc(h));

c++;

}

return s;

}

/**

* Splits this list into lists of the given size. If the size of this list is not evenly divisible by

* the given number, the last partition will contain the remainder.

*

* @param n The size of the partitions into which to split this list.

* @return A list of sublists of this list, of at most the given size.

*/

public final List<List<A>> partition(final int n) {

if (n < 1)

throw error("Can't create list partitions shorter than 1 element long.");

if (isEmpty())

throw error("Partition on empty list.");

return unfold(as -> as.isEmpty() ? Option.<P2<List<A>, List<A>>>none() : some(as.splitAt(n)), this);

}

/**

* Partitions the list into a tuple where the first element contains the

* items that satisfy the the predicate f and the second element contains the

* items that does not. The relative order of the elements in the returned tuple

* is the same as the original list.

*

* @param f Predicate function.

*/

public P2<List<A>, List<A>> partition(F<A, Boolean> f) {

P2<List<A>, List<A>> p2 = foldLeft(acc -> a ->

f.f(a) ? P.p(acc._1().cons(a), acc._2()) : P.p(acc._1(), acc._2().cons(a)),

P.p(nil(), nil())

);

return P.p(p2._1().reverse(), p2._2().reverse());

}

/**

* Returns the list of initial segments of this list, shortest first.

*

* @return The list of initial segments of this list, shortest first.

*/

public final List<List<A>> inits() {

List<List<A>> s = single(List.<A>nil());

if (isNotEmpty())

s = s.append(tail().inits().map(List.<A>cons().f(head())));

return s;

}

/**

* Returns the list of final segments of this list, longest first.

*

* @return The list of final segments of this list, longest first.

*/

public final List<List<A>> tails() {

return isEmpty() ? single(List.<A>nil()) : cons(this, tail().tails());

}

/**

* Sorts this list using the given order over elements using a <em>merge sort</em> algorithm.

*

* @param o The order over the elements of this list.

* @return A sorted list according to the given order.

*/

public final List<A> sort(final Ord<A> o) {

if (isEmpty())

return nil();

else if (tail().isEmpty())

return this;

else {

final class Merge<A> {

List<A> merge(List<A> xs, List<A> ys, final Ord<A> o) {

final Buffer<A> buf = empty();

while (true) {

if (xs.isEmpty()) {

buf.append(ys);

break;

}

if (ys.isEmpty()) {

buf.append(xs);

break;

}

final A x = xs.head();

final A y = ys.head();

if (o.isLessThan(x, y)) {

buf.snoc(x);

xs = xs.tail();

} else {

buf.snoc(y);

ys = ys.tail();

}

}

return buf.toList();

}

}

final P2<List<A>, List<A>> s = splitAt(length() / 2);

return new Merge<A>().merge(s._1().sort(o), s._2().sort(o), o);

}

}

/**

* Zips this list with the given list using the given function to produce a new list. If this list

* and the given list have different lengths, then the longer list is normalised so this function

* never fails.

*

* @param bs The list to zip this list with.

* @param f The function to zip this list and the given list with.

* @return A new list with a length the same as the shortest of this list and the given list.

*/

public final <B, C> List<C> zipWith(List<B> bs, final F<A, F<B, C>> f) {

final Buffer<C> buf = empty();

List<A> as = this;

while (as.isNotEmpty() && bs.isNotEmpty()) {

buf.snoc(f.f(as.head()).f(bs.head()));

as = as.tail();

bs = bs.tail();

}

return buf.toList();

}

/**

* Zips this list with the given list using the given function to produce a new list. If this list

* and the given list have different lengths, then the longer list is normalised so this function

* never fails.

*

* @param bs The list to zip this list with.

* @param f The function to zip this list and the given list with.

* @return A new list with a length the same as the shortest of this list and the given list.

*/

public final <B, C> List<C> zipWith(final List<B> bs, final F2<A, B, C> f) {

return zipWith(bs, curry(f));

}

/**

* Provides a first-class version of zipWith

*

* @return The first-class version of zipWith

*/

public static <A, B, C> F<List<A>, F<List<B>, F<F<A, F<B, C>>, List<C>>>> zipWith() {

return curry((as, bs, f) -> as.zipWith(bs, f));

}

/**

* Zips this list with the given list to produce a list of pairs. If this list and the given list

* have different lengths, then the longer list is normalised so this function never fails.

*

* @param bs The list to zip this list with.

* @return A new list with a length the same as the shortest of this list and the given list.

*/

public final <B> List<P2<A, B>> zip(final List<B> bs) {

final F<A, F<B, P2<A, B>>> __2 = p2();

return zipWith(bs, __2);

}

/**

* The first-class version of the zip function.

*

* @return A function that zips the given lists to produce a list of pairs.

*/

public static <A, B> F<List<A>, F<List<B>, List<P2<A, B>>>> zip() {

return curry((as, bs) -> as.zip(bs));