Lazy lists?

[Millies, Sebastian]

Hello Paul,

thanks for that example (although it computes the primes in the range up to 100, not the first 100 primes).
First time I see flatMap in action.

My code was intended only as an example, I am aware of O'Neills paper. I still think having lazy collections
would be nice. Your last sentence suggests you view them as an alternative to persistent collections. Or is
that an over-interpretation?

-- Sebastian


-----Original Message-----
From: lambda-dev-bounces at openjdk.java.net [mailto:lambda-dev-bounces at openjdk.java.net] On Behalf Of Paul Sandoz
Sent: Wednesday, October 09, 2013 12:22 PM
Cc: lambda-dev at openjdk.java.net
Subject: Re: Lazy lists?

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
>
>


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