Lazy lists?

[Paul Sandoz]

Hi Milles,

We avoided adding operation-based methods to collections themselves which would have made them lazy due to, in part, the complexity that it introduced to the implementation. So rather than a lazy data structure we opted for different abstraction we call Stream.

The approach of the specific example you present is falling into similar traps as discussed in [1] on trial division, and as such it is, IMHO, not a particular compelling reasons why lazy lists are needed.

Note: we are missing some operations on stream, such as limitWhen (or takeWhile) that would be useful for the trial division use-case.

Here is another way:

        Map<Integer, LinkedList<Integer>> m = new TreeMap<>();
        Function<Integer, LinkedList<Integer>> newList = (k) -> new LinkedList();
        IntStream.range(2, 100).forEach(x -> {
            if (!m.containsKey(x)) {
                // Always absent, just shorter expression
                m.computeIfAbsent(x * x, newList).push(x);
            }
            else {
                m.remove(x).forEach(p -> m.computeIfAbsent(x + p, newList).push(p));
            }
        });
        List<Integer> primes = m.values().stream().flatMap(List::stream).collect(toList());
        System.out.println(primes);

Obviously that is not parallelizable and of course it is not lazy, but then Java is not Haskell (for better or worse depending on one's opinion).

I think there are far more compelling reasons to add persistent collections to Java.

Paul.

[1] http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf


On Oct 9, 2013, at 9:00 AM, "Millies, Sebastian" <Sebastian.Millies at softwareag.com> wrote:

> Hello there,
> 
> now that we have infinite Streams, wouldn’t it be worthwhile to have a lazy list
> implementation in the collection library? By Lazy list, I mean a list that
> would be strict for the head and lazy for the tail in that it
> 
> a) could be based on a Function<T> to generate the elements in the tail
>   in sequence (like Stream#iterate())
> b) would accept a Supplier<LazyList<T>> to supply a tail (like Stream#generate())
> c) would accept a Predicate<T> to filter out non-matching elements
>   from the tail
> d) would allow constant time access to the head.
> 
> It would stream() using a spliterator of unknown size.
> 
> With it, we could write code somewhat like this to generate the first 100 primes
> by trial division (where cons is also a static factory methof of LazyList):
> 
> LazyList<Integer> s = sieve(LazyList.newList(2, x -> x + 1));
> s.stream().limit(100).forEach(x->System.out.print(x + " "));
> 
> private LazyList <Integer> sieve(LazyList <Integer> s) {
>  Integer p = s.head();
>  return cons(p, () -> sieve(s.tail().filter(x -> x % p != 0)));
> }
> 
> Which would be pretty neat. Any particular reason – now that we have
> lambdas – that there are no lazy data structures in the library?
> 
> 
> n  Sebastian
> 
> Software AG – Sitz/Registered office: Uhlandstraße 12, 64297 Darmstadt, Germany – Registergericht/Commercial register: Darmstadt HRB 1562 - Vorstand/Management Board: Karl-Heinz Streibich (Vorsitzender/Chairman), Dr. Wolfram Jost, Arnd Zinnhardt; - Aufsichtsratsvorsitzender/Chairman of the Supervisory Board: Dr. Andreas Bereczky - http://www.softwareag.com
> 
>