Функция фильтра не ленивая - PullRequest
Новая
       24

Функция фильтра не ленивая

0 голосов
/ 09 июня 2018

Я делаю свою собственную версию библиотеки Java Stream для развлечения.Вот моя подпись класса: 

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, чтобы указать конец потока (я не думаю, что буду хранить нулевые значения в потоке).

Затем я написалфункция сокращения, где функция сокращения ленива по второму аргументу: 

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

Основываясь на функции сокращения, я написал функцию фильтра. 

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

Как это исправить, и есть ли способ реализовать ленивый фильтр через ленивое уменьшение?

Благодарности : Это упражнение и реализация вышеуказанных функций были вдохновлены книгой Кьюзано и Бьярнасона Функциональное программирование в Scala .

1 Ответ

0 голосов
/ 09 июня 2018

В версии, которую вы написали без 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); // <- 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));
        }
    }
}

Что-то в этом роде.

...