Pierre-Yves Saumont

A stream is actually a generator. It generates a series of data. For this, it can use:

- a collection. Each step will generate the next element By reading it from the collection until there is no more element.

- a function of the position in the stream. For example, a random number generator. Generally, however, the generator is not a seen as a function. Instead, it memorizes its state, so it does not actually take the position as an argument.

- a function of the previous element. In such a case, it needs a seed In addition to the function.

Java streams often use a collection to generate data, which is why many programmers see them as “lazy” collections.

Laziness is essential to streams, which allows composing operations without executing them. It also allows working with infinite streams.

Basically, streams are not different from loopa generating values. It is in fact the functional equivalent of a loop generating a value on each iteration. The main benefit is that there is an agreed upon idiom to compose streams with operations, instead of manually composing loops an operations.

Saying that streams can only be used once makes no more sense than saying that a loop can only be executed once.

Java streams add parallelism, but this is not something specific to streams. Or maybe, they were called “streams“ in order to allow for this specificity. The correct name is “sequence”.

You're right. It's a very bad name  

Collecting strings by their length would not be a simplification. What I should have done is grouping strings by length AND set of characters (and not CharSet!). In fact, this might not be enough,  because "aabc" would then be equals to "abbc".  If true anagrams are to be considered, we can use something like:

public class SameSequenceString {  public static void main(String[] args) {    List<String> words = new ArrayList<>(Arrays.asList("the", "act", "cat", "is", "bats", "tabs", "tac", "aabc", "abbc", "abca"));    Map<Map<Character, Integer>, List<String>> map = words.stream().collect(Collectors.groupingBy(SameSequenceString::getCharMap));    System.out.println(map);  }  static Map<Character, Integer> getCharMap(String s) {    Map<Character, Integer> result = new HashMap<>();    for (int i = 0; i < s.length(); i++) {      char ch = s.charAt(i);      if (result.containsKey(ch)) {        result.replace(ch, result.get(ch) + 1);      } else {        result.put(ch, 1);      }    }    return result;  } }

Here is what I would do:

public class SameSequenceString {  public static void main(String[] args) {    List<String> words = new ArrayList<>(Arrays.asList("the", "act", "cat", "is", "bats", "tabs", "tac"));    Map<Set<Character>, List<String>> map = words.stream().collect(Collectors.groupingBy(SameSequenceString::getCharset));    System.out.println(map);  }  static Set<Character> getCharset(String s) {    Set<Character> result = new TreeSet<>();    for (int i = 0; i < s.length(); i++) {      result.add(s.charAt(i));    }    return result;  } }

(You can devise a better implementation of the getCharset method!)

Hi,

Why not write a program to do the job, and then simply call this program with the variable arguments? Here is an example. The Consumer<String> process is your actual program. The rest is just testing environment:

public static void main(String... args) {    HashMap<String, String> hashmap = new HashMap<>();    hashmap.put("PartLinkType1", null);    hashmap.put("PartLinkType2", "");    hashmap.put("PartLinkType3", "consumed");    hashmap.put("PartLinkType4", "not consumed");    Consumer<String> process = key -> {        if(hashmap.containsKey(key)) {            String value = hashmap.get(key);            if(value == null || value.isEmpty() || value.equals("consumed"))                hashmap.put(key, "USE");        }    };    process.accept("PartLinkType0");    process.accept("PartLinkType1");    process.accept("PartLinkType2");    process.accept("PartLinkType3");    process.accept("PartLinkType4");    System.out.println(hashmap); }

Hi Marco,

Yes, it is because although the version using two accumulators is tail recursive, Java does not implement TCE (Tail Call Elimination). So to use recursion in Java, you have the following solutions (some may be combined):

- Ensure that the number of steps will be low. This can be the result of some business condition. It could theoretically blow the stack, but you believe it won't happen with normal data.

- Use recursion for cases that can't blow the stack. For example on a balanced binary tree. As the number of objects will be equal to 2 at the power of the recursion depth (something like 2^ 3000), it'll blow the heap long before it exhausts the stack.

- Configure a larger stack. But this is a waste of space in most cases, and anyway, you can go very far in this direction.

- Use the trampoline implementation and tail recursion as I explained. But some recursive computations may not be replaced with tail recursive one.

- Use a language that implements TCO/TCE. This does not mean you have to switch to another language. You could put you tail recursive functions in a library written in Scala and call it from your Java code. Or (much) better, you can write your recursive code in Kotlin. This is not to say that Kotlin is better than Scala, but Kotlin code may be mixed with Java code in the same module. Using IntelliJ for editing and Gradle for Building, you can have Kotlin source files along with Java files in your project. Using Kotlin that way is no different from using any library (besides the fact that you have to learn a different syntax).

- Apply recursion to lazily evaluated collections. There is a strong relationship between the trampoline implementation and laziness. The trampoline is, in fact, a lazy computation. The trampoline can't be used for right-folding a list. However, under some conditions, a lazy-list, may be right-folded without any problem as I described in chapter 9 of my book due to the fact that no actual computation occurs. It will still blow the stack if the full lazy list is eventually evaluated. But often, it will not be the case because the number of elements will have been reduced before the data is evaluated.

What you get is the correct result given the fact that negative numbers are represented in Two's complement:

+1 = 00000 .... 001 -2 = 11111 .... 110

What result do you want to get?

Very good idea. In a previous example, I had implemented a system consisting of starting from the highest value present in the cache in case the needed value was not found, but it  would not work with a WeakHashMap. (Or should we implement a WeakTreeMap?   )

Here is an example of a very simple memoized recursive Fibonacci function. It works without any loop (not counting the loop in the main method, of course) for input values up to 100_000_000, without causing stack overflow nor heap overflow. It is very easy to alter to make it work for any long value (since this will, in any case, be limited to the maximum long value in Java).

It is not the fastest way to compute Fibonacci numbers (corecursion is not fast!). Only an example of handling recursion in a stack safe manner. Note that a maximum depth of 10_000 might not work for you. In such case, just use a lower value. Using 3_000 should work in all cases and allow calling the function with values up to 9_000_000. Also note that the fib(0 ) = 1. This is consistent with the definition, as the first Fibonacci number is 1.

import java.math.BigInteger; import java.util.Map; import java.util.Objects; import java.util.Scanner; import java.util.WeakHashMap; public class CorecursiveMemoizedFibonacci {    private static long MAX_DEPTH = 10_000;    private static Map<Long, Pair> cache = new WeakHashMap<>();    private static Pair fib(long n) {        return cache.computeIfAbsent(n, (Long i) -> {            long q = n / MAX_DEPTH;            long r = n % MAX_DEPTH;            Pair p = fib1(r, new Pair(BigInteger.ZERO, BigInteger.ONE));            return fib2(q, p);        });    }    private static Pair fib2(long i, Pair p) {        if (i == 0) return p;        return fib2(i - 1, fib1(MAX_DEPTH, p));    }    private static Pair fib1(long i, Pair p) {        if (i == 0) return p;        return fib1(i - 1, p.successor());    }    public static void main(String... args) {        Scanner inScan = new Scanner(System.in);        long input;        while ((input = inScan.nextLong()) >= 0) {            System.out.println(String.format("fib(%s) = %s", input, fib(input)));        }    }    private static class Pair {        final BigInteger first;        final BigInteger second;        Pair(BigInteger first, BigInteger second) {            this.first = first;            this.second = second;        }        Pair successor() {            return new Pair(second, first.add(second));        }        @Override        public String toString() {            return second.toString();        }        @Override        public boolean equals(Object o) {            if (this == o) return true;            if (o == null || getClass() != o.getClass()) return false;            Pair pair = (Pair) o;            return Objects.equals(second, pair.second);        }        @Override        public int hashCode() {            return Objects.hash(second);        }    } }

@Piet: Your solution does not really consist in building up the cache slowly, but in precomputing the cache in increments of 1000 elements, which allows using recursion inside each increment. As Java is able to handle a few thousand recursion steps with the default stack size, you could use a value higher than 1000.

Stream.foEach is actually a loop. You don't need to display the precomputed values, so you could simply write:

   public void computeAndShowNumbers() {        LongStream.rangeClosed(0, 33)                .map(i -> 3000 * i)                .forEach(i -> fib(i));        Scanner inScan = new Scanner(System.in);        long input;        while ((input = inScan.nextLong()) >= 0) {            System.out.printf("fib(%d) = %d%n", input, fib(input));        }    }

These parameters allow for relatively fast precomputation and a function working up to n = 34 * 3000, so you can, for example, compute fib(100_000).

However, it is still limited. You can't go any further because you will be out of memory. Memoized functions should generally use some way of invalidating cache entries in order to recover memory space when necessary.

@Sean Fibonacci in Kotlin:

fun main(args: Array<String>) {    (0 .. 1000).forEach { println(fibo(it)) }    println(fibo(100_000)) } fun fibo(n: Int) = when (n) {    0 -> BigInteger.ZERO    else -> generateSequence(Pair(BigInteger.ZERO, BigInteger.ONE))            { Pair(it.second, it.first + it.second)}.take(n).last().second }

@Piet  The cost is not very high but the benefit is null.  Of course, here you have to populate the map with three values. But this could be encapsulated in a FibCache class. So the only cost would be to get the initial FibCache and store it between successive calls. What are the benefits? In fact, there are none because either you share the cache, allowing other threads to benefit from the already computed values, but requiring synchronization of the cache, or you don't share the cache and you get the same result as when using a mutable map and not sharing the AbsentFibonacciDemo instance.

It is a common mistake to think that using immutable data structures makes sharing mutable state safer or easier. Immutable data structures prevent unintentional sharing of mutable state. This is fine when you don't need to share state. It makes sure you don't accidentally share mutable state. But it make sharing mutable state much more difficult. One solution, although not a functional one, is to use an actor framework which encapsulates access serialization and safe state mutation. It is not functional, but it fits nicely with functional programming. (This is chapter 14 of my book.)

@Sean Using an immutable map, you would have to store it somewhere, which means a mutable reference to a map. Or you can pass the map along with the number, and get back a map. Then you can extract the value from the map and ask for a new value passing the map along.

This would either mean that your successive calls are chained, or that they are made from a non functional program. Here his an example where the program is functional (although it is a simulation with a mutable map, but it would work just the same with an immutable one). Only the user (here the main method) is not functional:

import java.math.BigInteger; import java.util.HashMap; import java.util.Map; import java.util.Scanner; import java.util.stream.Stream; public class AbsentFibonacciDemo {  private Map<Long, Pair> compute(long i, Map<Long, Pair> cache) {    cache.computeIfAbsent(i, (Long n) -> {      Pair pmax =  cache.get(-1L);      long max = pmax.n;      Pair result = Stream.iterate(pmax, p -> {        Pair p2 = new Pair(p.n + 1, p.second, p.first.add(p.second));        cache.put(p2.n, p2);        return p2;      }).skip(i - max).findAny().get();      cache.put(-1L, result);      return result;    });    return cache;  }  static class Pair {    final long n;    final BigInteger first;    final BigInteger second;    Pair(long n, BigInteger first, BigInteger second) {      this.n = n;      this.first = first;      this.second = second;    }  }  static class Result {    final BigInteger result;    final  Map<Long, Pair> memoMap;    Result(BigInteger result, Map<Long, Pair> memoMap) {      this.result = result;      this.memoMap = memoMap;    }  }  public static void main(String... args) {    Scanner inScan = new Scanner(System.in);    long input;    AbsentFibonacciDemo fib = new AbsentFibonacciDemo();    Map<Long, Pair> cache = new HashMap<>();    cache.put(-1L, new Pair(1, BigInteger.ZERO, BigInteger.ONE));    cache.put(0L, new Pair(0, BigInteger.ZERO, BigInteger.ZERO));    cache.put(1L, new Pair(1, BigInteger.ZERO, BigInteger.ONE));    while ((input = inScan.nextLong()) >= 0) {      cache = fib.compute(input, cache);      System.out.printf("fib(%d) = %d%n", input, cache.get(input).second);    }  } }

@Piet Sorry, I did not read the code fully. You example is no longer recursive. Using forEach is like using a loop. I was thinking of the recursive example, if you ask for values incremented by one, the StackOverflowException may occur much later.

@Piet Yes, this effect may be observed with some recursive calls. But it will not work for really high values.

By the way, I fixed a bug in my code. (I was not using the map!)