3 ms·

Does anyone else 100% disagree with the claim that this "lambda version is more concise and expresses its intent effectively"? public static List generate(in

Does anyone else 100% disagree with the claim that this "lambda version is more concise and expresses its intent effectively"? public static List generate(int series) { return Stream.iterate(new int[]{0, 1}, s -> new int[]{s[1], s[0] + s[1]}) .limit(series) .map(n -> n[0]) .collect(toList()); } as opposed to this: public int fib(int n) { int x = 0, y = 1, z = 1; for (int i = 0; i < n; i++) { x = y; y = z; z = x + y; } return x; }

seanmcdirmid 9y ago
Ya, I noticed that also. Actually, the basic recursive version would be functional and concise, why did they go with the functional origami version instead?
- hardlianotion 9y ago
  I think the point is with the basic tail recursive copy it is easy to blow the call stack with the number of function calls needed.
bad_user 9y ago
Yes, also the author is wrong — in FP the direct equivalent of a loop are tail recursive functions (i.e. you can take any loop and transform it into a tail recursion) and not "list processing". Here's Scala: def fib(n: Int, a: Int, b: Int): Int = { if (n > 0) fib(n - 1, b, a + b) else a } Unfortunately Java cannot express self tail recursive functions and Scala too can't express mutual tail recursive functions, as that would require runtime support. But you know what? That mutable loop is totally fine, because any mutation it has is encapsulated, the function itself being pure.
- epai 9y ago
  Just to expand a little on the "you can take any loop and transform it into a tail recursion" (because I think it's cool), here's an example: Python iterative solution 1. def fib(n): 2. i, curr, next = 0, 0, 1 3. while i < n: 4. i += 1 5. curr, next = next, curr + next 6. return curr Python tail-recursive solution* 1. def fib(n): 2. def fib_tail(i, curr, next): #1 3. if i >= n: #2 4. return curr #3 5. return fib_tail(i+1, next, curr+next) #4 6. return fib_tail(0, 0, 1) Some explanation of the 1-1 conversion process: #1. We need a helper function, `fib_tail` to keep track of the variables we update in the while loop. (lines 4-5 in iterative) #2-3. Return `curr` when the opposite of the while condition is met. (lines 3,6 in iterative) #4. Recursively call `fib_tail`, using same update logic as while loop body when passing arguments. (line 5 in iterative) #5. Call helper function with initial values for the additional variables (line 1 in iterative) * We're going to pretend that Python supports tail recursion. It doesn't, but I figure more people are familiar with python; think of it more as pseudocode for instruction. You could easily implement the above in something like Scheme
MikkoFinell 9y ago
Yeah at that point I had to scroll up and check if the article was posted on April 1, but apparently it's not a joke.
tytytytytytytyt 9y ago
It's not even an apples to apples comparison. One of them returns a list, one doesn't, and one of them has a descriptive name, the other not so much.
yomritoyj 9y ago
Syntax matters. What I really like about Haskell is how much care has been given to the syntax to make functional idioms easy to read and write. One can just say, fib = 0:1:zipWith (+) fib (drop 1 fib) [I know that `drop 1` is just `tail`, but this one makes the intent clearer for those who may not know Haskell].
- Zpalmtree 9y ago
  Technically drop 1 isn't just tail, but it doesn't matter in this example. Tail will error on an empty list.
- ubernostrum 9y ago
  You can often get close to Haskell-y implementations in Python with help from the itertools module. There are a couple "Haskell style" Fibonacci generators with itertools floating around in blog posts, I'm sure, and I've used itertools to write all sorts of things in a pretty succinct manner.
hodl 9y ago
Its all a matter of familiarity. Once you've learned FP and practiced a bit, both listings are equally easy to grok.
kangoo1707 9y ago
The two versions that you give do not return the same thing. the FP one returns a list, while the imperative one returns a number
- archgoon 9y ago
  Yes, but that's another issue with the article. Modifying the first to return a list though is trivial, you declare an List at the beginning and then you append in the for loop.
barrkel 9y ago
I don't 100% disagree. The reason is that the lambda approach is much more declarative; it's a composition of parameterized parts using a standardized interface. That means it can easily be parallelized, for example, and if Java were a little more introspectable, it might even be distributed, restartable or even converted into code in a different system, like LINQ targets SQL. Toy examples are toys; they're usually easily broken, since the simplicity required for pedagogy leaves a poor ratio of problem difficulty to solution power. I wouldn't write the example code as a stream either, but I much prefer the approach when the complexity level increases only slightly.
yiransheng 9y ago
In this case, I think Java's lack of tuples adds quite a bit of syntactic noise, a similar version in rust (another language with method chaining based iterators): let generated: Vec<i32> = itertools::iterate((0, 1), |&(a, b)| (b, a + b)) .map(|s| s.0) .take(10) .collect(); Arguably, this is closer to the matrix form of Fibonacci series[1]. In addition, the same code structure can generalize to any series with a recursive definition in the form of: a_n = f(a_{n-1}, a_{n-2}, ..., a_{n-k}) - which by some standard expresses intent better. Especially, for some k, the mental overhead of a loop version is too much to bare :) [1] https://wikimedia.org/api/rest_v1/media/math/render/svg/c795926ab8f80e6207800de0451de69a69b8f641 https://wikimedia.org/api/rest_v1/media/math/render/svg/c795...

seanmcdirmid 9y ago

Ya, I noticed that also. Actually, the basic recursive version would be functional and concise, why did they go with the functional origami version instead?

hardlianotion 9y ago
I think the point is with the basic tail recursive copy it is easy to blow the call stack with the number of function calls needed.

bad_user 9y ago

Yes, also the author is wrong — in FP the direct equivalent of a loop are tail recursive functions (i.e. you can take any loop and transform it into a tail recursion) and not "list processing". Here's Scala: def fib(n: Int, a: Int, b: Int): Int = { if (n > 0) fib(n - 1, b, a + b) else a } Unfortunately Java cannot express self tail recursive functions and Scala too can't express mutual tail recursive functions, as that would require runtime support. But you know what? That mutable loop is totally fine, because any mutation it has is encapsulated, the function itself being pure.

epai 9y ago
Just to expand a little on the "you can take any loop and transform it into a tail recursion" (because I think it's cool), here's an example: Python iterative solution 1. def fib(n): 2. i, curr, next = 0, 0, 1 3. while i < n: 4. i += 1 5. curr, next = next, curr + next 6. return curr Python tail-recursive solution* 1. def fib(n): 2. def fib_tail(i, curr, next): #1 3. if i >= n: #2 4. return curr #3 5. return fib_tail(i+1, next, curr+next) #4 6. return fib_tail(0, 0, 1) Some explanation of the 1-1 conversion process: #1. We need a helper function, `fib_tail` to keep track of the variables we update in the while loop. (lines 4-5 in iterative) #2-3. Return `curr` when the opposite of the while condition is met. (lines 3,6 in iterative) #4. Recursively call `fib_tail`, using same update logic as while loop body when passing arguments. (line 5 in iterative) #5. Call helper function with initial values for the additional variables (line 1 in iterative) * We're going to pretend that Python supports tail recursion. It doesn't, but I figure more people are familiar with python; think of it more as pseudocode for instruction. You could easily implement the above in something like Scheme

MikkoFinell 9y ago

Yeah at that point I had to scroll up and check if the article was posted on April 1, but apparently it's not a joke.

tytytytytytytyt 9y ago

It's not even an apples to apples comparison. One of them returns a list, one doesn't, and one of them has a descriptive name, the other not so much.

yomritoyj 9y ago

Syntax matters. What I really like about Haskell is how much care has been given to the syntax to make functional idioms easy to read and write. One can just say, fib = 0:1:zipWith (+) fib (drop 1 fib) [I know that `drop 1` is just `tail`, but this one makes the intent clearer for those who may not know Haskell].

Zpalmtree 9y ago
Technically drop 1 isn't just tail, but it doesn't matter in this example. Tail will error on an empty list.
ubernostrum 9y ago
You can often get close to Haskell-y implementations in Python with help from the itertools module. There are a couple "Haskell style" Fibonacci generators with itertools floating around in blog posts, I'm sure, and I've used itertools to write all sorts of things in a pretty succinct manner.

hodl 9y ago

Its all a matter of familiarity. Once you've learned FP and practiced a bit, both listings are equally easy to grok.

kangoo1707 9y ago

The two versions that you give do not return the same thing. the FP one returns a list, while the imperative one returns a number

archgoon 9y ago
Yes, but that's another issue with the article. Modifying the first to return a list though is trivial, you declare an List at the beginning and then you append in the for loop.

barrkel 9y ago

I don't 100% disagree. The reason is that the lambda approach is much more declarative; it's a composition of parameterized parts using a standardized interface. That means it can easily be parallelized, for example, and if Java were a little more introspectable, it might even be distributed, restartable or even converted into code in a different system, like LINQ targets SQL. Toy examples are toys; they're usually easily broken, since the simplicity required for pedagogy leaves a poor ratio of problem difficulty to solution power. I wouldn't write the example code as a stream either, but I much prefer the approach when the complexity level increases only slightly.

yiransheng 9y ago

In this case, I think Java's lack of tuples adds quite a bit of syntactic noise, a similar version in rust (another language with method chaining based iterators): let generated: Vec<i32> = itertools::iterate((0, 1), |&(a, b)| (b, a + b)) .map(|s| s.0) .take(10) .collect(); Arguably, this is closer to the matrix form of Fibonacci series[1]. In addition, the same code structure can generalize to any series with a recursive definition in the form of: a_n = f(a_{n-1}, a_{n-2}, ..., a_{n-k}) - which by some standard expresses intent better. Especially, for some k, the mental overhead of a loop version is too much to bare :) [1] https://wikimedia.org/api/rest_v1/media/math/render/svg/c795926ab8f80e6207800de0451de69a69b8f641 https://wikimedia.org/api/rest_v1/media/math/render/svg/c795...