Pierre-Yves Saumont

Author
Rancher
+ Follow
since Oct 30, 2015
Cows and Likes
Cows
Total received
31
In last 30 days
0
Total given
0
Likes
Total received
39
Received in last 30 days
0
Total given
1
Given in last 30 days
0
Forums and Threads
Scavenger Hunt
expand Rancher Scavenger Hunt
expand Ranch Hand Scavenger Hunt
expand Greenhorn Scavenger Hunt

Recent posts by Pierre-Yves Saumont

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:

3 months ago
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.
7 months ago
What you get is the correct result given the fact that negative numbers are represented in Two's complement:



What result do you want to get?
10 months ago
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?  )
10 months ago
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.

10 months ago
@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:



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.


10 months ago
@Sean Fibonacci in Kotlin:

10 months ago
@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.)
10 months ago
@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:

10 months ago
@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.
10 months ago
@Piet Yes, this effect may be observed with some recursive calls. But it will not work for really high values.


10 months ago
By the way, I fixed a bug in my code. (I was not using the map!)
10 months ago
Yes, I think I understand that, but I can't reproduce it. Whatever value I use for input, it works except for the StackOverflow problem.
10 months ago
Not sure what the question is (I can't reproduce the ConcurrentModificationException), but it will not work anyway since Java recursion is extremely limited. Using corecursion through TCE is not possible neither, but it is possible with Stream (and of course with a simple loop!). Here is a quick and dirty working corecursive version using Stream:

10 months ago
If you added an ActionListener parameter to the Event constructor, and you write:



the reason why it does not compile is that the type of the client parameter is ActionEvent, because the interface is:



So you should change the parameter name into:



Now you see that you can only call methods of the ActionEvent class. clickMenuItem is not one of them.

You might also see how difficult it is to help you if you don't post the code.
10 months ago