3 ms·

Not necessarily. For an easy counter example, build a Sierpiński triangle. Easy to unit test. Easier to build using imperative code than functional. (This g

by taeric 3y ago

Not necessarily. For an easy counter example, build a Sierpiński triangle. Easy to unit test. Easier to build using imperative code than functional. (This goes for a ton of fractals, honestly.)

PaulHoule 3y ago
It burns me up that Fibonacci numbers are used so frequently as an example of functional programming because it is a clear case of malpractice, particularly because it performs terribly without memoization. Even in the 1980s CS profs were trying to tell us how BASIC sucks but efficient Fibonacci is so easy to code up in BASIC. (I'd really be impressed with a system that could figure out the closed form based on the definition.) How easy it is to draw fractals depends on your tools. If you have turtle graphics with affine transformations (rotation and scaling) it is so easy to write simple recursive programs to draw space filling curves and such.
- taeric 3y ago
  Change for a dollar is another fun one there. Closed form is mind bending, and I don't think we have built a system that can derive that.
- dragonwriter 3y ago
  > It burns me up that Fibonacci numbers are used so frequently as an example of functional programming because it is a clear case of malpractice, particularly because it performs terribly without memoization It's used as an example of basic recursive programming largely because its an example that can be returned to with memoization. That there is a better way to do it that can be shown later is a reason for selecting early examples in a curriculum.
- JoelMcCracken 3y ago
  Or you can write the tail-recursive version which starts from 1 and builds to n; no need to memoize.
- toast0 3y ago
  I don't see why you can't write the closed form in a functional language as well. This only works for 1 =< N =< 70, for N >= 71 the approximation of Sqrt5 isn't good enough; you need to do more symbolic math so you can eliminate that term. -module('fib'). -export([go/1]). go(N) when N < 1 -> throw(badarg); go(N) -> Sqrt5 = math:sqrt(5), round(1.0 / Sqrt5 * math:pow((1 + Sqrt5) / 2.0, N) - 1.0 / Sqrt5 * math:pow((1 - Sqrt5) / 2.0, N)). rp(lists:map(fun fib:go/1, lists:seq(1, 71))). [1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584, 4181,6765,10946,17711,28657,46368,75025,121393,196418, 317811,514229,832040,1346269,2178309,3524578,5702887, 9227465,14930352,24157817,39088169,63245986,102334155, 165580141,267914296,433494437,701408733,1134903170, 1836311903,2971215073,4807526976,7778742049,12586269025, 20365011074,32951280099,53316291173,86267571272, 139583862445,225851433717,365435296162,591286729879, 956722026041,1548008755920,2504730781961,4052739537881, 6557470319842,10610209857723,17167680177565,27777890035288, 44945570212853,72723460248141,117669030460994, 190392490709135,308061521170130] ( 190392490709135 + 117669030460994 /= 308061521170130 )
  - taeric 3y ago
    The question is if you can have a system that can derive the closed form from the definition. Not one you can feed it to. Right? Similarly, it may be faster to use the repeated squares approach to get a large value fib, and I don't know any system that can get that from the recursive definition, either.
    - toast0 3y ago
      Nonfunctional programming doesn't give you that either, so I don't see the problem? If you use the iterative / recursive form, runtime performance isn't great. If you use a lookup table, performance is great, but space might suffer (but then, how many values do you really need?). If you want to use something better, you've got to write it yourself. Maybe one day an optimizing compiler will figure it out, but it's more likely to figure out you never call it with N > 10, and precompute, and that's fine.
      - taeric 3y ago
shhsshs 3y ago
> Easier to build using imperative code than functional. I am a bit confused about this. The following code is pure and I can't think of an easier way to do it imperatively: function triangle(n) { if (n <= 1) { return [1] } const p = triangle(n - 1) return Array.from({ length: n }) .map((_, i) => (p[i - 1] ?? 0) + (p[i] ?? 0)) }
- taeric 3y ago
  I was actually mildly curious if anyone would call me on having picked an easy fractal to do with the recursion. :) When I wrote the post, I was thinking of the Koch curve. Not sure why I mixed it up in name with the other. I was definitely leaning on some of the abstractions that you get in the likes of turtle geometry to show how this works. Many of the programs you can write using those primitives are very interesting, and far more unwieldy in any other paradigm. At large, I view it as the difficulty of forcing Cartesian coordinates. For a large number of problems, things get far easier to state in polar coordinates. Such that your choice of abstraction and representation matters. A lot.
  - PaulHoule 3y ago
    Another "pure functional" approach to drawing these things is to write a shader program which takes the (x,y) coordinates and returns the pixel values. Here is a parameterized Koch curve done as a shader https://www.shadertoy.com/view/XdcGzH https://www.shadertoy.com/view/XdcGzH
    - taeric 3y ago
      Sadly, that page isn't loading for me. :( Mistake on my end? I'm going to guess that the shader version is a bit larger than the naive turtle version. Not that it isn't doable, but is tough evidence to hold for the benefits of the expressive power of functional code. :D
      - PaulHoule 3y ago

by taeric 3y ago

Not necessarily. For an easy counter example, build a Sierpiński triangle. Easy to unit test. Easier to build using imperative code than functional. (This goes for a ton of fractals, honestly.)

PaulHoule 3y ago

It burns me up that Fibonacci numbers are used so frequently as an example of functional programming because it is a clear case of malpractice, particularly because it performs terribly without memoization. Even in the 1980s CS profs were trying to tell us how BASIC sucks but efficient Fibonacci is so easy to code up in BASIC. (I'd really be impressed with a system that could figure out the closed form based on the definition.) How easy it is to draw fractals depends on your tools. If you have turtle graphics with affine transformations (rotation and scaling) it is so easy to write simple recursive programs to draw space filling curves and such.

taeric 3y ago
Change for a dollar is another fun one there. Closed form is mind bending, and I don't think we have built a system that can derive that.
dragonwriter 3y ago
> It burns me up that Fibonacci numbers are used so frequently as an example of functional programming because it is a clear case of malpractice, particularly because it performs terribly without memoization It's used as an example of basic recursive programming largely because its an example that can be returned to with memoization. That there is a better way to do it that can be shown later is a reason for selecting early examples in a curriculum.
JoelMcCracken 3y ago
Or you can write the tail-recursive version which starts from 1 and builds to n; no need to memoize.
toast0 3y ago
I don't see why you can't write the closed form in a functional language as well. This only works for 1 =< N =< 70, for N >= 71 the approximation of Sqrt5 isn't good enough; you need to do more symbolic math so you can eliminate that term. -module('fib'). -export([go/1]). go(N) when N < 1 -> throw(badarg); go(N) -> Sqrt5 = math:sqrt(5), round(1.0 / Sqrt5 * math:pow((1 + Sqrt5) / 2.0, N) - 1.0 / Sqrt5 * math:pow((1 - Sqrt5) / 2.0, N)). rp(lists:map(fun fib:go/1, lists:seq(1, 71))). [1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584, 4181,6765,10946,17711,28657,46368,75025,121393,196418, 317811,514229,832040,1346269,2178309,3524578,5702887, 9227465,14930352,24157817,39088169,63245986,102334155, 165580141,267914296,433494437,701408733,1134903170, 1836311903,2971215073,4807526976,7778742049,12586269025, 20365011074,32951280099,53316291173,86267571272, 139583862445,225851433717,365435296162,591286729879, 956722026041,1548008755920,2504730781961,4052739537881, 6557470319842,10610209857723,17167680177565,27777890035288, 44945570212853,72723460248141,117669030460994, 190392490709135,308061521170130] ( 190392490709135 + 117669030460994 /= 308061521170130 )
- taeric 3y ago
  The question is if you can have a system that can derive the closed form from the definition. Not one you can feed it to. Right? Similarly, it may be faster to use the repeated squares approach to get a large value fib, and I don't know any system that can get that from the recursive definition, either.
  - toast0 3y ago
    Nonfunctional programming doesn't give you that either, so I don't see the problem? If you use the iterative / recursive form, runtime performance isn't great. If you use a lookup table, performance is great, but space might suffer (but then, how many values do you really need?). If you want to use something better, you've got to write it yourself. Maybe one day an optimizing compiler will figure it out, but it's more likely to figure out you never call it with N > 10, and precompute, and that's fine.
    - taeric 3y ago

shhsshs 3y ago

> Easier to build using imperative code than functional. I am a bit confused about this. The following code is pure and I can't think of an easier way to do it imperatively: function triangle(n) { if (n <= 1) { return [1] } const p = triangle(n - 1) return Array.from({ length: n }) .map((_, i) => (p[i - 1] ?? 0) + (p[i] ?? 0)) }

taeric 3y ago
I was actually mildly curious if anyone would call me on having picked an easy fractal to do with the recursion. :) When I wrote the post, I was thinking of the Koch curve. Not sure why I mixed it up in name with the other. I was definitely leaning on some of the abstractions that you get in the likes of turtle geometry to show how this works. Many of the programs you can write using those primitives are very interesting, and far more unwieldy in any other paradigm. At large, I view it as the difficulty of forcing Cartesian coordinates. For a large number of problems, things get far easier to state in polar coordinates. Such that your choice of abstraction and representation matters. A lot.
- PaulHoule 3y ago
  Another "pure functional" approach to drawing these things is to write a shader program which takes the (x,y) coordinates and returns the pixel values. Here is a parameterized Koch curve done as a shader https://www.shadertoy.com/view/XdcGzH https://www.shadertoy.com/view/XdcGzH
  - taeric 3y ago
    Sadly, that page isn't loading for me. :( Mistake on my end? I'm going to guess that the shader version is a bit larger than the naive turtle version. Not that it isn't doable, but is tough evidence to hold for the benefits of the expressive power of functional code. :D
    - PaulHoule 3y ago