过滤函数不是惰性的
过滤函数不是惰性的
提问于 2018-06-09 14:00:21
为了好玩，我正在制作我自己的Java流库版本。下面是我的类签名：
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是iterate的一个特例，它永远重复给定的元素。在上面的函数中，我生成了一个无限的null序列来表示流的结束(我不认为我会在流中存储null值)。
然后我编写了一个reduce函数，其中reduce函数的第二个参数是惰性的：
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类：
public static void main(String[] args) {
Stream<Integer> ilist =
Stream
.iterate(1, x -> x + 1)
.filter(x -> x >= 5);
}但是过滤器并不是懒惰的！从下面给出的输出中，我认为filter会对元素进行求值，直到找到与给定谓词匹配的元素。
FILTER
REDUCE CALL
REDUCE CALL
REDUCE CALL
REDUCE CALL
REDUCE CALL我的代码出了什么问题，我怎样才能让我的过滤器函数再次变得懒惰？
更新：基于清道夫的评论，我在没有使用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我如何解决这个问题，有没有办法通过惰性缩减来实现惰性过滤器？
Acknowledgements：本练习和上述函数的实现灵感来自于Chiusano和Bjarnason合著的《在Scala中进行函数式编程》一书。
回答 1
Stack Overflow用户
回答已采纳
发布于 2018-06-09 17:09:44
在您编写的不带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));
}
}
}一些类似的东西。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/50771373
复制相关文章
相似问题
腾讯云开发者
