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 }