Hacker News Reader

Comment by PaulHoule | Hacker News Reader

Systems that have clear inputs and outputs. Parsers, compilers, stuff like that. SAT Solvers. Anything you could unit test without mock objects.

Mixed initiative systems (say UI code where you call into the framework and the framework calls into you) can go either way. Sometimes you can formulate the part of your code in a pure functional way which tames the chaos, if you can’t or that formulation is unnatural the chaos tames you.

System w/ immutable data structures lose a factor of two or so in performance in some cases. FORTRAN programmers won’t accept them, distributed “big data” systems will spend a lot of time marshaling and unmarshaling data and won’t accept any slowdown in their parsing code. The same could be true for something like that SAT solver.

View on HN

>Anything you could unit test without mock objects

You can unit test without mock objects because you're following functional patterns.

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.)

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.

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.

> 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.

Or you can write the tail-recursive version which starts from 1 and builds to n; no need to memoize.

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 )

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.

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.

Right, but the post is "I'd really be impressed with a system that could figure out the closed form based on the definition." Point seeming that coding up a recursive process based on the definition doesn't seem to be the best reason to teach something that way.

This goes back to a ton of the talk on early compilers and systems. They would push that you should lean heavily on the system to move from definitions to optimal solutions. (This later got changed heavily to leaning only on the compiler, but the same idea applies.)

That was parenthetical, I was responding to "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"

Right, I took that to be that the complaint is the recursive definition is used to teach it. Stated differently, ignoring the parenthetical takes the weakest interpretation of that post.

> 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))
    }

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.

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

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

It is 74 lines of basically C code on a page that runs the shader with WebGL. On my iPad it renders at 60 fps with a parameter that changes. It’s really neat.

It doesn’t look like “functional code” but it really is since the shader returns a pixel color for x and y. I bet there is some squarish kind of fractal that could be code golfed with but manipulation.

Odd that the page doesn't show me the code. For some reason, webgl is busted on my firefox at the moment. Not sure if that is my fault or something else. I'd expect it to still show the code, though. :(

At any rate, thanks for the link! Will try another computer later to see if it can load.

... or working in an environment or on a problem for which functional patterns apply.

Suppose you are writing a "CRUD" app that writes to a relational database, how do you apply functional programming to that? The whole point of an application like that is that it makes side effects.

In some cases you can break those problems down into functional pieces. Consider Python drivers for a product like

https://www.arangodb.com/

One major problem is that you want drivers that work synchronously and asynchronously, the structure of the average api call is something like

   def query(parameters):
      encoded_parameters = encode_parameter(parameters)
      url = generate_rest_url(configuration, parameters)
      response = do_post(url, encoded_parameters)
      return decode_response(response)

To make that async all you have to do is stick "async" before the def and put an "await" before the do_post. 95% of the API calls have a structure like the above. Most of the complexity lives in encode_parameter(), generate_rest_url() and decode_response() are all perfectly functional functions that are easy to test. Code gen the API stubs and you get sync and async switching almost for free. Contrast that to the option of mocking do_post.

I never really understood what a "monad" is but for a program like that I'd have all the "side effect" stuff separated from all the "data manipulation" stuff. It could all be organized as functions, which I generally do because I find it much easier to reason about mentally than objects.

"Pure" functional programming is an extreme which probably isn't suitable for many real-world programming tasks. Functional style is typically what I do, I use lists and maps and folds quite a bit but still end up updating a database.

Code like the above can be restructured with monads in various ways.

In general there is the pattern of building systems that do execution control such as the methods used to create control structures in Lisp, the Executor in Java, etc. One way to use monads is to accumulate a list of operations that need to be done and actually does the operations when you "unpack" the monad at the end. Such a monad could do many of the things a compiler does since it has the operation list at the outset and doesn't just blast from one statement to the next. This blends into the techniques used in Fluent DSLs.

Usually your database connection is a function that is passed as a parameter to the functions using it.

That way you don't need to Mock, but you can input a "connection" during testing that does what you expect.

If you say "well now I have to type extra parameters everywhere", this is usually solved with partial application. I.e. you create findings from your functions that have the Db Connection already baked inside.

https://fsharpforfunandprofit.com/posts/low-risk-ways-to-use...

https://fsharpforfunandprofit.com/posts/partial-application/

Haskell has the IO Monad which is like a magic type that is allow to have any side effect whatsoever. So you are free to write imperative code in Haskell.

However what you might want to do (and this is based on IIRC!) is have a typeclass for your database interaction. Then the real DB type and the mock one can both implement that typeclass and you have basically dependency injection.

There are other ways like free monads but I never got my head around that.

You could also create a monad transformer which is a bit more straight forward. They let you compose monads, so you can chain little bits of side effect. Like “here is something that can talk to a database and write logs and that is all it will do” … but actually it is pure! It thinks it is doing those things but they can be mocked.

Could you elaborate a little bit more? These days i write a lot of go code and i end up using mock objects for different interfaces to write unit tests. Is there another way to do this?

Reply on news.ycombinator.com