201611 SICP系列 第7讲 流计算模型 学习笔记 (Java&Python版) - xiaoxianfaye/Learning GitHub Wiki

0 Outline

用Java语言写了如下程序：

  1. 用Cesaro方法估算PI值：pi.PiEstimator。
  2. sumOddsSquare & oddFibs：
    • 未用Stream实现：nostream.Procedures
    • 用Java 8 Stream实现：java8stream.Procedures
    • 用自定义Stream(List)实现：liststream.Procedures
    • 用自定义Stream(Delay)实现：delaystream.Procedures
  3. primeSumPairs：
    • 未用Stream实现：nostream.Procedures
    • 用Java 8 Stream实现：java8stream.Procedures
    • 用自定义Stream(List)实现：liststream.Procedures
    • 用自定义Stream(Delay)实现：delaystream.Procedures
  4. triples:
    • 未用Stream实现：nostream.Procedures
    • 用Java 8 Stream实现：java8stream.Procedures
    • 用自定义Stream(List)实现：liststream.Procedures
    • 用自定义Stream(Delay)实现：delaystream.Procedures
  5. Eight Queens Problem：
    • Backtracking Search (未用Stream)
      • 求出一个解：nostream.Queens.btQueensForOneSolution()
      • 求出所有解：nostream.Queens.btQueensForAllSolutions()
    • Recursive Strategy
      • 用Java 8 Stream实现：java8stream.ReQueens
      • 用自定义Stream(List)实现：liststream.ReQueens
      • 用自定义Stream(Delay)实现：delaystream.ReQueens
  6. Second Prime：用自定义Stream(Delay)实现，delaystream.Procedures
  7. No Sevens & Sieve of Eratosthenes：用自定义Stream(Delay)实现，delaystream.Procedures
  8. Defining Streams Implicitly：用自定义Stream(Delay)实现，delaystream.StreamOp
  9. Integrator：用自定义Stream(Delay)实现，delaystream.Procedures
    • 生成式定义
    • 隐式定义
    • Delay Integrator
  10. Sqrt：用自定义Stream(Delay)实现，delaystream.Procedures
  11. Stream of Pairs：用自定义Stream(Delay)实现，delaystream.Procedures
    • Stream of pairs constructed from an infinite stream
    • Stream of pairs constructed from two infinite streams
    • All the pairs：non-recursive & recursive
    • Up pairs: recursive
  12. 用Cesaro方法估算PI值：用自定义Stream(Delay)实现，pi.PiEstimatorWithDelayStream
  13. 用Stream Class替换List表示流

用Python语言写了上述所有程序，除了Stream Class。因为Python是弱类型的，所以List和Stream Class区别不大。

  1. Python版本

1 用Cesaro方法估算PI值

pi.PiEstimator

import java.util.function.BooleanSupplier;
import java.util.stream.DoubleStream;
import java.util.stream.IntStream;

public class PiEstimator
{
    private static final int MAX_RANDOM_NUMER = 100000;
    
    public static double estimate(int count)
    {
        return Math.sqrt(6 / monteCarlo(count, cesaro()));
    }

    private static double monteCarlo(int count, BooleanSupplier func)
    {
        long trueCount = IntStream.range(1, count + 1)
                                  .mapToObj(c -> func.getAsBoolean())
                                  .filter(b -> b)
                                  .count();
        return 1.0 * trueCount / count;
    }

    private static BooleanSupplier cesaro()
    {
        return () -> {
            return gcd(randomNumber(), randomNumber()) == 1;
        };
    }

    private static int randomNumber()
    {
        return (int)(Math.random() * MAX_RANDOM_NUMER) + 1;
    }
    
    private static int gcd(int x, int y)
    {
        if(y == 0)
        {
            return x;
        }
        
        return gcd(y, x % y);
    }
    
    private static DoubleStream estimate(int...counts)
    {
        return IntStream.of(counts).mapToDouble(count -> estimate(count));
    }
    
    public static void main(String[] args)
    {
        DoubleStream pis = PiEstimator.estimate(1000, 10000, 100000, 1000000, 10000000);
        pis.forEach((pi) -> System.out.println(pi));
    }
}

2 sumOddsSquare & oddFibs

2.1 未用Stream实现

nostream.ProceduresTest

import static fayelab.sicp.stream.nostream.Procedures.*;
import static java.util.Arrays.asList;

import junit.framework.TestCase;

public class ProceduresTest extends TestCase
{
    public void test_sumOddsSquare()
    {
        BiTuple<?, ?> biTree = biTuple(biTuple(1, biTuple(2, 7)), biTuple(19, biTuple(12, 14)));
        assertEquals(411, sumOddsSquare(biTree));
    }
    
    public void test_oddFibs()
    {
        assertEquals(asList(1, 2, 4, 5), oddFibs(6));
    }
}

nostream.Procedures

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

public class Procedures
{
    public static int sumOddsSquare(Object obj)
    {
        if(obj instanceof BiTuple<?, ?>)
        {
            return sumOddsSquareForBiTuple((BiTuple<?, ?>)obj);
        }
        
        return sumOddsSquareForInteger((Integer)obj);
    }

    private static int sumOddsSquareForBiTuple(BiTuple<?, ?> biTuple)
    {
        return sumOddsSquare(biTuple.getElement1()) + sumOddsSquare(biTuple.getElement2());
    }

    private static int sumOddsSquareForInteger(Integer integer)
    {
        int n = integer.intValue();
        
        if(isOdd(n))
        {
            return square(n);
        }
        
        return 0;
    }
    
    public static List<Integer> oddFibs(int n)
    {
        List<Integer> result = new ArrayList<>();
        
        for(int i = 0; i <= n; i++)
        {
            if(isOdd(fib(i)))
            {
                result.add(i);
            }
        }
        
        return result;
    }

    private static boolean isOdd(int n)
    {
        return n % 2 == 1;
    }
    
    private static int square(int n)
    {
        return n * n;
    }
    
    private static int fib(int n)
    {
        int a = 0;
        int b = 1;
        int s = 0;
        
        if(n == 0)
        {
            return a;
        }
        
        if(n == 1)
        {
            return b;
        }
        
        for(int i = 0; i <= n - 2; i++)
        {
            s = a + b;
            a = b;
            b = s;
        }
        
        return s;
    }

    public static <T1, T2> BiTuple<T1, T2> biTuple(T1 element1, T2 element2)
    {
        return new BiTuple<>(element1, element2);
    }
    
    static class BiTuple<T1, T2>
    {
        private T1 element1;
        private T2 element2;
        
        public BiTuple(T1 element1, T2 element2)
        {
            this.element1 = element1;
            this.element2 = element2;
        }
    
        public T1 getElement1()
        {
            return element1;
        }
    
        public T2 getElement2()
        {
            return element2;
        }
    }
}

2.2 用Java 8 Stream实现

java8stream.ProceduresTest

import static fayelab.sicp.stream.java8stream.Procedures.*;
import static java.util.Arrays.asList;
import static java.util.stream.Collectors.toList;

import junit.framework.TestCase;

public class ProceduresTest extends TestCase
{
    public void test_enumTree()
    {
        assertEquals(asList(1, 2, 7, 19, 12, 14), 
                     enumTree(biTuple(biTuple(1, biTuple(2, 7)), 
                                      biTuple(19, biTuple(12, 14))))
                     .collect(toList()));
        
        assertEquals(asList(1, 2, 3, 7, 19, 12, 13, 14), 
                     enumTree(biTuple(biTuple(1, biTuple(biTuple(2, 3), 7)), 
                                      biTuple(19, biTuple(12, biTuple(13, 14)))))
                     .collect(toList()));
    }
    
    public void test_enumInterval()
    {
        assertEquals(asList(2, 3, 4, 5), enumInterval(2, 5).collect(toList()));
        assertEquals(asList(), enumInterval(3, 1).collect(toList()));
    }
    
    public void test_sumOddsSquare()
    {
        BiTuple<?, ?> biTree = biTuple(biTuple(1, biTuple(2, 7)), biTuple(19, biTuple(12, 14)));
        assertEquals(411, sumOddsSquare(biTree));
    }
    
    public void test_oddFibs()
    {
        assertEquals(asList(1, 2, 4, 5), oddFibs(6));
    }
}

java8stream.Procedures

import java.util.ArrayList;
import java.util.List;
import java.util.stream.IntStream;
import java.util.stream.Stream;

import static java.util.Arrays.asList;

public class Procedures
{
    @SuppressWarnings("unchecked")
    static <T> Stream<T> enumTree(Object obj)
    {
        if(obj instanceof BiTuple)
        {
            BiTuple<?, ?> biTuple = (BiTuple<?, ?>)obj;
            return Stream.concat(enumTree(biTuple.getElement1()), enumTree(biTuple.getElement2()));
        }
        
        return Stream.of((T)obj);
    }

    static Stream<Integer> enumInterval(int low, int high)
    {
        return IntStream.rangeClosed(low, high).boxed();
    }
    
    public static int sumOddsSquare(BiTuple<?, ?> biTree)
    {
        Stream<Integer> s = enumTree(biTree);
        return s.filter(x -> isOdd(x))
                .map(x -> square(x))
                .reduce((x, y) -> x + y)
                .get();
    }
    
    public static List<Integer> oddFibs(int n)
    {
        List<Integer> result = new ArrayList<>();
        
        enumInterval(0, n).filter(idx -> isOdd(fib(idx)))
                          .collect(() -> result,
                                   (acc, idx) -> acc.add(idx),
                                   (acc1, acc2) -> acc1.addAll(acc2));

        return result;
    }
    
    private static boolean isOdd(int n)
    {
        return n % 2 == 1;
    }
    
    private static int square(int n)
    {
        return n * n;
    }
    
    private static int fib(int n)
    {
        int a = 0;
        int b = 1;
        int s = 0;
        
        if(n == 0)
        {
            return a;
        }
        
        if(n == 1)
        {
            return b;
        }
        
        for(int i = 0; i <= n - 2; i++)
        {
            s = a + b;
            a = b;
            b = s;
        }
        
        return s;
    }

    public static <T1, T2> BiTuple<T1, T2> biTuple(T1 element1, T2 element2)
    {
        return new BiTuple<>(element1, element2);
    }

    static class BiTuple<T1, T2>
    {
        private T1 element1;
        private T2 element2;
        
        public BiTuple(T1 element1, T2 element2)
        {
            this.element1 = element1;
            this.element2 = element2;
        }
    
        public T1 getElement1()
        {
            return element1;
        }
    
        public T2 getElement2()
        {
            return element2;
        }
    }
}

2.3 用自定义Stream(List)实现

liststream.StreamOpTest

import junit.framework.TestCase;

import static fayelab.sicp.stream.liststream.StreamOp.*;
import static java.util.Arrays.asList;

public class StreamOpTest extends TestCase
{
    public void test_consStream()
    {
        assertEquals(asList(1, 2, 3), consStream(1, asList(2, 3)));
        assertEquals(asList(1), consStream(1, asList()));
    }
    
    public void test_theEmptyStream()
    {
        assertEquals(asList(), theEmptyStream());
    }
    
    public void test_head()
    {
        assertEquals(new Integer(1), head(asList(1, 2, 3)));
    }
    
    public void test_tail()
    {
        assertEquals(asList(2, 3), tail(asList(1, 2, 3)));
    }
    
    public void test_isEmptyStream()
    {
        assertTrue(isEmptyStream(asList()));
    }
    
    public void test_mapStream()
    {
        assertEquals(asList(2, 4), mapStream(x -> 2 * x, asList(1, 2)));
        assertEquals(asList("1", "2"), mapStream(x -> String.valueOf(x), asList(1, 2)));
        assertEquals(asList(), mapStream(x -> x, asList()));
    }
    
    public void test_filterStream()
    {
        assertEquals(asList(2, 4), filterStream(x -> x % 2 == 0, asList(1, 2, 3, 4)));
        assertEquals(asList(), filterStream(x -> true, asList()));
    }
    
    public void test_accStream()
    {
        assertEquals(new Integer(10), accStream((x, y) -> x + y, 0, asList(1, 2, 3, 4)));
        assertEquals("123", accStream((x, y) -> String.join("", String.valueOf(x), String.valueOf(y)), "", asList(1, 2, 3)));
        assertEquals(new Integer(0), accStream((Integer x, Integer y) -> x + y, 0, asList()));
        assertEquals(new Integer(1), accStream((x, y) -> x + y, 0, asList(1)));
    }
    
    public void test_appendStream()
    {
        assertEquals(asList(1, 2, 3, 4), appendStream(asList(1, 2), asList(3, 4)));
        assertEquals(asList(3, 4), appendStream(asList(), asList(3, 4)));
        assertEquals(asList(1, 2), appendStream(asList(1, 2), asList()));
        assertEquals(asList(), appendStream(asList(), asList()));
    }
    
    public void test_enumTree()
    {
        assertEquals(asList(1, 2, 7, 19, 12, 14), 
                     enumTree(biTuple(biTuple(1, biTuple(2, 7)), 
                              biTuple(19, biTuple(12, 14)))));
        
        assertEquals(asList(1, 2, 3, 7, 19, 12, 13, 14), 
                     enumTree(biTuple(biTuple(1, biTuple(biTuple(2, 3), 7)), 
                              biTuple(19, biTuple(12, biTuple(13, 14))))));
    }
    
    public void test_enumInterval()
    {
        assertEquals(asList(1, 2, 3, 4), enumInterval(1, 4));
        assertEquals(asList(), enumInterval(3, 1));
    }
    
    public void test_flatten()
    {
        assertEquals(asList(1, 2, 3, 4, 5), flatten(asList(asList(1, 2), asList(3, 4), asList(5))));
        assertEquals(asList(1, 2), flatten(asList(asList(1, 2))));
        assertEquals(asList(), flatten(asList()));
    }
    
    public void test_flatmap()
    {
        assertEquals(asList(1, 2, 3, 2, 4, 6), flatmap(x -> asList(x, x * 2, x * 3), asList(1, 2)));
        assertEquals(asList(), flatmap(x -> asList(x), asList()));
    }
}

liststream.StreamOp

import java.util.ArrayList;
import java.util.List;
import java.util.function.BiFunction;
import java.util.function.Function;
import java.util.function.Predicate;

import static java.util.Arrays.asList;

public class StreamOp
{
    //Constructors
    public static <T> List<T> consStream(T head, List<T> tail)
    {
        List<T> result = new ArrayList<>();
        result.add(head);
        result.addAll(tail);
        return result;
    }
    
    public static <T> List<T> theEmptyStream()
    {
        return asList();
    }
    
    //Selectors
    public static <T> T head(List<T> s)
    {
        return s.get(0);
    }
    
    public static <T> List<T> tail(List<T> s)
    {
        return s.subList(1, s.size());
    }
    
    public static <T> boolean isEmptyStream(List<T> s)
    {
        return s.isEmpty();
    }
    
    //Stream Operations
    public static <T, R> List<R> mapStream(Function<T, R> proc, List<T> s)
    {
        if(isEmptyStream(s))
        {
            return theEmptyStream();
        }
        
        return consStream(proc.apply(head(s)), mapStream(proc, tail(s)));
    }
    
    public static <T> List<T> filterStream(Predicate<T> pred, List<T> s)
    {
        if(isEmptyStream(s))
        {
            return theEmptyStream();
        }
        
        if(pred.test(head(s)))
        {
            return consStream(head(s), filterStream(pred, tail(s)));
        }
        
        return filterStream(pred, tail(s));
    }
    
    public static <T, R> R accStream(BiFunction<T, R, R> proc, R acc, List<T> s)
    {
        if(isEmptyStream(s))
        {
            return acc;
        }
        
        return proc.apply(head(s), accStream(proc, acc, tail(s)));
    }
    
    public static <T> List<T> appendStream(List<T> s1, List<T> s2)
    {
        if(isEmptyStream(s1))
        {
            return s2;
        }
        
        return consStream(head(s1), appendStream(tail(s1), s2));
    }
    
    @SuppressWarnings("unchecked")
    public static <T> List<T> enumTree(Object obj)
    {
        if(obj instanceof BiTuple)
        {
            BiTuple<?, ?> biTuple = (BiTuple<?, ?>)obj;
            return appendStream(enumTree(biTuple.getElement1()), enumTree(biTuple.getElement2()));
        }
        
        return consStream((T)obj, theEmptyStream());
    }
    
    public static List<Integer> enumInterval(int low, int high)
    {
        if(low > high)
        {
            return theEmptyStream();
        }
        
        return consStream(low, enumInterval(low + 1, high));
    }
    
    public static <T> List<T> flatten(List<List<T>> sos)
    {
        return accStream((s1, s2) -> appendStream(s1, s2), theEmptyStream(), sos);
    }
    
    public static <T, R> List<R> flatmap(Function<T, List<R>> proc, List<T> s)
    {
        return flatten(mapStream(proc, s));
    }
    
    public static <T1, T2> BiTuple<T1, T2> biTuple(T1 element1, T2 element2)
    {
        return new BiTuple<>(element1, element2);
    }

    static class BiTuple<T1, T2>
    {
        private T1 element1;
        private T2 element2;
        
        public BiTuple(T1 element1, T2 element2)
        {
            this.element1 = element1;
            this.element2 = element2;
        }
    
        public T1 getElement1()
        {
            return element1;
        }
    
        public T2 getElement2()
        {
            return element2;
        }
    }
}

liststream.ProceduresTest

import junit.framework.TestCase;

import static fayelab.sicp.stream.liststream.Procedures.*;
import static fayelab.sicp.stream.liststream.StreamOp.*;
import static java.util.Arrays.asList;

public class ProceduresTest extends TestCase
{
    public void test_sumOddsSquare()
    {
        BiTuple<?, ?> biTree = biTuple(biTuple(1, biTuple(2, 7)), biTuple(19, biTuple(12, 14)));
        assertEquals(411, sumOddsSquare(biTree));
    }
    
    public void test_oddFibsWithStream()
    {
        assertEquals(asList(1, 2, 4, 5), oddFibs(6));
    }
}

liststream.Procedures

import static fayelab.sicp.stream.liststream.StreamOp.*;
import static java.util.Arrays.asList;

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

public class Procedures
{
    public static <T1, T2> int sumOddsSquare(BiTuple<T1, T2> biTree)
    {
        return accStream((x, y) -> x + y, 
                         0, 
                         mapStream(x -> square(x),
                                   filterStream((Integer x) -> isOdd(x),
                                                enumTree(biTree))));
    }
    
    public static List<Integer> oddFibs(int n)
    {
        return accStream((idx, acc) -> glue(idx, acc), 
                         new ArrayList<>(),
                         filterStream(idx -> isOdd(fib(idx)),
                                      enumInterval(0, n)));
    }

    private static boolean isOdd(int n)
    {
        return n % 2 == 1;
    }
    
    private static int square(int n)
    {
        return n * n;
    }
    
    private static int fib(int n)
    {
        int a = 0;
        int b = 1;
        int s = 0;
        
        if(n == 0)
        {
            return a;
        }
        
        if(n == 1)
        {
            return b;
        }
        
        for(int i = 0; i <= n - 2; i++)
        {
            s = a + b;
            a = b;
            b = s;
        }
        
        return s;
    }
    
    private static <T> List<T> glue(T newHead, List<T> list)
    {
        List<T> result = new ArrayList<>();
        result.add(newHead);
        result.addAll(list);
        return result;
    }
}

2.4 用自定义Stream(Delay)实现

依然用List数据结构定义Stream，但不同于前面的List，这里的List只有两个元素。第一个元素是流的头元素，可通过head()访问。第二个元素是一个Supplier函数接口，调用tail()则调用Supplier.get()方法，返回接下来的流。因为头元素和Supplier函数接口类型不同，所以只能用长度为2的List数据结构定义Stream。

为了方便测试，在StreamOp中增加了listToStream和collectStream两个辅助方法。

delaystream.StreamOpTest

import junit.framework.TestCase;

import static java.util.Arrays.asList;
import static fayelab.sicp.stream.delaystream.StreamOp.*;

public class StreamOpTest extends TestCase
{
    public void test_stream_constructors_and_selectors()
    {
        assertEquals(asList(1, 2, 3), collectStream(consStream(1, () -> listToStream(2, 3))));
        assertEquals(asList(1), collectStream(consStream(1, () -> listToStream())));
        assertEquals(asList(), collectStream(theEmptyStream()));
    }

    public void test_mapStream()
    {
        assertEquals(asList(2, 4), collectStream(mapStream((Integer x) -> x * 2, listToStream(1, 2))));
        assertEquals(asList("1", "2"), collectStream(mapStream(x -> String.valueOf(x), listToStream(1, 2))));
        assertEquals(asList(), collectStream(mapStream(x -> x, listToStream())));
    }
    
    public void test_filterStream()
    {
        assertEquals(asList(2, 4), collectStream(filterStream((Integer x) -> x % 2 == 0, listToStream(1, 2, 3, 4))));
        assertEquals(asList(), collectStream(filterStream(x -> true, listToStream())));
    }
    
    public void test_accStream()
    {
        assertEquals(new Integer(10), accStream((Integer x, Integer y) -> x + y, 0, listToStream(1, 2, 3, 4)));
        assertEquals("123", accStream((x, y) -> String.join("", String.valueOf(x), String.valueOf(y)), "", listToStream(1, 2, 3)));
        assertEquals(new Integer(0), accStream((Integer x, Integer y) -> x + y, 0, listToStream()));
        assertEquals(new Integer(1), accStream((Integer x, Integer y) -> x + y, 0, listToStream(1)));
    }
    
    public void test_appendStream()
    {
        assertEquals(asList(1, 2, 3, 4), collectStream(appendStream(listToStream(1, 2), listToStream(3, 4))));
        assertEquals(asList(3, 4), collectStream(appendStream(listToStream(), listToStream(3, 4))));
        assertEquals(asList(1, 2), collectStream(appendStream(listToStream(1, 2), listToStream())));
        assertEquals(asList(), collectStream(appendStream(listToStream(), listToStream())));
    }

    public void test_enumTree()
    {
        assertEquals(asList(1, 2, 7, 19, 12, 14), 
                     collectStream(enumTree(biTuple(biTuple(1, biTuple(2, 7)), 
                                            biTuple(19, biTuple(12, 14))))));
        
        assertEquals(asList(1, 2, 3, 7, 19, 12, 13, 14), 
                     collectStream(enumTree(biTuple(biTuple(1, biTuple(biTuple(2, 3), 7)), 
                                            biTuple(19, biTuple(12, biTuple(13, 14)))))));
    }
    
    public void test_enumInterval()
    {
        assertEquals(asList(1, 2, 3, 4), collectStream(enumInterval(1, 4)));
        assertEquals(asList(), collectStream(enumInterval(3, 1)));
    }
    
    public void test_flatten()
    {
        assertEquals(asList(1, 2, 3, 4, 5), collectStream(flatten(listToStream(listToStream(1, 2), 
                                                                               listToStream(3, 4), 
                                                                               listToStream(5)))));
        assertEquals(asList(1, 2), collectStream(flatten(listToStream(listToStream(1, 2)))));
        assertEquals(asList(), collectStream(flatten(listToStream())));
    }
    
    public void test_flatmap()
    {
        assertEquals(asList(1, 2, 3, 2, 4, 6), collectStream(flatmap((Integer x) -> listToStream(x, x * 2, x * 3), listToStream(1, 2))));
        assertEquals(asList(), collectStream(flatmap(x -> asList(x), asList())));
    }
}

delaystream.StreamOp

import java.util.List;
import java.util.function.BiFunction;
import java.util.function.Function;
import java.util.function.Predicate;
import java.util.function.Supplier;

import java.util.ArrayList;

import static java.util.Arrays.asList;

public class StreamOp
{
    //Constructors
    public static <T> List<Object> consStream(T head, Supplier<List<Object>> tail)
    {
        return asList(head, tail);
    }
    
    public static List<Object> theEmptyStream()
    {
        return asList();
    }
    
    //Selectors
    @SuppressWarnings("unchecked")
    public static <T> T head(List<Object> s)
    {
        return (T)s.get(0);
    }
    
    @SuppressWarnings("unchecked")
    public static List<Object> tail(List<Object> s)
    {
        return ((Supplier<List<Object>>)s.get(1)).get();
    }
    
    public static boolean isEmptyStream(List<Object> s)
    {
        return s.isEmpty();
    }
    
    public static <T, R> List<Object> mapStream(Function<T, R> proc, List<Object> s)
    {
        if(isEmptyStream(s))
        {
            return theEmptyStream();
        }
        
        return consStream(proc.apply(head(s)), () -> mapStream(proc, tail(s)));
    }
    
    public static <T> List<Object> filterStream(Predicate<T> pred, List<Object> s)
    {
        if(isEmptyStream(s))
        {
            return theEmptyStream();
        }
        
        if(pred.test(head(s)))
        {
            return consStream(head(s), () -> filterStream(pred, tail(s)));
        }
        
        return filterStream(pred, tail(s));
    }
    
    public static <T, R> R accStream(BiFunction<T, R, R> proc, R acc, List<Object> s)
    {
        if(isEmptyStream(s))
        {
            return acc;
        }
        
        return proc.apply(head(s), accStream(proc, acc, tail(s)));
    }
    
    public static List<Object> appendStream(List<Object> s1, List<Object> s2)
    {
        if(isEmptyStream(s1))
        {
            return s2;
        }
        
        return consStream(head(s1), () -> appendStream(tail(s1), s2));
    }
    
    public static List<Object> enumTree(Object obj)
    {
        if(obj instanceof BiTuple)
        {
            BiTuple<?, ?> biTuple = (BiTuple<?, ?>)obj;
            return appendStream(enumTree(biTuple.getElement1()), enumTree(biTuple.getElement2()));
        }
        
        return consStream(obj, () -> theEmptyStream());
    }
    
    public static List<Object> enumInterval(int low, int high)
    {
        if(low > high)
        {
            return theEmptyStream();
        }
        
        return consStream(low, () -> enumInterval(low + 1, high));
    }
    
    public static List<Object> flatten(List<Object> sos)
    {
        return accStream((List<Object> s1, List<Object> s2) -> appendStream(s1, s2), theEmptyStream(), sos);
    }
    
    public static <T> List<Object> flatmap(Function<T, List<Object>> proc, List<Object> s)
    {
        return flatten(mapStream(proc, s));
    }
    
    //Auxiliary methods
    @SafeVarargs
    static <T> List<Object> listToStream(T...elements)
    {
        return listToStream(new ArrayList<>(asList(elements)));
    }
    
    private static <T> List<Object> listToStream(List<T> list)
    {
        if(list.isEmpty())
        {
            return theEmptyStream();
        }
        
        T head = list.remove(0);
        return consStream(head, () -> listToStream(list));
    }
    
    static <T> List<T> collectStream(List<Object> s)
    {
        List<T> result = new ArrayList<>();
        
        if(isEmptyStream(s))
        {
            return result;
        }
        
        result.add(head(s));
        result.addAll(collectStream(tail(s)));
        
        return result;
    }
    
    public static <T1, T2> BiTuple<T1, T2> biTuple(T1 element1, T2 element2)
    {
        return new BiTuple<>(element1, element2);
    }

    static class BiTuple<T1, T2>
    {
        private T1 element1;
        private T2 element2;
        
        public BiTuple(T1 element1, T2 element2)
        {
            this.element1 = element1;
            this.element2 = element2;
        }
    
        public T1 getElement1()
        {
            return element1;
        }
    
        public T2 getElement2()
        {
            return element2;
        }
    }
}

delaystream.ProceduresTest

import junit.framework.TestCase;

import static java.util.Arrays.asList;
import static fayelab.sicp.stream.delaystream.StreamOp.*;
import static fayelab.sicp.stream.delaystream.Procedures.*;

public class ProceduresTest extends TestCase
{
    public void test_sumOddsSquare()
    {
        BiTuple<?, ?> biTree = biTuple(biTuple(1, biTuple(2, 7)), biTuple(19, biTuple(12, 14)));
        assertEquals(411, sumOddsSquare(biTree));
    }
    
    public void test_oddFibs()
    {
        assertEquals(asList(1, 2, 4, 5), oddFibs(6));
    }
}

delaystream.Procedures

import static java.util.Arrays.asList;

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

import static fayelab.sicp.stream.delaystream.StreamOp.*;

public class Procedures
{
    public static <T1, T2> int sumOddsSquare(BiTuple<T1, T2> biTree)
    {
        return accStream((Integer x, Integer y) -> x + y,
                         0,
                         mapStream((Integer x) -> square(x),
                                   filterStream((Integer x) -> isOdd(x),
                                                enumTree(biTree))));
    }
    
    public static List<Integer> oddFibs(int n)
    {
        return accStream((idx, acc) -> glue(idx, acc), 
                         new ArrayList<>(),
                         filterStream((Integer idx) -> isOdd(fib(idx)),
                                      enumInterval(0, n)));
    }
    
    private static boolean isOdd(int n)
    {
        return n % 2 == 1;
    }
    
    private static int square(int n)
    {
        return n * n;
    }
    
    private static int fib(int n)
    {
        int a = 0;
        int b = 1;
        int s = 0;
        
        if(n == 0)
        {
            return a;
        }
        
        if(n == 1)
        {
            return b;
        }
        
        for(int i = 0; i <= n - 2; i++)
        {
            s = a + b;
            a = b;
            b = s;
        }
        
        return s;
    }
    
    private static <T> List<T> glue(T newHead, List<T> list)
    {
        List<T> result = new ArrayList<>();
        result.add(newHead);
        result.addAll(list);
        return result;
    }
}

3 primeSumPairs

3.1 未用Stream实现

nostream.ProceduresTest

    public void test_primeSumPairs()
    {
        assertEquals(asList(asList(2, 1), asList(3, 2), asList(4, 1), asList(4, 3), asList(5, 2)), 
                     primeSumPairs(5));
    }

nostream.Procedures

    public static List<List<Integer>> primeSumPairs(int n)
    {
        List<List<Integer>> result = new ArrayList<>();
        
        for(int i = 2; i <= n; i++)
        {
            for(int j = 1; j < i; j++)
            {
                if(isPrime(i + j))
                {
                    result.add(asList(i, j));
                }
            }
        }
        
        return result;
    }

    private static boolean isPrime(int n)
    {
        for(int i = 2; i < n; i++)
        {
            if(n % i == 0)
            {
                return false;
            }
        }
        
        return true;
    }

3.2 用Java 8 Stream实现

java8stream.ProceduresTest

    public void test_primeSumPairs()
    {
        assertEquals(asList(asList(2, 1), asList(3, 2), asList(4, 1), asList(4, 3), asList(5, 2)), 
                primeSumPairs(5));
    }

java8stream.Procedures

    public static List<List<Integer>> primeSumPairs(int n)
    {
        return enumInterval(2, n).flatMap(i -> enumInterval(1, i - 1).map(j -> asList(i, j))
                                                                     .filter(pair -> isPrime(pair.get(0) + pair.get(1))))
                                 .collect(toList());
    }

    private static boolean isPrime(int n)
    {
        return enumInterval(2, n - 1).noneMatch(i -> n % i == 0);
    }

3.3 用自定义Stream(List)实现

liststream.StreamOpTest

    public void test_noneMatch()
    {
        assertTrue(noneMatch(x -> x % 2 == 0, asList(1, 3, 5)));
        assertTrue(noneMatch(x -> true, asList()));
        assertTrue(noneMatch(x -> false, asList()));
    }

liststream.StreamOp

    public static <T> boolean noneMatch(Predicate<T> pred, List<T> s)
    {
        if(isEmptyStream(s))
        {
            return true;
        }
        
        if(pred.test(head(s)))
        {
            return false;
        }
        
        return noneMatch(pred, tail(s));
    }

liststream.ProceduresTest

    public void test_primeSumPairs()
    {
        assertEquals(asList(asList(2, 1), asList(3, 2), asList(4, 1), asList(4, 3), asList(5, 2)), 
                primeSumPairs(5));
    }

liststream.Procedures

    public static List<List<Integer>> primeSumPairs(int n)
    {
        return filterStream((List<Integer> pair) -> isPrime(pair.get(0) + pair.get(1)),
                            flatmap(i -> mapStream(j -> asList(i, j),
                                                   enumInterval(1, i - 1)), 
                                    enumInterval(2, n)));
    }

    private static boolean isPrime(int n)
    {
        return noneMatch(i -> n % i == 0, enumInterval(2, n - 1));
    }

3.4 用自定义Stream(Delay)实现

delaystream.StreamOpTest

    public void test_noneMatch()
    {
        assertTrue(noneMatch((Integer x) -> x % 2 == 0, listToStream(1, 3, 5)));
        assertTrue(noneMatch(x -> true, listToStream()));
        assertTrue(noneMatch(x -> false, listToStream()));
    }

delaystream.StreamOp

    public static <T> boolean noneMatch(Predicate<T> pred, List<Object> s)
    {
        if(isEmptyStream(s))
        {
            return true;
        }
        
        if(pred.test(head(s)))
        {
            return false;
        }
        
        return noneMatch(pred, tail(s));
    }

delaystream.ProceduresTest

    public void test_primeSumPairs()
    {
        assertEquals(asList(asList(2, 1), asList(3, 2), asList(4, 1), asList(4, 3), asList(5, 2)), 
                     primeSumPairs(5));
    }

delaystream.Procedures

    public static List<List<Integer>> primeSumPairs(int n)
    {
        return collectStream(filterStream((List<Integer> pair) -> isPrime(pair.get(0) + pair.get(1)),
                                          flatmap((Integer i) -> mapStream(j -> asList(i, j),
                                                                           enumInterval(1, i - 1)),
                                                  enumInterval(2, n))));
    }

    private static boolean isPrime(int n)
    {
        return noneMatch((Integer i) -> n % i == 0, enumInterval(2, n - 1));
    }

4 triples

4.1 未用Stream实现

nostream.ProceduresTest

    public void test_triples()
    {
        assertEquals(asList(asList(3, 2, 1),
                            asList(4, 2, 1), asList(4, 3, 1), asList(4, 3, 2),
                            asList(5, 2, 1), asList(5, 3, 1), asList(5, 3, 2), 
                            asList(5, 4, 1), asList(5, 4, 2), asList(5, 4, 3)),
                     triples(5));
    }

nostream.Procedures

    public static List<List<Integer>> triples(int n)
    {
        List<List<Integer>> result = new ArrayList<>();
        
        for(int i = 3; i <= n; i++)
        {
            for(int j = 2; j < i; j++)
            {
                for(int k = 1; k < j; k++)
                {
                    result.add(asList(i, j, k));
                }
            }
        }
        
        return result;
    }

4.2 用Java 8 Stream实现

java8stream.ProceduresTest

    public void test_triples()
    {
        assertEquals(asList(asList(3, 2, 1),
                            asList(4, 2, 1), asList(4, 3, 1), asList(4, 3, 2),
                            asList(5, 2, 1), asList(5, 3, 1), asList(5, 3, 2), 
                            asList(5, 4, 1), asList(5, 4, 2), asList(5, 4, 3)),
                     triples(5));
    }

java8stream.Procedures

    public static List<List<Integer>> triples(int n)
    {
        return enumInterval(3, n).flatMap(i -> enumInterval(2, i - 1).flatMap(j -> enumInterval(1, j - 1).map(k -> asList(i, j, k))))
                                 .collect(toList());
    }

4.3 用自定义Stream(List)实现

liststream.ProceduresTest

    public void test_triples()
    {
        assertEquals(asList(asList(3, 2, 1),
                            asList(4, 2, 1), asList(4, 3, 1), asList(4, 3, 2),
                            asList(5, 2, 1), asList(5, 3, 1), asList(5, 3, 2), 
                            asList(5, 4, 1), asList(5, 4, 2), asList(5, 4, 3)),
                     triples(5));
    }

liststream.Procedures

    public static List<List<Integer>> triples(int n)
    {
        return flatmap(i -> flatmap(j -> mapStream(k -> asList(i, j, k), enumInterval(1, j - 1)), 
                                    enumInterval(2, i - 1)), 
                       enumInterval(3, n));
    }

4.4 用自定义Stream(Delay)实现

delaystream.ProceduresTest

    public void test_triples()
    {
        assertEquals(asList(asList(3, 2, 1),
                            asList(4, 2, 1), asList(4, 3, 1), asList(4, 3, 2),
                            asList(5, 2, 1), asList(5, 3, 1), asList(5, 3, 2), 
                            asList(5, 4, 1), asList(5, 4, 2), asList(5, 4, 3)),
                     triples(5));
    }

delaystream.Procedures

    public static List<List<Integer>> triples(int n)
    {
        return collectStream(flatmap((Integer i) -> flatmap((Integer j) -> mapStream(k -> asList(i, j, k), 
                                                                                     enumInterval(1, j - 1)), 
                                                            enumInterval(2, i - 1)), 
                                     enumInterval(3, n)));
    }

5 Eight Queens Problem

5.1 Backtracking Search

Back tracking算法。未用Stream。采用修改引用的方式。

5.1.1 One Solution

求出一个解。

nostream.BtQueensTest

public class BtQueensTest extends TestCase
{
    public void test_solveOne()
    {
        assertEquals(asList(asList(1, 2), asList(2, 4), asList(3, 1), asList(4, 3)), solveOne(4).get());
        
        assertEquals(Optional.empty(), solveOne(3));
        
        assertEquals(asList(asList(1, 1), asList(2, 5), asList(3, 8), asList(4, 6),
                            asList(5, 3), asList(6, 7), asList(7, 2), asList(8, 4)),
                     solveOne(8).get());
    }
}

nostream.BtQueens

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

import static java.util.Arrays.*;

public class BtQueens
{
    public static Optional<List<List<Integer>>> solveOne(int n)
    {
        List<List<Integer>> solution = emptyBoard();
        solveOne(n, 1, 1, solution);
        return solution.isEmpty() ? Optional.empty() : Optional.of(solution);
    }

    private static void solveOne(int size, int curRow, int curCol, List<List<Integer>> curPoses)
    {
        if(curRow > size)
        {
            return;
        }
        
        if(curCol > size)
        {
            if(curPoses.isEmpty())
            {
                return;
            }
            
            List<Integer> lastPos = curPoses.remove(curPoses.size() - 1);
            solveOne(size, lastPos.get(0), lastPos.get(1) + 1, curPoses);
            return;
        }
        
        adjoinPos(curRow, curCol, curPoses);
        if(isSafe(curPoses))
        {
            solveOne(size, curRow + 1, 1, curPoses);
            return;
        }
        
        curPoses.remove(curPoses.size() - 1);
        solveOne(size, curRow, curCol + 1, curPoses);
    }
    
    private static List<List<Integer>> emptyBoard()
    {
        return new ArrayList<>();
    }

    private static void adjoinPos(int curRow, int curCol, List<List<Integer>> curPoses)
    {
        curPoses.add(asList(curRow, curCol));
    }
    
    private static boolean isSafe(List<List<Integer>> poses)
    {
        List<Integer> newPos = poses.get(poses.size() - 1);
        List<List<Integer>> restPoses = poses.subList(0, poses.size() - 1);
        return isNotSameCol(newPos, restPoses) && isNotDiagonal(newPos, restPoses);
    }

    private static boolean isNotSameCol(List<Integer> newPos, List<List<Integer>> restPoses)
    {
        return restPoses.stream()
                        .noneMatch(restPos -> newPos.get(1) == restPos.get(1));
    }

    private static boolean isNotDiagonal(List<Integer> newPos, List<List<Integer>> restPoses)
    {
        return restPoses.stream()
                        .noneMatch(restPos -> Math.abs(newPos.get(0) - restPos.get(0)) 
                                                == Math.abs(newPos.get(1) - restPos.get(1)));
    }
}

5.1.2 All Solutions

求出所有解。

nostream.BtQueensTest

    public void test_solveAll()
    {
        assertEquals(asList(asList(asList(1, 2), asList(2, 4), asList(3, 1), asList(4, 3)),
                            asList(asList(1, 3), asList(2, 1), asList(3, 4), asList(4, 2))), solveAll(4).get());
        
        assertEquals(Optional.empty(), solveAll(3));
        
        assertEquals(92, solveAll(8).get().size());
    }

nostream.BtQueens

    public static Optional<List<List<List<Integer>>>> solveAll(int n)
    {
        List<List<List<Integer>>> solutions = new ArrayList<>();
        solveAll(n, 1, 1, emptyBoard(), solutions);
        return solutions.isEmpty() ? Optional.empty() : Optional.of(solutions);
    }

    private static void solveAll(int size, int curRow, int curCol, 
            List<List<Integer>> curPoses, List<List<List<Integer>>> solutions)
    {
        if(curRow > size)
        {
            solutions.add(new ArrayList<>(curPoses));
            List<Integer> lastPos = curPoses.remove(curPoses.size() - 1);
            solveAll(size, lastPos.get(0), lastPos.get(1) + 1, curPoses, solutions);
            return;
        }
        
        if(curCol > size)
        {
            if(curPoses.isEmpty())
            {
                return;
            }
            
            List<Integer> lastPos = curPoses.remove(curPoses.size() - 1);
            solveAll(size, lastPos.get(0), lastPos.get(1) + 1, curPoses, solutions);
            return;
        }
        
        adjoinPos(curRow, curCol, curPoses);
        if(isSafe(curPoses))
        {
            solveAll(size, curRow + 1, 1, curPoses, solutions);
            return;
        }
        
        curPoses.remove(curPoses.size() - 1);
        solveAll(size, curRow, curCol + 1, curPoses, solutions);
    }
}

5.2 Recursive Strategy

递归算法。

不能采用修改引用的方式，只能采用返回新值的方式。

写了两种遍历顺序：“先restPoses再col”和“先col再restPoses”。在第二种遍历顺序中，针对每一列(col)都要做一次fill_Rows(Size, Row-1)。在第一种遍历顺序中，每一行(row)只需要做一次fill_Rows(Size, Row-1)。第二种遍历顺序的计算量远大于第一种，从单元测试的运行时间上也可以看到差别。除此以外，solutions中solution的顺序也稍有区别，单元测试中四皇后的计算结果可以看到区别。

5.2.1 用Java 8 Stream实现

在运行ReQueensTest时，如果是计算八皇后，需要设置JVM运行参数“VM arguments”为“-Xms512m -Xmx1024m -Xss64m”，否则会抛出StackOverflowError。

单元测试运行耗时：

  • 先restPoses再col(solveAll)：0.015s
  • 先col再restPoses(solveAll2)：11.049s

java8stream.ReQueensTest

import java.util.Optional;

import junit.framework.TestCase;

import static java.util.Arrays.asList;
import static fayelab.sicp.stream.java8stream.ReQueens.*;

public class ReQueensTest extends TestCase
{
    public void test_solveAll()
    {
        assertEquals(asList(asList(asList(1, 2), asList(2, 4), asList(3, 1), asList(4, 3)),
                            asList(asList(1, 3), asList(2, 1), asList(3, 4), asList(4, 2))), solveAll(4).get());
        
        assertEquals(Optional.empty(), solveAll(3));
        
        assertEquals(92, solveAll(8).get().size());
    }

    public void test_solveAll2()
    {
        assertEquals(asList(asList(asList(1, 3), asList(2, 1), asList(3, 4), asList(4, 2)),
                            asList(asList(1, 2), asList(2, 4), asList(3, 1), asList(4, 3))), solveAll2(4).get());
        
        assertEquals(Optional.empty(), solveAll2(3));
        
        assertEquals(92, solveAll2(8).get().size());
    }
}

java8stream.ReQueens

import java.util.ArrayList;
import java.util.List;
import java.util.Optional;
import java.util.stream.IntStream;
import java.util.stream.Stream;

import static java.util.Arrays.asList;
import static java.util.stream.Collectors.toList;

public class ReQueens
{
    public static Optional<List<List<List<Integer>>>> solveAll(int n)
    {
        List<List<List<Integer>>> solutions = fillRows(n, n).collect(toList());
        return solutions.isEmpty() ? Optional.empty() : Optional.of(solutions);
    }
    
    private static Stream<List<List<Integer>>> fillRows(int size, int row)
    {
        if(row == 0)
        {
            return Stream.of(emptyBoard());
        }
                
        return fillRows(size, row - 1)
                .flatMap(restPoses -> enumInterval(1, size).map(col -> adjoinPos(row, col, restPoses)))
                .filter(poses -> isSafe(poses));
    }

    public static Optional<List<List<List<Integer>>>> solveAll2(int n)
    {
        List<List<List<Integer>>> solutions = fillRows2(n, n).collect(toList());
        return solutions.isEmpty() ? Optional.empty() : Optional.of(solutions);
    }
    
    private static Stream<List<List<Integer>>> fillRows2(int size, int row)
    {
        if(row == 0)
        {
            return Stream.of(emptyBoard());
        }
                
        return enumInterval(1, size).flatMap(col -> fillRows2(size, row - 1).map(restPoses -> adjoinPos(row, col, restPoses)))
                                    .filter(poses -> isSafe(poses));
    }
    
    private static Stream<Integer> enumInterval(int low, int high)
    {
        return IntStream.rangeClosed(low, high).boxed();
    }

    private static List<List<Integer>> emptyBoard()
    {
        return new ArrayList<>();
    }

    private static List<List<Integer>> adjoinPos(int curRow, int curCol, List<List<Integer>> curPoses)
    {
        List<List<Integer>> result = new ArrayList<>();
        result.addAll(curPoses);
        result.add(asList(curRow, curCol));
        return result;
    }
    
    private static boolean isSafe(List<List<Integer>> poses)
    {
        List<Integer> newPos = poses.get(poses.size() - 1);
        List<List<Integer>> restPoses = poses.subList(0, poses.size() - 1);
        return isNotSameCol(newPos, restPoses) && isNotDiagonal(newPos, restPoses);
    }

    private static boolean isNotSameCol(List<Integer> newPos, List<List<Integer>> restPoses)
    {
        return restPoses.stream()
                        .noneMatch(restPos -> newPos.get(1) == restPos.get(1));
    }

    private static boolean isNotDiagonal(List<Integer> newPos, List<List<Integer>> restPoses)
    {
        return restPoses.stream()
                        .noneMatch(restPos -> Math.abs(newPos.get(0) - restPos.get(0)) 
                                                == Math.abs(newPos.get(1) - restPos.get(1)));
    }
}

5.2.2 用自定义Stream(List)实现

在运行ReQueensTest时，如果是计算八皇后，需要设置JVM运行参数“VM arguments”为“-Xms512m -Xmx1024m -Xss64m”，否则会抛出StackOverflowError。

单元测试运行耗时：

  • 先restPoses再col(solveAll)：0.064s
  • 先col再restPoses(solveAll2)：33.912s

liststream.ReQueensTest

import java.util.Optional;

import junit.framework.TestCase;

import static java.util.Arrays.asList;
import static fayelab.sicp.stream.liststream.ReQueens.*;

public class ReQueensTest extends TestCase
{
    public void test_solveAll()
    {
        assertEquals(asList(asList(asList(1, 2), asList(2, 4), asList(3, 1), asList(4, 3)),
                            asList(asList(1, 3), asList(2, 1), asList(3, 4), asList(4, 2))), solveAll(4).get());
        
        assertEquals(Optional.empty(), solveAll(3));
        
        assertEquals(92, solveAll(8).get().size());
    }

    public void test_solveAll2()
    {
        assertEquals(asList(asList(asList(1, 3), asList(2, 1), asList(3, 4), asList(4, 2)),
                            asList(asList(1, 2), asList(2, 4), asList(3, 1), asList(4, 3))), solveAll2(4).get());
        
        assertEquals(Optional.empty(), solveAll2(3));
        
        assertEquals(92, solveAll2(8).get().size());
    }
}

liststream.ReQueens

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

import static java.util.Arrays.asList;
import static fayelab.sicp.stream.liststream.StreamOp.*;

public class ReQueens
{
    public static Optional<List<List<List<Integer>>>> solveAll(int n)
    {
        List<List<List<Integer>>> solutions = fillRows(n, n);
        return solutions.isEmpty() ? Optional.empty() : Optional.of(solutions);
    }
    
    private static List<List<List<Integer>>> fillRows(int size, int row)
    {
        if(row == 0)
        {
            List<List<List<Integer>>> emptyList = new ArrayList<>();
            emptyList.add(emptyBoard());
            return emptyList;
        }
        
        return filterStream((List<List<Integer>> poses) -> isSafe(poses), 
                            flatmap(restPoses -> mapStream(col -> adjoinPos(row, col, restPoses), 
                                                           enumInterval(1, size)), 
                                    fillRows(size, row - 1)));
    }

    public static Optional<List<List<List<Integer>>>> solveAll2(int n)
    {
        List<List<List<Integer>>> solutions = fillRows2(n, n);
        return solutions.isEmpty() ? Optional.empty() : Optional.of(solutions);
    }
    
    private static List<List<List<Integer>>> fillRows2(int size, int row)
    {
        if(row == 0)
        {
            List<List<List<Integer>>> emptyList = new ArrayList<>();
            emptyList.add(emptyBoard());
            return emptyList;
        }
        
        return filterStream((List<List<Integer>> poses) -> isSafe(poses), 
                            flatmap(col -> mapStream(restPoses -> adjoinPos(row, col, restPoses), fillRows2(size, row - 1)),
                                    enumInterval(1, size)));
    }

    private static List<List<Integer>> emptyBoard()
    {
        return new ArrayList<>();
    }

    private static List<List<Integer>> adjoinPos(int curRow, int curCol, List<List<Integer>> curPoses)
    {
        List<List<Integer>> result = new ArrayList<>();
        result.addAll(curPoses);
        result.add(asList(curRow, curCol));
        return result;
    }
    
    private static boolean isSafe(List<List<Integer>> poses)
    {
        List<Integer> newPos = poses.get(poses.size() - 1);
        List<List<Integer>> restPoses = poses.subList(0, poses.size() - 1);
        return isNotSameCol(newPos, restPoses) && isNotDiagonal(newPos, restPoses);
    }

    private static boolean isNotSameCol(List<Integer> newPos, List<List<Integer>> restPoses)
    {
        return noneMatch(restPos -> newPos.get(1) == restPos.get(1), restPoses);
    }

    private static boolean isNotDiagonal(List<Integer> newPos, List<List<Integer>> restPoses)
    {
        return noneMatch(restPos -> Math.abs(newPos.get(0) - restPos.get(0)) 
                                        == Math.abs(newPos.get(1) - restPos.get(1)),
                         restPoses);
    }
}

5.2.3 用自定义Stream(Delay)实现

在运行ReQueensTest时，如果是计算八皇后，需要设置JVM运行参数“VM arguments”为“-Xms512m -Xmx1024m -Xss64m”，否则会抛出StackOverflowError。

单元测试运行耗时：

  • 先restPoses再col(solveAll)：0.028s
  • 先col再restPoses(solveAll2)：java.lang.OutOfMemoryError: GC overhead limit exceeded

delaystream.ReQueensTest

import java.util.Optional;

import junit.framework.TestCase;

import static java.util.Arrays.asList;
import static fayelab.sicp.stream.delaystream.ReQueens.*;

public class ReQueensTest extends TestCase
{
    public void test_solveAll()
    {
        assertEquals(asList(asList(asList(1, 2), asList(2, 4), asList(3, 1), asList(4, 3)),
                            asList(asList(1, 3), asList(2, 1), asList(3, 4), asList(4, 2))), solveAll(4).get());
        
        assertEquals(Optional.empty(), solveAll(3));
        
        assertEquals(92, solveAll(8).get().size());
    }
    
    public void test_solveAll2()
    {
        assertEquals(asList(asList(asList(1, 3), asList(2, 1), asList(3, 4), asList(4, 2)),
                            asList(asList(1, 2), asList(2, 4), asList(3, 1), asList(4, 3))), solveAll2(4).get());
        
        assertEquals(Optional.empty(), solveAll2(3));
        
        assertEquals(92, solveAll2(8).get().size());
    }
}

delaystream.ReQueens

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

import static java.util.Arrays.asList;
import static fayelab.sicp.stream.delaystream.StreamOp.*;

public class ReQueens
{
    public static Optional<List<List<List<Integer>>>> solveAll(int n)
    {
        List<List<List<Integer>>> solutions = collectStream(fillRows(n, n));
        return solutions.isEmpty() ? Optional.empty() : Optional.of(solutions);
    }
    
    private static List<Object> fillRows(int size, int row)
    {
        if(row == 0)
        {
            return consStream(emptyBoard(), () -> theEmptyStream());
        }
        
        return filterStream((List<List<Integer>> poses) -> isSafe(poses), 
                            flatmap((List<List<Integer>> restPoses) -> mapStream((Integer col) -> adjoinPos(row, col, restPoses), 
                                                                                 enumInterval(1, size)), 
                                    fillRows(size, row - 1)));
    }
    
    public static Optional<List<List<List<Integer>>>> solveAll2(int n)
    {
        List<List<List<Integer>>> solutions = collectStream(fillRows2(n, n));
        return solutions.isEmpty() ? Optional.empty() : Optional.of(solutions);
    }
    
    private static List<Object> fillRows2(int size, int row)
    {
        if(row == 0)
        {
            return consStream(emptyBoard(), () -> theEmptyStream());
        }
        
        return filterStream((List<List<Integer>> poses) -> isSafe(poses), 
                            flatmap((Integer col) -> mapStream((List<List<Integer>> restPoses) -> adjoinPos(row, col, restPoses), 
                                                                fillRows2(size, row - 1)),
                                    enumInterval(1, size)));
    }

    private static List<List<Integer>> emptyBoard()
    {
        return new ArrayList<>();
    }

    private static List<List<Integer>> adjoinPos(int curRow, int curCol, List<List<Integer>> curPoses)
    {
        List<List<Integer>> result = new ArrayList<>();
        result.addAll(curPoses);
        result.add(asList(curRow, curCol));
        return result;
    }
    
    private static boolean isSafe(List<List<Integer>> poses)
    {
        List<Integer> newPos = poses.get(poses.size() - 1);
        List<List<Integer>> restPoses = poses.subList(0, poses.size() - 1);
        return isNotSameCol(newPos, restPoses) && isNotDiagonal(newPos, restPoses);
    }

    private static boolean isNotSameCol(List<Integer> newPos, List<List<Integer>> restPoses)
    {
        return restPoses.stream()
                        .noneMatch(restPos -> newPos.get(1) == restPos.get(1));
    }

    private static boolean isNotDiagonal(List<Integer> newPos, List<List<Integer>> restPoses)
    {
        return restPoses.stream()
                        .noneMatch(restPos -> Math.abs(newPos.get(0) - restPos.get(0)) 
                                                == Math.abs(newPos.get(1) - restPos.get(1)));
    }
}

6 Second Prime

用自定义Stream(Delay)实现。

delaystream.ProceduresTest 在运行ProceduresTest时，需要设置JVM运行参数“VM arguments”为“-Xms512m -Xmx1024m -Xss64m”，否则会抛出StackOverflowError。

    public void test_secondPrime()
    {
        assertEquals(10009, secondPrime());
    }

delaystream.Procedures

    public static int secondPrime()
    {
        return head(tail(filterStream((Integer x) -> isPrime(x), enumInterval(10000, 1000000))));
    }

7 No Sevens & Sieve of Eratosthenes

用自定义Stream(Delay)实现。

在StreamOp中增加了nthStream、printStream、integersFrom、collectStreamLimit等辅助方法。

delaystream.StreamOpTest

    public void test_nthStream()
    {
        List<Object> s = listToStream(0, 1);
        assertEquals(new Integer(0), nthStream(0, s));
        assertEquals(new Integer(1), nthStream(1, s));
        
        try
        {
            nthStream(2, s);
            assertTrue(false);
        }
        catch(RuntimeException e)
        {
            assertEquals("This index does not exist.", e.getMessage());
        }
    }
    
//    public void test_printStream()
//    {
//        printStream(listToStream(0, 1));
//    }
    
    public void test_integersFrom()
    {
        List<Object> s = integersFrom(2);
        assertEquals(new Integer(2), nthStream(0, s));
        assertEquals(new Integer(3), nthStream(1, s));
        
        List<Object> s2 = integersFrom(0);
        assertEquals(asList(0, 1, 2), collectStreamLimit(3, s2));
        assertEquals(asList(), collectStreamLimit(-1, s2));
        
        assertEquals(asList(), collectStreamLimit(-1, theEmptyStream()));
    }

delaystream.StreamOp

    static <T> List<T> collectStreamLimit(int num, List<Object> s)
    {
        List<T> result = new ArrayList<>();
        collectStreamLimit(num, s, result);
        return result;        
    }
    
    private static <T> void collectStreamLimit(int num, List<Object> s, List<T> result)
    {
        if(isEmptyStream(s))
        {
            return;
        }
        
        if(num <= 0)
        {
            return;
        }
        
        result.add(head(s));
        collectStreamLimit(num - 1, tail(s), result);
    }

delaystream.ProceduresTest

    public void test_noSevens()
    {
        List<Object> s = noSevens();
        assertEquals(new Integer(1), nthStream(0, s));
        assertEquals(new Integer(8), nthStream(6, s));
        assertEquals(new Integer(16), nthStream(13, s));
        
        assertEquals(asList(1, 2, 3, 4, 5, 6, 8), collectStreamLimit(7, noSevens()));
    }

    public void test_primes()
    {
        assertEquals(asList(2, 3, 5, 7, 11, 13, 17, 19, 23, 29), collectStreamLimit(10, primes()));
    }

delaystream.Procedures

    public static List<Object> noSevens()
    {
        return filterStream((Integer x) -> x % 7 != 0, integersFrom(1));
    }

    public static List<Object> primes()
    {
        return sieve(integersFrom(2));
    }
    
    private static List<Object> sieve(List<Object> s)
    {
        return consStream(head(s), () -> sieve(filterStream((Integer n) -> n % (Integer)head(s) != 0, tail(s))));
    }

8 Defining Streams Implicitly

用自定义Stream(Delay)实现。

在StreamOp中增加了addStream、scale等方法，隐式定义了ones、integers、fibs等流。

delaystream.StreamOpTest

    public void test_addStream()
    {
        assertEquals(asList(4, 6), collectStream(addStream(enumInterval(1, 2), enumInterval(3, 4))));
        assertEquals(asList(), collectStream(addStream(theEmptyStream(), theEmptyStream())));
        assertEquals(asList(1, 2), collectStream(addStream(enumInterval(1, 2), theEmptyStream())));
        assertEquals(asList(3, 4), collectStream(addStream(theEmptyStream(), enumInterval(3, 4))));
        assertEquals(asList(4, 4), collectStream(addStream(enumInterval(1, 1), enumInterval(3, 4))));
        assertEquals(asList(4, 2), collectStream(addStream(enumInterval(1, 2), enumInterval(3, 3))));
        
        assertEquals(asList(3, 5, 7, 9), collectStreamLimit(4, addStream(integersFrom(1), integersFrom(2))));
    }
    
    public void test_scale()
    {
        assertEquals(asList(2, 4), collectStream(scale(2, enumInterval(1, 2))));
        assertEquals(asList(), collectStream(scale(2, theEmptyStream())));
        
        assertEquals(asList(2, 4, 6, 8), collectStreamLimit(4, scale(2, integersFrom(1))));
    }

    public void test_ones()
    {
        assertEquals(asList(1, 1, 1, 1), collectStreamLimit(4, ones())); 
    }
    
    public void test_integers()
    {
        assertEquals(asList(1, 2, 3, 4), collectStreamLimit(4, integers())); 
    }

    public void test_fibs()
    {
        assertEquals(asList(0, 1, 1, 2, 3, 5), collectStreamLimit(6, fibs(0, 1)));
        assertEquals(asList(1, 2, 3, 5, 8, 13), collectStreamLimit(6, fibs(1, 2)));
       
        assertEquals(asList(0, 1, 1, 2, 3, 5), collectStreamLimit(6, fibs()));
    }

delaystream.StreamOp

    public static List<Object> addStream(List<Object> s1, List<Object> s2)
    {
        if(isEmptyStream(s1) & isEmptyStream(s2))
        {
            return theEmptyStream();
        }
        
        if(isEmptyStream(s1))
        {
            return s2;
        }
        
        if(isEmptyStream(s2))
        {
            return s1;
        }
        
        return consStream((Integer)head(s1) + (Integer)head(s2), () -> addStream(tail(s1), tail(s2)));
    }
    
    public static List<Object> scale(int c, List<Object> s)
    {
        if(isEmptyStream(s))
        {
            return theEmptyStream();
        }
        
        return consStream(c * (Integer)head(s), () -> scale(c, tail(s)));
    }

    public static List<Object> ones()
    {
        return consStream(1, () -> ones());
    }
    
    public static List<Object> integers()
    {
        return consStream(1, () -> addStream(integers(), ones()));
    }

    public static List<Object> fibs(int n1, int n2)
    {
        return consStream(n1, () -> fibs(n2, n1 + n2));
    }
    
    public static List<Object> fibs()
    {
        return consStream(0, () -> consStream(1, () -> addStream(fibs(), tail(fibs()))));
    }

9 Integrator

用自定义Stream(Delay)实现。

因为涉及积分运算，在StreamOp中增加了浮点数相关的doubleOnes、doubles、doublesFrom、addDoubleStream、doubleScale等方法。

9.1 生成式定义

delaystream.StreamOpTest

    public void test_doubleOnes()
    {
        assertEquals(asList(1., 1., 1., 1.), collectStreamLimit(4, doubleOnes())); 
    }
    
    public void test_doubles()
    {
        assertEquals(asList(1., 2., 3., 4.), collectStreamLimit(4, doubles())); 
        assertEquals(asList(1., 2.), collectStreamLimit(2, doubles(1., 2.))); 
        assertEquals(asList(3., 4.), collectStreamLimit(2, doubles(3., 5.)));
    }
    
    public void test_doublesFrom()
    {
        List<Object> s = doublesFrom(2.);
        assertEquals(new Double(2.), nthStream(0, s));
        assertEquals(new Double(3.), nthStream(1, s));
        
        List<Object> s2 = doublesFrom(0.);
        assertEquals(asList(0., 1., 2.), collectStreamLimit(3, s2));
    }
    
    public void test_addDoubleStream()
    {
        assertEquals(asList(4., 6.), collectStream(addDoubleStream(doubles(1., 2.), doubles(3., 4.))));
        assertEquals(asList(), collectStream(addDoubleStream(theEmptyStream(), theEmptyStream())));
        assertEquals(asList(1., 2.), collectStream(addDoubleStream(doubles(1., 2.), theEmptyStream())));
        assertEquals(asList(3., 4.), collectStream(addDoubleStream(theEmptyStream(), doubles(3., 4.))));
        assertEquals(asList(4., 4.), collectStream(addDoubleStream(doubles(1., 1.), doubles(3., 4.))));
        assertEquals(asList(4., 2.), collectStream(addDoubleStream(doubles(1., 2.), doubles(3., 3.))));
        
        assertEquals(asList(3., 5., 7., 9.), collectStreamLimit(4, addDoubleStream(doublesFrom(1.), doublesFrom(2.))));
    }
    
    public void test_doubleScale()
    {
        assertEquals(asList(2, 4), collectStream(scale(2, enumInterval(1, 2))));
        assertEquals(asList(), collectStream(scale(2, theEmptyStream())));
        
        assertEquals(asList(2, 4, 6, 8), collectStreamLimit(4, scale(2, integersFrom(1))));
    }

delaystream.StreamOp

    public static List<Object> doubleOnes()
    {
        return consStream(1., () -> doubleOnes());
    }
    
    public static List<Object> doubles()
    {
        return consStream(1., () -> addDoubleStream(doubles(), doubleOnes()));
    }
    
    public static List<Object> doubles(double low, double high)
    {
        if(low > high)
        {
            return theEmptyStream();
        }
        
        return consStream(low, () -> doubles(low + 1., high));
    }
    
    public static List<Object> doublesFrom(double d)
    {
        return consStream(d, () -> doublesFrom(d + 1.));
    }
    
    public static List<Object> addDoubleStream(List<Object> s1, List<Object> s2)
    {
        if(isEmptyStream(s1) & isEmptyStream(s2))
        {
            return theEmptyStream();
        }
        
        if(isEmptyStream(s1))
        {
            return s2;
        }
        
        if(isEmptyStream(s2))
        {
            return s1;
        }
        
        return consStream((Double)head(s1) + (Double)head(s2), () -> addDoubleStream(tail(s1), tail(s2)));
    }
    
    public static List<Object> doubleScale(double c, List<Object> s)
    {
        if(isEmptyStream(s))
        {
            return theEmptyStream();
        }
        
        return consStream(c * (Double)head(s), () -> doubleScale(c, tail(s)));
    }

delaystream.ProceduresTest

    public void test_integral()
    {
        assertEquals(asList(0., 1., 2., 3., 4.), collectStreamLimit(5, integral(doubleOnes(), 0., 1.)));
    }
    
    public void test_funmaps()
    {
        assertEquals(asList(0., 1., 2., 3., 4.), collectStreamLimit(5, funmaps(x -> x, 0., 1.)));
    }

    public void test_funmaps_integral()
    {
        List<Object> idFs = funmaps(x -> x, 1., 0.001);
        List<Object> s1 = integral(idFs, 0., 0.001);
        Double actual1 = (Double)nthStream(1001, s1);
        System.out.println(actual1);
        assertTrue(Math.abs(1.5 - actual1) < 0.1);
        
        List<Object> sqFs = funmaps(x -> x * x, 1., 0.001);
        List<Object> s2 = integral(sqFs, 0., 0.001);
        Double actual2 = (Double)nthStream(1001, s2);
        System.out.println(actual2);
        assertTrue(Math.abs(2.33 - actual2) < 0.1);
        
        List<Object> sqFs2 = funmaps(x -> x * x, 0., 0.001);
        List<Object> s3 = integral(sqFs2, 0., 0.001);
        Double actual3 = (Double)nthStream(1001, s3);
        System.out.println(actual3);
        assertTrue(Math.abs(0.33 - actual3) < 0.1);
    }

delaystream.Procedures

    public static List<Object> integral(List<Object> s, double init, double dt)
    {
        return consStream(init, () -> addDoubleStream(doubleScale(dt, s), integral(s, init, dt)));
    }
    
    public static List<Object> funmaps(Function<Double, Double> func, double init, double dt)
    {
        return consStream(func.apply(init), () -> funmaps(func, init + dt, dt));
    }

9.2 隐式定义

delaystream.ProceduresTest

    public void test_integrator()
    {
        List<Object> s1 = integrator(x -> x, 1, 0.01);
        Double actual1 = (Double)nthStream(101, s1);
        System.out.println(actual1);
        assertTrue(Math.abs(1.5 - actual1) < 0.1);
        
        List<Object> s2 = integrator(x -> x * x, 1, 0.01);
        Double actual2 = (Double)nthStream(101, s2);
        System.out.println(actual2);
        assertTrue(Math.abs(2.33 - actual2) < 0.1);
        
        List<Object> s3 = integrator(x -> x * x, 0, 0.01);
        Double actual3 = (Double)nthStream(101, s3);
        System.out.println(actual3);
        assertTrue(Math.abs(0.33 - actual3) < 0.1);
    }

delaystream.Procedures

    public static List<Object> integrator(Function<Double, Double> func, double init, double dt)
    {
        List<Object> ones = doubleOnes();
        List<Object> s = mapStream(func, integral(ones, init, dt));
        return integral(s, 0, dt);
    }

9.3 Delay Integrator

步长0.001、0.01都会导致java.lang.OutOfMemoryError: GC overhead limit exceeded。所以步长定义为0.1。

delaystream.ProceduresTest

//    public void test_integralWithDelay()
//    {
//        List<Object> s = ys();
//        Double actual = (Double)nthStream(11, s);
//        System.out.println(actual);
//    }

delaystream.Procedures

    public static List<Object> integralWithDelay(Supplier<List<Object>> delayS, double init, double dt)
    {
        return consStream(init, () -> {
                                          List<Object> s = delayS.get();
                                          return addDoubleStream(doubleScale(dt, s), integral(s, init, dt));
                                      });
    }
    
    public static List<Object> ys()
    {
        return integralWithDelay(() -> dys(), 1., 0.1);
    }
    
    public static List<Object> dys()
    {
        return mapStream((Double x) -> x * x, ys());
    }

10 Sqrt

用自定义Stream(Delay)实现。

delaystream.ProceduresTest

    public void test_sqrt()
    {
        assertTrue(Math.abs(1.414 - sqrt(2, 0.001)) < 0.001);
        assertTrue(Math.abs(3. - sqrt(9, 0.001)) < 0.001);
    }

delaystream.Procedures

    public static double sqrt(double d, double tolerance)
    {
        return streamLimit(sqrtStream(d), tolerance);
    }

    private static List<Object> sqrtStream(double d)
    {
        return consStream(1.0, () -> mapStream((Double ele) -> (ele + d / ele) / 2., sqrtStream(d)));
    }
    
    private static double streamLimit(List<Object> s, double tolerance)
    {
        return streamLimit(head(s), tail(s), tolerance);
    }

    private static double streamLimit(double prev, List<Object> s, double tolerance)
    {
        double next = head(s);
        if(Math.abs(next - prev) < tolerance)
        {
            return next;
        }
        return streamLimit(next, tail(s), tolerance);
    }

11 Stream of Pairs

用自定义Stream(Delay)实现。

11.1 Stream of pairs constructed from an infinite stream

需要改进flatten的写法以处理无限流，并增加printStreamLimit()方法。

改进前的现象是，抛出StrackOverflowError。

StreamOpTest测试代码不需要修改。

delaystream.StreamOp

//    public static List<Object> flatten(List<Object> sos)
//    {
//        return accStream((List<Object> s1, List<Object> s2) -> appendStream(s1, s2), theEmptyStream(), sos);
//    }
    
    public static List<Object> flatten(List<Object> sos)
    {
        if(isEmptyStream(sos))
        {
            return theEmptyStream();
        }
        
        return flatten(head(sos), tail(sos));
    }
    
    private static List<Object> flatten(List<Object> headS, List<Object> sos)
    {
        if(isEmptyStream(headS))
        {
            return flatten(sos);
        }
        
        return consStream(head(headS), () -> flatten(tail(headS), sos));
    }

    public static void printStreamLimit(int num, List<Object> s)
    {
        if(isEmptyStream(s))
        {
            System.out.println("Done.\n");
            return;
        }
        
        if(num == 0)
        {
            System.out.println("ok.\n");
            return;
        }
        
        System.out.println(head(s).toString());
        printStreamLimit(num - 1,tail(s));
    }

delaystream.ProceduresTest

    public void test_pair()
    {
        assertEquals(asList(asList(1, 1),
                            asList(1, 2), asList(2, 2),
                            asList(1, 3), asList(2, 3), asList(3, 3)),
                     collectStreamLimit(6, pair(integersFrom(1))));
        
        printStreamLimit(10, pair(integersFrom(1)));
    }

delaystream.Procedures

    public static List<Object> pair(List<Object> s)
    {
        return flatmap((Integer j) -> mapStream((Integer i) -> asList(i, j), enumInterval(1, j)), s);
    }

11.2 Stream of pairs constructed from two infinite streams

delaystream.ProceduresTest

    public void test_pair2()
    {
        assertEquals(asList(asList(1, 1),
                            asList(1, 2), asList(2, 2),
                            asList(1, 3), asList(2, 3), asList(3, 3),
                            asList(1, 4), asList(2, 4), asList(3, 4), asList(4, 4)),
                     collectStreamLimit(10, pair(integersFrom(1), integersFrom(1))));
        
        assertEquals(asList(asList(1, 1.),
                            asList(1, 2.), asList(2, 2.),
                            asList(1, 3.), asList(2, 3.), asList(3, 3.),
                            asList(1, 4.), asList(2, 4.), asList(3, 4.), asList(4, 4.)),
                     collectStreamLimit(10, pair(integersFrom(1), doublesFrom(1.))));
    }

delaystream.Procedures

    public static List<Object> pair(List<Object> s, List<Object> t)
    {
        return pair(s, t, ele -> theEmptyStream());
    }

    private static <T> List<Object> pair(List<Object> s, List<Object> t, Function<T, List<Object>> func)
    {
        return appendStream(func.apply(head(t)), 
                            consStream(asList(head(s), head(t)), 
                                       () -> pair(tail(s), tail(t), accFunc(func, head(s)))));
    }

    private static <S, T> Function<T, List<Object>> accFunc(Function<T, List<Object>> func, S headS)
    {
        return ele -> appendStream(func.apply(ele), consStream(asList(headS, ele), () -> theEmptyStream()));
    }

11.3 All the pairs

11.3.1 non-recursive

delaystream.ProceduresTest

    public void test_allPairs()
    {
        assertEquals(asList(asList(1, 1),
                            asList(1, 2),
                            asList(2, 1),
                            asList(2, 2),
                            asList(1, 3), asList(2, 3),
                            asList(3, 1), asList(3, 2),
                            asList(3, 3),
                            asList(1, 4), asList(2, 4), asList(3, 4),
                            asList(4, 1), asList(4, 2), asList(4, 3),
                            asList(4, 4)), 
                     collectStreamLimit(16, allPairs(integersFrom(1), integersFrom(1))));
        
        assertEquals(asList(asList(1, 1.),
                            asList(1, 2.),
                            asList(2, 1.),
                            asList(2, 2.),
                            asList(1, 3.), asList(2, 3.),
                            asList(3, 1.), asList(3, 2.),
                            asList(3, 3.),
                            asList(1, 4.), asList(2, 4.), asList(3, 4.),
                            asList(4, 1.), asList(4, 2.), asList(4, 3.),
                            asList(4, 4.)), 
                     collectStreamLimit(16, allPairs(integersFrom(1), doublesFrom(1.))));
    }

delaystream.Procedures

    public static List<Object> allPairs(List<Object> s, List<Object> t)
    {
        return allPairs(s, t, eleS -> theEmptyStream(), eleT -> theEmptyStream());
    }
    
    private static <S, T> List<Object> allPairs(List<Object> s, List<Object> t, 
            Function<T, List<Object>> sFunc, Function<S, List<Object>> tFunc)
    {
        return appendStream(sFunc.apply(head(t)), 
                            appendStream(tFunc.apply(head(s)),
                                         consStream(asList(head(s), head(t)),
                                                    () -> allPairs(tail(s), tail(t), 
                                                                   accFirstFunc(sFunc, head(s)), 
                                                                   accSecondFunc(tFunc, head(t))))));
    }

    private static <S, T> Function<T, List<Object>> accFirstFunc(Function<T, List<Object>> sFunc, S headS)
    {
        return eleT -> appendStream(sFunc.apply(eleT), consStream(asList(headS, eleT), () -> theEmptyStream()));
    }
    
    private static <S, T> Function<S, List<Object>> accSecondFunc(Function<S, List<Object>> tFunc, T headT)
    {
        return eleS -> appendStream(tFunc.apply(eleS), consStream(asList(eleS, headT), () -> theEmptyStream()));
    }

11.3.2 recursive

delaystream.ProceduresTest

    public void test_reAllPairs()
    {
        assertEquals(asList(asList(1, 1), asList(1, 2), asList(2, 1), asList(1, 3),
                            asList(2, 2), asList(1, 4), asList(3, 1), asList(1, 5)), 
                     collectStreamLimit(8, reAllPairs(integersFrom(1), integersFrom(1))));
        
        assertEquals(asList(asList(1, 1.), asList(1, 2.), asList(2, 1.), asList(1, 3.),
                            asList(2, 2.), asList(1, 4.), asList(3, 1.), asList(1, 5.)), 
                     collectStreamLimit(8, reAllPairs(integersFrom(1), doublesFrom(1.))));
    }

delaystream.Procedures

    public static List<Object> reAllPairs(List<Object> s, List<Object> t)
    {
        return consStream(asList(head(s), head(t)), 
                          () -> interleave(mapStream(eleT -> asList(head(s), eleT), tail(t)),
                                           reAllPairs(tail(s), t)));
    }

    private static List<Object> interleave(List<Object> s1, List<Object> s2)
    {
        if(isEmptyStream(s1))
        {
            return s2;
        }
        
        return consStream(head(s1), () -> interleave(s2, tail(s1)));
    }

11.4 Up pairs

recursive

delaystream.ProceduresTest

    public void test_upPairs()
    {
        assertEquals(asList(asList(1, 1), asList(1, 2), asList(2, 2), asList(1, 3), 
                            asList(2, 3), asList(1, 4), asList(3, 3), asList(1, 5)), 
                     collectStreamLimit(8, upPairs(integersFrom(1), integersFrom(1))));
        
        assertEquals(asList(asList(1, 1.), asList(1, 2.), asList(2, 2.), asList(1, 3.), 
                            asList(2, 3.), asList(1, 4.), asList(3, 3.), asList(1, 5.)), 
                     collectStreamLimit(8, upPairs(integersFrom(1), doublesFrom(1.))));
    }

delaystream.Procedures

    public static List<Object> upPairs(List<Object> s, List<Object> t)
    {
        return consStream(asList(head(s), head(t)),
                          () -> interleave(mapStream(eleT -> asList(head(s), eleT), tail(t)),
                                           upPairs(tail(s), tail(t))));
    }

12 用Cesaro方法估算PI值

用自定义Stream(Delay)实现。

pi.PiEstimatorWithDelayStream

import static fayelab.sicp.stream.delaystream.StreamOp.*;

import java.util.List;
import java.util.function.BiFunction;

public class PiEstimator
{
    private static final int MAX_RANDOM_NUMER = 100000;

    private static List<Object> randomStream()
    {
        return consStream(randomNumber(), () -> randomStream());
    }
    
    private static List<Object> cesaroStream(List<Object> randomS)
    {
        return mapSuccessivePairs((Integer r1, Integer r2) -> gcd(r1, r2) == 1, randomS);
    }
    
    private static <T, U, R> List<Object> mapSuccessivePairs(BiFunction<T, U, R> func, List<Object> s)
    {
        return consStream(func.apply(head(s), head(tail(s))), () -> mapSuccessivePairs(func, tail(tail(s))));
    }
    
    private static List<Object> monteCarloStream(List<Object> s, int total, int passed)
    {
        int newPassed = (Boolean)head(s) ? passed + 1 : passed;
        int newTotal = total + 1;
        
        System.out.println("newTotal = " + newTotal + " newPassed = " + newPassed + " p = " + 1.0 * newPassed / newTotal);
        
        return consStream(1.0 * newPassed / newTotal, () -> monteCarloStream(tail(s), newTotal, newPassed));
    }
    
    private static List<Object> piStream()
    {
        return mapStream((Double p) -> doubleEquals(p, 0.0) ? 0.0 : Math.sqrt(6. / p),
                         monteCarloStream(cesaroStream(randomStream()), 0, 0));
    }
    
    public static double estimate(double tolerance)
    {
        return streamLimit(piStream(), tolerance);
    }
    
    private static int randomNumber()
    {
        return (int)(Math.random() * MAX_RANDOM_NUMER) + 1;
    }
    
    private static int gcd(int x, int y)
    {
        if(y == 0)
        {
            return x;
        }
        
        return gcd(y, x % y);
    }
    
    private static double streamLimit(List<Object> s, double tolerance)
    {
        return streamLimit(head(s), tail(s), tolerance);
    }

    private static double streamLimit(double prev, List<Object> s, double tolerance)
    {
        double next = head(s);
        
        System.out.println("next = " + next + " prev = " + prev);
        
        if(doubleEquals(next, prev, tolerance) && !doubleEquals(next, 2.449489742783178))
        {
            return next;
        }
        
        return streamLimit(next, tail(s), tolerance);
    }
    
    private static boolean doubleEquals(double d1, double d2)
    {
        return doubleEquals(d1, d2, 0.000000000000001);
    }
    
    private static boolean doubleEquals(double d1, double d2, double tolerance)
    {
        return Math.abs(d1 - d2) < tolerance;
    }
    
    public static void main(String[] args)
    {
        System.out.println("****** " + PiEstimator.estimate(0.0001));
        
//        List<Object> pis = PiEstimator.piStream();
//        System.out.println("****** 100th " + nthStream(100, pis));
//        System.out.println("****** 1000th  " + nthStream(1000, pis));
//        System.out.println("****** 10000th " + nthStream(10000, pis));
    }
}

13 用Stream Class替换List表示流

代码不列在这里了，详见fayelab.sicp.stream.delaystreamclass。跟List相比，用Stream Class可以定义流元素类型的泛型或具体类型，还是清晰一些。

14 Python版本

详见Python目录。

⚠️ **GitHub.com Fallback** ⚠️