Exercise 7 - InfiniteList

What is InfiniteList

In Lab 06, there is a very good explanation about Infinite List, go back to take a read for better understanding!

Main methods explanation

1

Fields

Our InfiniteList implementation has three fields

private final Lazy<Maybe<T>> head;
private final Lazy<InfiniteList<T>> tail;
private static InfiniteList<?> SENTINEL = new Sentinel();

2

generate(Producer producer)

Creates an infinite list where each element is generated on demand using a Producer.

Implementation

It wraps each element in a Maybe using Maybe.some(), and lazily generates the rest using recursion.

public static <T> InfiniteList<T> generate(Producer<T> producer) {
  return new InfiniteList<>(
      Lazy.of(() -> Maybe.some(producer.produce())),
      Lazy.of(() -> generate(producer)));
}

Here, we assume that the producer will always produce a valid value. So, we wrap it into a Maybe.some instead of using Maybe.of().

3

iterate(T seed, Transformer<T, T> next)

Creates an infinite list starting from a seed, where each next element is computed by applying a transformer function to the previous one.

Implementation

Each new element is lazily created from the transformation of the seed.

public static <T> InfiniteList<T> iterate(T seed, Transformer<T, T> next) {
  return new InfiniteList<>(
      Lazy.of(Maybe.some(seed)),
      Lazy.of(() -> iterate(next.transform(seed), next)));
}

4

head()

Returns the first non-filtered (i.e. Maybe.some) element of the list.

Implementation

If the current head is empty (Maybe.none), it moves to the next one via tail.

public T head() {
  Maybe<T> h = this.head.get();
  return h.orElseGet(() -> this.tail.get().head());
}

5

tail()

Returns the next node in the list, skipping any Maybe.none() elements (which were filtered out).

Implementation

If current head is present, return tail; otherwise skip ahead recursively.

public InfiniteList<T> tail() {
  Maybe<T> h = this.head.get();
  return h.map(x -> this.tail.get()).orElseGet(() -> this.tail.get().tail());
}

Condition here is head() is present or not, if it is, we need to use map to map it to the tail we want.

6

map(Transformer<? super T, ? extends R> mapper)

Transforms every element in the list using a provided function.

Implementation

Applies the map to both the head and tail lazily.

public <R> InfiniteList<R> map(Transformer<? super T, ? extends R> mapper) {
  return new InfiniteList<>(
    this.head.map(x -> x.map(mapper)),
    this.tail.map(x -> x.map(mapper)));
}

7

filter(BooleanCondition<? super T> predicate)

Filters elements based on a condition; filtered elements are wrapped as Maybe.none().

Implementation

Applies the predicate to the head, and recursively filters the tail.

public InfiniteList<T> filter(BooleanCondition<? super T> predicate) {
  return new InfiniteList<>(
      Lazy.of(() -> this.head.get().filter(predicate)),
      Lazy.of(() -> this.tail.get().filter(predicate)));
}

The following code won't work because the Lazy::filter will return a Lazy<Boolean>, that doesn't fit into the fields of our InfiniteList.

public InfiniteList<T> filter(BooleanCondition<? super T> predicate) {
  return new InfiniteList<>(
      this.head.filter(predicate),
      this.tail.filter(predicate));
}

8

sentinel()

Returns a special end-of-list marker (Sentinel object) that represents the end of a (limited) list.

Implementation

Casts the shared SENTINEL object to the desired type.

public static <T> InfiniteList<T> sentinel() {
  @SuppressWarnings("unchecked")
  InfiniteList<T> sentinel = (InfiniteList<T>) SENTINEL;
  return sentinel;
}

9

limit(long n)

Limits the list to n number of actual elements (ignoring filtered ones).

Implementation

Each time it finds a non-filtered element, it decrements n. If n is zero or less, it returns a sentinel.

public InfiniteList<T> limit(long n) {
  if (n <= 0) {
    return InfiniteList.sentinel();
  }
  return new InfiniteList<>(
      this.head,
      Lazy.of(
          () ->
              this.head
                  .get()
                  .map(h -> this.tail.get().limit(n - 1))
                  .orElseGet(() -> this.tail.get().limit(n))));
}

10

takeWhile(BooleanCondition<? super T> predicate)

The most challenging part in this exercise!!!

Keeps taking elements while they satisfy a condition. Stops at first failure.

Implementation

Normal Approach

1. What conditions do we need to check for the head?

   1. Whether the head exists,

   2. Whether the head passes the predicate

Lazy<Boolean> headExists = this.head.filter(
    head -> !head.equals(Maybe.none()));
Lazy<Boolean> passTest = this.head.filter(
    head -> !head.filter(predicate).equals(Maybe.none()));

1. Under what conditions do we keep the head?

   1. The head does not exist, or

   2. The head passes the test

2. How to combine the conditions Lazily, Use Lazy::combine

Lazy<Boolean> shouldKeepHead = headExists.combine(passTest,
    (b1, b2) -> !b1 || b2);

Final Code

public InfiniteList<T> takeWhile(BooleanCondition<? super T> p) {
    Lazy<Boolean> headExists = this.head.filter(
            head -> !head.equals(Maybe.none()));
    Lazy<Boolean> passTest = this.head.filter(
            head -> !head.filter(p).equals(Maybe.none()));
    Lazy<Boolean> shouldKeepHead = headExists.combine(passTest,
            (b1, b2) -> !b1 || b2);
    // Keep the head if it doesn't exist or passes the test.
    return new InfiniteList<>(
            shouldKeepHead.map(bool -> bool
                    ? this.head.get()
                    : Maybe.none()),
            shouldKeepHead.map(bool -> bool
                    ? this.tail.map(list -> list.takeWhile(p)).get()
                    : InfiniteList.sentinel())
    );
}

One-liner Approach

11

isSentinel()

Tells whether the list is the sentinel.

Implementation

Default returns false. Sentinel overrides this to return true.

public boolean isSentinel() {
  return false;
}

12

reduce(U identity, Combiner<U, ? super T, U> accumulator)

Performs a reduction/fold operation over the list (like summing up or combining values).

Implementation

1. Iteratively: Use the idea of traversing through the list

2. Recursively: Skips Maybe.none(), combines head with tail.reduce() result recursively.

Iterative

public <R> R reduce(R identity, Combiner<? super R, ? super T, ? extends R> accumulator) {
    R sum = identity;
    InfiniteList<T> currList = this;
    while (!currList.isSentinel()) {
        sum = currList.head.get()
                .map(h -> accumulator.combine(sum, h))
                .orElse(sum);
        currList = currList.tail.get();
    }
    return sum;
}

Recursive

13

count()

Counts how many non-filtered elements are in the list (before sentinel).

Implementation

Uses reduce with accumulator that counts.

public long count() {
  return this.reduce(0, (x, y) -> x + 1);
}

14

toList()

Collects all non-filtered elements into a Java List<T> until sentinel is reached.

Implementation

Iterates through the list, checks if head is not Maybe.none, and adds to list.

public List<T> toList() {
  List<T> list = new ArrayList<>();
  InfiniteList<T> currList = this;
  while (!currList.isSentinel()) {
    if (!currList.head.get().equals(Maybe.none())) {
      list.add(currList.head());
    }
    currList = currList.tail.get();
  }
  return list;
}

15

Traverse through the Infinite List

There is no explicit indexing in InfiniteList, so we need to traverse the list by shrinking the tail.

public void forEach(Consumer<? super T> action) {
    InfiniteList<T> currList = this;
    while (!currList.isSentinel()) {
        // Consume the head
        currList.head.get().ifPresent(action); // Do the operation
        // Shrink the sublist
        currList = currList.tail.get();
    }
}