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