过滤功能不偷懒

Question

为了好玩，我正在制作我自己的 Java 流库版本。这是我的 class 签名：

class Stream<T> {
  Supplier<T> head;
  Supplier<Stream<T>> tail;
  ...
}

此外，我编写了一个基本的无限流迭代器，它会根据给定的函数生成一个无限列表：

  public static <T> Stream<T> iterate(T first, Function<T, T> f) {
    return new Stream<T>(
            () -> first,
            () -> {
              T nextElem = f.apply(first);
              if (nextElem == null) {
                return generate(() -> null);
              } else {
                return iterate(nextElem, f);
              }
            }
    );
  }

函数generate是迭代的一个特例，它永远重复一个给定的元素。在上面的函数中，我生成了一个 null 的无限序列来指示流的结尾（我不认为我会在流中存储空值）。

然后我写了一个reduce函数，其中reducing函数在第二个参数上是惰性的：

  public <U> U reduce(U acc, Function<T, Function<Supplier<U>, U>> f) {
    System.out.println("REDUCE CALL");
    T elem = head.get();
    if (elem != null) {
      return f.apply(elem).apply(() -> this.tail.get().reduce(acc, f));
    } else {
      return acc;
    }
  }

在 reduce 函数的基础上，我编写了 filter 函数。

  public Stream<T> filter(Predicate<T> p) {
    System.out.println("FILTER");
    return reduce(generate(() -> null), elem -> acc -> {
      if (p.test(elem)) {
        return new Stream<>(
                () -> elem,
                () -> acc.get()
        );
      } else {
        return acc.get();
      }
    });
  }

最后，我开始使用我自己的 Stream class:

  public static void main(String[] args) {
    Stream<Integer> ilist =
            Stream
              .iterate(1, x -> x + 1)
              .filter(x -> x >= 5);
  }

但过滤器并不懒惰！从下面给出的输出来看，我认为过滤器会评估元素，直到找到与给定谓词匹配的元素。

FILTER
REDUCE CALL
REDUCE CALL
REDUCE CALL
REDUCE CALL
REDUCE CALL

我的代码有什么问题，我怎样才能让我的过滤器函数再次惰性化？

更新: 根据 Sweeper 的评论，我在没有使用 reduce 的情况下再次尝试了过滤功能。

  public Stream<T> filter2(Predicate<T> p) {
    System.out.println("FILTER2");
    T elem = head.get();
    if (elem == null) {
      return generate(() -> null);
    } else {
      if (p.test(elem)) {
        return new Stream<>(
                () -> elem,
                () -> this.tail.get().filter2(p)
        );
      } else {
        return this.tail.get().filter2(p);
      }
    }
  }

但是，这个函数也不是懒惰的。我使用 filter2 的主要功能的输出如下：

FILTER2
FILTER2
FILTER2
FILTER2
FILTER2

我该如何解决这个问题，有没有办法通过惰性 reduce 实现惰性过滤器？

致谢：本练习和上述函数的实现受到 Chiusano 和 Bjarnason 合着的 Scala 函数式编程 一书的启发。

Answer 1

在你写的没有reduce的版本中，元素存在但不满足谓词的情况不是惰性的。不像在其他情况下那样将递归调用包装在供应商 lambda 中，而是急切地获取尾巴并立即对其进行过滤。

public Stream<T> filter2(Predicate<T> p) {
    System.out.println("FILTER2");
    T elem = head.get();
    if (elem == null) {
        return generate(() -> null);
    } else {
        if (p.test(elem)) {
            return new Stream<>(
                () -> elem,
                () -> this.tail.get().filter2(p)
            );
        } else {
            return this.tail.get().filter2(p); // <- not lazy!
        }
    }
}

您需要一种创建流的方法，这样可以推迟到以后再决定它是否为空。

public class Stream<T> {
    // private constructor(s)

    public static <T> Stream<T> empty() { /* ... */ }

    public static <T> Stream<T> cons(Supplier<T> head, Supplier<Stream<T> tail) { /* ... */ }

    public static <T> Stream<T> lazy(Supplier<Stream<T>> stream) { /* ... */ }

    public Stream<T> filter(Predicate<T> p) {
        if ( /* this stream is empty */ ) {
            return Stream.empty();
        } else if ( /* head element satisfies predicate */ ) {
            // lazily filter tail, cons head element
        } else {
            return Stream.lazy(() -> this.tail.get().filter(p));
        }
    }
}

类似的东西。

过滤功能不偷懒

Filter Function Not Lazy

java

lambda

functional-programming

lazy-evaluation

java-8