1
\$\begingroup\$

In order to understand how the lazy sequences work in Clojure, I decided to implement the quick-sort example from the "The Joy of Clojure, Second Edition" book simulating lazy sequences in Java. Of course my version of (lazy) sequence is much more simplified than the Clojure one.

From the linked source, I basically implemented sort-parts function as QuickSortProducer and lazy-seq as LazySequence class. NextValueProducer is a rudimentary representation of the functions passed to lazy-seq to produce the next value.

The main question of this review is, whether my Java program grasps the analogy correctly, i.e. if my code represents what is going on in with a Clojure lazy-seq. Besides that, I would be interested whether the implementation could be made "nicer" in some way (I especially do not like the while(true) loop in the body of QuickSortProducer.getNextValue, but I could not think of any better. Also, I wonder if the field work could be anything better than List<Object>, given that it has to store Integers and Lists of Integers at the same time. Last but not least, any further suggestions for unit tests would be welcome. (Of course, any other remark or suggestion is also very much appreciated.)

One last remark: I have only very basic knowledge of the new Java 8 functional constructs, that's why I did not use them in this example (also I am not sure if they would apply at all). Any suggestion taking advantage of Java 8 is still very much welcome, though.

NextValueProducer.java:

public interface NextValueProducer {
    Object getNextValue();
}

LazySequence.java:

import java.util.ArrayList;
import java.util.List;

public class LazySequence {
    private NextValueProducer nvp;
    private List cache;

    public LazySequence(NextValueProducer nvp) {
        this.nvp = nvp;
        cache = new ArrayList<>();
    }

    public Object getNthElement(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("n has to be positive");
        }
        for (int i = cache.size(); i <= n; ++i) {
            Object produced = nvp.getNextValue();
            if (produced == null) {
                break;
            }
            else {
                cache.add(produced);
            }
        }
        if (cache.size() > n) {
            return cache.get(n);
        }
        else {
            return null;
        }
    }
}

QuickSortProducer.java:

import java.util.ArrayList;
import java.util.List;

public class QuickSortProducer implements NextValueProducer {

    private List<Object> work;

    public QuickSortProducer(List<Integer> nums) {
        work = new ArrayList<>();
        List<Integer> temp = new ArrayList<>(nums);
        work.add(temp);
    }

    @Override
    public Object getNextValue() {

        List workCopy = new ArrayList<>(work);

        while (true) {

            List part = new ArrayList<>((List)workCopy.get(0));
            List parts = new ArrayList<>(workCopy.subList(1, workCopy.size()));

            if (part.size() > 0) {
                int pivot = (int)part.get(0);
                List xs = part.subList(1, part.size());

                List<Integer> smallers = new ArrayList<>();
                List<Integer> biggers = new ArrayList<>();

                for (Object xObj : xs) {
                    int x = (int)xObj;
                    if (x < pivot) {
                        smallers.add(x);
                    }
                    else if (x > pivot) {
                        biggers.add(x);
                    }
                }

                workCopy = new ArrayList<>();
                workCopy.add(smallers);
                workCopy.add(pivot);
                workCopy.add(biggers);
                workCopy.addAll(parts);
            }
            else {
                if (parts.size() > 0) {
                    work = new ArrayList<>(parts.subList(1, parts.size()));
                    return parts.get(0);
                }
                else {
                    return null;
                }
            }
        }       
    }
}

QuickSortProducerTest.java:

import static org.junit.Assert.*;

import java.util.ArrayList;
import java.util.List;

import org.junit.Test;

public class QuickSortProducerTest {

    @Test
    public void testQuickSortEmptyList() {
        List<Integer> numsToSort = new ArrayList<>();
        LazySequence seq = new LazySequence(new QuickSortProducer(numsToSort));

        Object elem = seq.getNthElement(0);

        assertNull(elem);
    }

    @Test
    public void testQuickSortOneElementList() {
        List<Integer> numsToSort = new ArrayList<>();
        numsToSort.add(2);

        LazySequence seq = new LazySequence(new QuickSortProducer(numsToSort));

        assertEquals(2, seq.getNthElement(0));
        assertEquals(null, seq.getNthElement(1));
    }

    @Test
    public void testQuickSortUnsortedList() {
        List<Integer> numsToSort = new ArrayList<>();
        numsToSort.add(2);
        numsToSort.add(1);
        numsToSort.add(4);
        numsToSort.add(3);

        LazySequence seq = new LazySequence(new QuickSortProducer(numsToSort));

        assertEquals(1, seq.getNthElement(0));
        assertEquals(2, seq.getNthElement(1));
        assertEquals(3, seq.getNthElement(2));
        assertEquals(4, seq.getNthElement(3));
        assertEquals(null, seq.getNthElement(4));
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.