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    }