On my computer, the article's imperative range(6000) took 0.05 ms and the "functional" range(6000) took 400 ms. The whole [...cur, cur.length+1] thing turns a linear algorithm into a quadratic one. It wouldn't happen in all languages, but that's how JavaScript's arrays work. My advice is that if you really want to do stuff like this, choose appropriate data structures (i.e., learn about persistent data structures).
Except in this case the imperative version is already totally fine. It is modifying an array that it created itself. You have all of the benefits of avoiding shared mutable state already.
Also, the difference in performance would become even worse, except that for range(7000) I already get "Maximum call stack size exceeded" on the recursive one. The imperative implementation handles 10000000 without breaking a sweat. My second advice is to not use recursion to process arrays in languages (like JavaScript) that have a very limited call stack size.
At least in imperative code the "how" is explicit. In functional code it's implicit and you need intimate knowledge about compiler and/or runtime to know what's going to happen.
But also, writing imperative code doesn't guarantee explicit performance characteristics. Whether you mutate references or not, you still need to know which operations are fast and which are slow.
In JavaScript, concatenation, [...array1, ...array2], is non-mutating and slow. Adding an element to the end, array.push(x), is mutating and fast. But adding an element to the beginning, array.unshift(x), is mutating and slow. So even if you're sticking to mutation, you still need to know that push is fast and unshift is slow.
And yeah, sorry, "in JavaScript" is not quite right. I meant in my browser. This is not part of the spec, and it's not mentioned in the documentation. Is it the same in other browsers? Who knows. To me, this is just as much "you need intimate knowledge about compiler and/or runtime to know what's going to happen".
Unless there is clear evidences upfront that the project will be a piece of software where local performance is highly critical, it makes sense to favor code readability and maintainability over optimality.
Of course, you can have different level of code quality whatever the paradigm retained. Most languages out there will allow you to mix different paradigms anyway.
Given this fact, we would surely better served with an article like "When to favor expression in each paradigm available in your favorite language".
In the end the vanilla solution won in both areas. And I say that as an FP and Haskell fan boy.
Edit. For some reason people equate "functional" with Haskell, even though Javascript (and most modern languages) is perfectly capable of expressing functional idioms without the descent into madness.
Your vanilla solution is already a functional solution. Literally no need for `transduce pipe map over lens`
> My second advice is to not use recursion to process arrays languages (like JavaScript) that have a very limited call stack size.
Can also confirm this, here was my process on the some of the harder days in Advent of Code:
1. I wonder if I can solve this in a pure functional style with JavaScript
2. Yay, it works on the example input
3. Oh, I hit the call stack limit on the real input
4. Time to rewrite the recursion as a loop lol
IME avoid recursion, use immutability in the large while avoiding in local scope beyond a simple .map.filter chain, and on the backend I allow myself fp-ts to have sane error handling (I assumed TypeScript there but I'd just not ever use vanilla JS nowadays).
With that said I'd really, really rather use a compile to JS lang that does the optimizations for you, specially for frontend use cases.
Use ES6 classes to guard every property read and write behind a method-call.
You can avoid mutable state by making methods return only primitive data, including JSON. Then nobody can modify such state from the outside. You control and can easily observe all state-changes.
Both versions are quadratic if arrays are actual arrays and require a single chunk of memory. (push may need to copy the entire array)
If I remember correctly this is a pretty fundamental limitation of persistent structures, so it's not like there is a better persistent map data structure out there waiting.
That is a good point and should perhaps have been timed before being put as an example. Arrays themselves are usually quite the mutable data structure as well, so I think your advice about learning persistent data structures is spot on. Sometimes one can simulate a persistent data structure by using copying the whole or parts for some operations and use those only when one needs a separate copy.
Persistent data structure are really useful, and are (often) magnitudes more efficient than DIY-immutable data structures.
Imperative ones however, like you mentioned, are often (comparatively) near ideal by virtue of being imperative.
Languages like JavaScript and Rust (and Go?) have blurred the lines between purely functional and purely imperative. I think I prefer that compromise position myself.
To program in a functional style means no more or less than to construct your program by composing referentially transparent functions (that is, functions that have no side effects, and whose output is deterministic based on the inputs -- in other words: the mathematical notion of a function). The solutions that are marked as functional in the post fulfill this criterium, so it's correct to call them functional solutions.
Whether your functions are written in method notation or not is not relevant to determining whether the program is written in a functional style.
Hanging functions off of objects/types isn't really anti-functional either, as long as they don't mutate the subject
Functional programming is mainly about not changing state; you can do that with or without methods
Difference between functional style and functional language?
The line blurring ones are the ones taking the comprising position right? So you're saying you prefer Javascript, Rust and Go?
Then this post from my blog might be of interest:
Examples of method chaining in Python:
https://jugad2.blogspot.com/2016/02/examples-of-method-chain...
Honestly, I just opened your page and it's not a great example. Consider the method chaining in the linked article that operates on an array, it's much closer to real problems imo, and more succinct.
In Eiffel (which is an object oriented language), methods on objects are separated into two kinds: commands and queries. This is also known as the "Command-Query Separation" principle. The idea is that commands are the ones causing changes to the systems and queries only inform you about the system. `a_set.add(item)` changes the set, while `a_set.has(item)` tells you about the set but makes no changes to it. It's very useful, and very common. I mean, I'd hope that `some_collection.Size()` doesn't actually change its size, that's not what it exists to do.
1. Read the fields of 'this' 2. Write the fields of 'this' 3. Call other methods of 'this' (including "private" methods in many OOP languages)
That is very characteristic of OOP languages. Does anybody know if FP languages have something like the 'this' and if not what do they use instead?
Firstly if you're conceiving a novel algorithm it can be tedious to debug/test if written in a functional style because it's hard to step through in the debugger.
Second, you need to be extremely familiar with the language and ensure that you know that you're not mixing and matching mutable and immutable system calls, which will be hell to debug, see 1.
I'm not anti-functional and sometimes it can yield really clean and easy to read code, but I have to recoil when I see praises sung without the criticism.
Like anything, real life functional programming is not a panacea and most languages that append functional constructs as an afterthought often come with a price (debugging, performance) and just as you pointed out, mixing functional code with imperative code indiscriminately can yield wonderfully nuanced bugs.
With that, I find languages like OCaml and F# provide a great ergonomic experience for writing both functional and imperative style code. (There’s nothing wrong with imperative code confined to the scope of a function or a well defined object)
Even with great tools, I still think there’s quite a bit that can be done to improve the hidden costs incurred from a functional-first approach.
This is often the case with hash tables. Sometimes one simply wants to store an info and the fact, that this info has been discovered or processed or occurred. If one makes the hash table inside the function where it is used, then the important aspects of no side effects and no mutation of arguments of the function are still preserved.
However, sometimes a problem can arise later, when wanting to parallelize something inside that function involving the hash table. So one needs to be a bit careful here as well.
Thhat is a fine point which I rarely see discussed in connection with FP. (Pure) FP is commonly understood (?) to mean that there can be no mutable data. You can "bind" a value to a variable but only once. Right?
But within a function you can have local variables. I don't see why it would be bad to assign multiple different values to the same local variable, which only exists during the execution of the function. The variable only exists in the "stack" not in the "heap" and is gone as soon as the function returns.
So if I run a while-loop and repeatedly assign a new value to the local variable "i" for instance, would that be unacceptable according to "FP"? Why? I can't see any ill effects from modifying a variable whose value can not "linger" past the execution of the function.
What am I missing? Why is it (supposed to be) bad to rebind any number of different values to a local variable?
If you are using a lazy evaluated language like Haskell, instead of the stack trace you're used to in an imperative programing language, you'd get the reductions that led up to the reduction of the expression with the breakpoint on it.
The second point, However, I do agree with, especially in languages where mutability is the default.
How is this not the case, for say, python?
E.g. You can get yourself into real trouble with a function like this in python.
def f(dict = {}):
return dictLanguages that were designed from the ground up to be pure functional, like Haskell, keep you from making this mistake.
F# (and other FP languages, like Scala) have standard libraries which come with (and are built around) persistent collections (immutable collections, but with smart structural sharing when doing copy-on-write). And all the other libraries and the whole community is designed for Functional Programming.
There are also other aspects, that FP languages like F# or Scala tend to have shorter and prettier syntax. And many of the FP idioms are easier to express in these languages. Good example would be ADTs (algebraic data types), or Computation expressions in F# and its analogue in Scala for-comprehension. But these are more subjective reasons than my former point.
Unless f# has massive advantages over c# when it comes to functional programming, I would say this paradigm is not worth it in 90% of my programming projects.
type User = Admin | Basic
And generate a lot of overhead both in execution time and memory. Which is unacceptable in games where every ms counts.
>Games tend to define update() functions which mutate some state each tick. We can avoid mutation by taking game state as an argument and returning new state. Now our game is much easier to test too! We simply call update with some game state and assert that the result is what we expect. Imagine how hard it would be test the imperative update function!
As a game dev I kinda cringe on the idea of copying WHOLE world state just to update it (and if I understand correctly we copy the state EVERY TIME we want to update i.e: from every actor instance?).
The way I would do this imperatively with N cores is, I would have the game state be an array, and I would have each core update 1/Nth of the array. That might thrash the cache, but it wouldn't need any locking at all.
Functionally, it could probably be done better to have each core produce a new sub-state, and then have one thread combine the N sub-states into the new state, and update all the threads with the new combined state.
A nice showcase of this idea is in Juan Pedro Bolivar Puente's CppCon '17 talk Postmodern Immutable Data Structures: https://youtu.be/sPhpelUfu8Q
Lazy data structures can be very efficient (slower than mutable one in single-threaded execution, but much faster for concurrent usage) and they definitely don’t copy everything every time.
I know something about lazy data structures from my IOI days and I'm pretty sure I know about game development (altough admittedly forgot about this stuff while reading this post as it is not mentioned in the article itself, others comments provided nice resources).
While they are extremely efficient you still have an overhead. It is obviously minimal but it can matter with -+10000 updates (game logic, actors only, with some overhead by itself) per frame - not per second. O(log n) is not dissmisible (in some hardcore cases I would say that even O(log log n) can have slight impact and If you can have steady 60fps rather than 59fps you want that).
Game development also doesn't really align with functional programming (as described in the article). I mean the main thing to care about is speed since it allows us to do more fancy stuff. Then again, I'm not an engine developer so who knows, maybe it's actually better and some big engines do use it at core (If anyone knows I'm interested). But in most cases it's a lot harder to do (since games do SO much different stuff that It's really hard to seperate parallelizable from sequential tasks anyway and it simply doesn't make sense in most productions).
I respect FP, but I don't envision using it personally, and by the way, I don't get how OOP is getting bashed on HN so much. Like google FP + HackerNews and there are articles about FP like this one, google OOP + HN and you get "OOP is not just bad, it's super-duper-hyper-ultra atrocious".
Imagine a style of programming where everything is assumed to be asynchronous, all the way down to language primitives. Someone who only ever wrote AsyncScript would look at TypeScript, say "Requests are inevitable, you're always going to end up in async/await anyway, so what's the point?"
This is exactly the relationship between imperative and pure-functional programming: the point of having explicit effect monads (or some other tracking system) is that it makes it possible to write code that isn't in them.
I feel like I would be more likely to get burned by the above point (complexity and boilerplate) vs. a mutated state bug or a "gorilla is holding the banana" problem, especially considering that the former is an ongoing effort and the latter is things you only need to deal with at times, if ever.
I think a lot of the OOP bashing comes from soooooo much bad OOP code out there (I'm looking at you "enterprise JAVA")!
This is also the reason some people have a bad taste in their mouths about other things: PHP, JavaScript library hell, etc.
On top of all that runtime errors are way less common because the compiler catches so much more
Stepping through code is nice when it works, but it often falls apart when there's concurrency, since all you get to step through are timeouts.
The more I read about functional programming the more it seems like that. Am I correct in my assumption? Is functional programming declarative? Is all functional programming declarative?
APL seems a little like this from my research.
The thing that confuses me is that under the hood isn't the computer doing those loops? It's just hidden from you?
> The thing that confuses me is that under the hood isn't the computer doing those loops? It's just hidden from you?
No. Under the hood the computer is doing conditional jumps. And yeah, those are hidden from you. :)
Of course my apologies. I was more thinking about in the language it's written in (C for some of it?). But yes at the assembly level.
It took me a while to get my head around it for J (array language written in C), which under the hood must be using a loop but you don't explicitly loop in array languages.
Helping a C++ friend of mine with some Scala code the other day, there was a line like this:
val requests = availableDrivers.filter(notPhonedHome).map(pleasePhoneHomeRequest)
I thought of this line in a more declarative way: requests is a list of phone home requests for the drivers that haven't phoned home recently.
Both of us used a simplified mental model that didn't fully reflect what the computer is doing. My model didn't account for memory allocations. His model didn't account for potential optimizations. Neither of our models accounted for type-level trickery, possible side effects of pleasePhoneHomeRequest, or error handling (although his was closer to accounting for side effects and error handling.) Does the intermediate array actually get constructed? What happens if pleasePhoneHomeRequest throws an exception? Is requests a concrete collection type, or is it something akin to an iterator?
In practice, a language like SQL has similar concerns. Occasionally you may need to be aware that an awkwardly constructed query requires space that exceeds the size of the relevant data, or that a delete cascades in a way that is inherently slow.
tl;dr Functional programming idioms are designed to let you think more declaratively when you read and write code, but sometimes the declarative view isn't adequate for understanding the code.
Part of the charm of purely functional solutions for me (and why I'm hooked) is that it forces you to think about the representation of the data that you would need in order to have a "clean" solution without mutation. E.g. IntMap for index of arrays and folding with Set/Map operations to build state without accruing algorithmic complexity. I've found that I do a lot more "deep thinking" when forced into using (or creating) the right data-structures and this is something I enjoy a lot more than purely iterative debugging/hacking, and it's more satisfying (to me) at the end of it all.
My go-to for AoC is almost always Attoparsec + Containers with a recursive "solve" function and the complexity seemingly always stays manageable. I'm no savant but feel free to give examples of a tricky task to solve functionally I can share a specific solution.
Would love to see your solution for one of these problems!
For arrays I wrote a functional map function, since my language did not have a functional one and I only used it for transforming input, while preserving the original input under a different binding.
For hash tables I could have used functional sets, which I only bothered with in later puzzles, because I wanted to parallelize things.
I did parallelize quite a few things in later puzzles, just because it is so easy to do when you have pure functions.
So at least 26 of 50 puzzles are perfectly possible in functional style.
[1]: https://notabug.org/ZelphirKaltstahl/advent-of-code-2022
Is that really what FP is? I had the impression that FP was something different.
I think the confusing bit is that one of the most popular functional programming languages is Haskell... which is really hard. So certainly in my mind I had "functional programming = like Haskell = stupidly difficult" for ages. But Haskell is difficult for other reasons: really abstract type system, functions are pure, etc.
Oh also another thing is they all tend to really encourage you to use immutable singly linked lists and write recursive functions that match on (head :: tail)... but I don't think you have to do that, and IMO it's the wrong thing to do a lot of the time (it semantically nice but computationally terrible).
As a side note, those 2 or 3 were not any more or less capable, in the end, than other interviewers.
I don't quite know what to do with that datapoint, but it is interesting.
The imperative solution makes perfect sense and is fast, everyone can understand it including future me. I don't have to think about it at all and just understand it as I'm reading it.
In the real world out there this is something that carries a lot of value.
The recurrence relation of range(n)=range(n-1):n is easily understood and also already the naive functional implementation.
These kinds of recursive/recurrence definitions are part of K12 curriculae, and not just at the end of it.
Functional programming is not inherently harder to understand than imperative programming. Your school blackboard has been functional and stateless since grade 1. At some point somebody tacked state on to your mental model, and somehow I=I+1 now makes sense.
To me it looks like a purely educational problem, when FP is dismissed for not being easily understood, compared to the IP abstractions.
Sometimes functional style isn't as clear (especially recursion for me). But things like map and filter are usually a lot easier for me to read than for loops.
In the imperative solutions, the programmer is essentially thinking and acting like a problem solver AND computer. There's the human element of understanding the problem and devising a solution, and then there's the step-by-step implementation. This is fine, and it's quite good for learning how to think. But it doesn't take much experience to ascend above it...
The FP solutions illustrate a problem solver "telling" the computer what operations to perform on a dataset to get the result.
At first even the tiny FP example may be off-putting to someone from an imperative background. It may seem a bit obtuse. But really, it is just thinking about the major steps necessary to transform one set of data into another, and then knowing which tools/building blocks to use to achieve that goal. You intentionally stop caring about how to add elements of a list together and instead just choose the right functions to map/apply/(reduce) your data with.
Now what I have not yet wrapped my head around is the Clojure transducers. I get the concept, but haven't quite grokked it fully. They are the step beyond the data.do_this.then_do_this.etc.
But for me, FP approaches, even applied to traditionally imperative languages (even Python, with some struggling with inconsistent and unergonomic details) provide some key benefits.
1. Pure functions can be understood and then forgotten about; once you know what it does, your mind is free to never worry about unexpected things going on inside. This is counter to typical OO functions which mutate objects at will. The mental load is so much higher with the OO mutation functions.
2. Pure functions are vastly easier to test. Couple this with using simpler, decoupled data types (hashmaps, arrays, structs... things which generally do not require special setup and teardown due to instance creation activities) and you have a much easier time writing tests that cover 100% of lines/branches - in fewer lines of code than incomplete OO tests.
All that said, I am less enthusiastic about passing anonymous functions everywhere as is common in modern JavaScript. That increases the cognitive load for me simply because it's harder to remember what does what and where things are happening. So I try not to have more than 1-2 layers of functions passed to functions.
There is one FP-related challenge which doesn't really have a solution as far as I can tell: more small functions means more function names to think of. To keep them recognizable and memorable, the names must be pretty descriptive. This means you can end up with some_pretty_long_function_names. It's a small concern, however. And as a bonus, your code ends up reading a lot more like human language - meaning you can give a code tour to a less technical person and they may actually be able to follow.
I.e., you can fully contain anything that a called function does.
It is immensely powerful.
In some languages the imperative for loop is the most efficient way to iterate, sometimes the compiler does optimize functional code into imperative code
If performance becomes a problem (it might, after all there are several more passes than strictly necessary), have tests in place and refactor to an optimised imperative version.
4. Make most code harder to read