6 ms·

I still don't understand what all the hype is about pure functional programming. Sometimes mutations are useful. There are lot of good programming design patte

I still don't understand what all the hype is about pure functional programming. Sometimes mutations are useful. There are lot of good programming design patterns which depend on mutations. Also, always copying objects by value every time you call a function seems very expensive; especially if you're dealing with very large objects/structs/maps/strings which have to be processed by many functions.

jondubois 10y ago
I just had a thought; if arguments always get cloned by value every time they are passed to a function, doesn't that mean that the time complexity for an insertion operation in Elixir can never be better than O(n)? According to this answer http://stackoverflow.com/questions/11055391/time-complexity-of-erlang-dict http://stackoverflow.com/questions/11055391/time-complexity-... it claims that for dictionaries it's O(log n). How is that possible if mutations are not allowed? Wouldn't the function have to process at least n items? Or it uses parallel processing to get a speedup there?
- andy_ppp 10y ago
  If I create an immutable string "hello world" why would it be passed by copy; it can never be changed only garbage collected. The BEAM seems to do magic here and do much less work than you might think when creating "new" things.
- owaislone 10y ago
  If you are only dealing with Immutable structures that no one can really change, there is no point in passing by value. You can always pass by reference. The language will not allow any code to modify it. Instead a new variable will have to be assigned if the function changes the values. So, it can always be pass by reference until a change needs to be made aka copy on write.
fetbaffe 10y ago
You only need to copy the data if the consumer of the data changes it, i.e. copy-on-write.
- jondubois 10y ago
  That sounds a bit better than I thought but it still doesn't change the worst-case complexity.
  - fetbaffe 10y ago
    Depends on the scenario, if you know a value never changes, you can share that between variables under the hood, as the article explains with the example about sorting arrays. Passing around complex mutable structures feels more like procedural programs.
  - jlouis 10y ago
    Consider a binary tree. You don't have to copy the whole tree, which is O(n) but rather only the "spine" path from the altered element to the top, which is O(lg n). In practice, there are also many cases which ends up on the stack and never reaches the heap, so the memory allocation needs are somewhat smaller than what people think. Another point is that short-lived garbage is collected in O(1) time in the GC. So you don't pay for its collection either. Things are slower than a mutation, but the overhead is lower than people tend to think.
  - axiomabsolute 10y ago
    The canonical text discussing how this is achieved refers to data structures optimized for immutability as "purely functional data structures". [1] These type of data structures are the default for Clojure as well, and there are a number of blog posts and presentations discussing their implementation. [2] [3] It's a reasonably complicated topic, but the basic idea is that since the data structures are immutable, much of their structure can be shared between versions with few changes. Most of these data structures end up using a Tree of some sort. Performance characteristics can be influenced to an extent by using bucketing to control the width/height of the tree. [1] : Purely Functional Data Structures (Amazon: https://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504 https://www.amazon.com/Purely-Functional-Structures-Chris-Ok...) [2] http://hypirion.com/musings/understanding-persistent-vector-pt-1 http://hypirion.com/musings/understanding-persistent-vector-... [3] https://www.youtube.com/watch?v=7BFF50BHPPo https://www.youtube.com/watch?v=7BFF50BHPPo
danielnesbitt 10y ago
Pure functional languages often do not use the same data structures common in imperative languages. Instead there's an emphasis on persistent structures that copy on write while sharing as much data as possible. For instance, prepending to a linked list results in a new head node, but nothing is actually copied. Appending requires a full copy. A developer has to be aware of where the limitations of these data structures are, but I think that's true of using any library in any language. https://en.wikipedia.org/wiki/Persistent_data_structure https://en.wikipedia.org/wiki/Persistent_data_structure
- mohaine 10y ago
  The performance issue still stands. Linked Lists are often MUCH slower then array backed lists on modern hardware. This is true even when doing lots of inserts. Having all your list in the CPU cache is just too much of a performance gain over having it spread out in random locations.
  - whateveracct 10y ago
    Depending on your GC, linked lists won't be "spread out in random locations." The nodes will be allocated right next to each other in the case where you're building up a list iteratively.
    - mohaine 10y ago
      How does the GC change allocations? While I agree that this Linked list memory layout should be optimized, with real world tests Array backed normally win by a large margin.
jordwest 10y ago
This is something I think Rust solves very nicely. The ownership model gives the benefits of immutability (no shared mutable state and race conditions) without the need to copy most of the time.
digitalzombie 10y ago
Erlang isn't purely functional... the time function is an example. To be pure, iirc, a function call have to return the same result everytime, there's a one to one mapping for each parameter there's a unique value. time() is an arity 0 (no parameters) and yet it return different value every time you call it depending on the time currently. You can mutate by making a new copy, you modify the old one and save it to a new variable. The old variable is unchanged. If you set x <- 1, you can't change x anymore but you can do y <- x + 1. Your modification is in a new variable. Elixir you can change x to a new value but that's just a new copy, unless you pin it.. You can also keep state by passing an accumulator via function parameter, it's also how you to tail call optimization. It's a weird pattern and I haven't use functional paradigm enough to give one on top of my head.
josevalim 10y ago
In practice, functional languages typically use persistent data structures, which represent collections such as dictionaries, vectors, sets internally as trees. Adding, removing and updating data requires changing a path in this tree while sharing the remaining of the structure. It is not a deep a copy and a really large map won't be very expensive to modify. Rich Hickey has a good talk on the matter: https://www.youtube.com/watch?v=dzP05hEDNvs https://www.youtube.com/watch?v=dzP05hEDNvs There are also optimizations that are straight-forward to understand and implement once you assume immutability. For example, take the following function in Elixir: def some_list do [1, 2, 3] end Because a list is immutable, when code is compiled we put such data structures that appear literally in the code into something called a literal pool. Anything in literal pool is loaded when the code is loaded. Now every time you call that function, we return the same list and we don't create new instances/copies on every call. That list may be embedded in a map, another list, whatever, and still point to the same memory representation because nothing will ever change it. Here is an example that leverages this in the context of a web framework for great rendering performance https://www.bignerdranch.com/blog/elixir-and-io-lists-part-2-io-lists-in-phoenix/ https://www.bignerdranch.com/blog/elixir-and-io-lists-part-2.... While this is definitely achievable in other languages, we get it pretty much for free with immutable data structures and it is a natural mechanism to reason about. IanCal talked about it a couple comments above: https://news.ycombinator.com/item?id=13498532 https://news.ycombinator.com/item?id=13498532 Regardless, you are still correct when you say that mutations are useful. There are many algorithms that will be more performant if implemented on top of mutations. Luckily, most functional programming languages, including the pure ones, provide mutable data structures or memory references for such cases. For example, when working on GenStage/Flow for Elixir, I optimized the hot paths by using mutable dictionary and called it a day. Many claim immutable data structures are a better "default" for writing software since it is conceptually simple to reason about code when data cannot change right under your feet. However, I won't try to argue if this is actually the case or not, as this reply is already quite long as is. The point is that many concerns regarding immutable data structures are solved and functional languages also provide alternate paths when you need mutability.
keymone 10y ago
> Sometimes mutations are useful especially in a hello-world sized projects. as you scale up mutations become a constant source of bugs, bottlenecks and complexity. > always copying objects by value every time you call a function seems very expensive; especially if you're dealing with very large objects/structs/maps/strings which have to be processed by many functions structural sharing in functional persistent data structures makes this problem go away 99% what you get in exchange for giving up mutability are programs that are easier to reason about, have less bugs, better modularity, less man-hours wasted on maintenance. all the good stuff.
- Bahamut 10y ago
  I think the person's point was that you sacrifice performance - having the ability to mutate is only a good thing there, as immutability without being able to exit out of that is too inflexible and potentially could cause other hacks to appear when trying to solve that problem. FP with a focus on immutability is good for the default, but ignoring its limitations is bad.
  - acomar 10y ago
    Sure, but I don't know any pure languages that provide no facilities for mutation whatsoever, they just ask you to be explicit about it and add some syntactic weight (which is a good thing, you want mutation called out as a reader). Haskell provides several different mutation options from simple references to various kinds of thread-safe references depending on what semantics you need. There's even a "no-really-trust-me" option. So where does the myth that you can't exit out of immutability come from?
    - lobster_johnson 10y ago
      Erlang is purely immutable and doesn't have any "facilities for mutation" that I know about, although it does have side effects (I/O, but no Haskell-style effect system).
      - 10y ago
deleted 10y ago
[deleted]
pka 10y ago
I don't know why people keep spreading the misconception that mutation isn't possible in pure languages. ref <- newIORef 0 writeIORef ref 1 y <- readIORef ref print y > 1 There you go, mutation in Haskell.
stcredzero 10y ago
I still don't understand what all the hype is about pure functional programming. Sometimes mutations are useful. There are lot of good programming design patterns which depend on mutations. Study the Chomsky Hierarchy and the Theory of Automata. < https://en.wikipedia.org/wiki/Automata_theory https://en.wikipedia.org/wiki/Automata_theory > Here it is in a nutshell: Languages are synonymous with computation. These can be divided into just a few types, based on how they can use state. One can observe that the complexity of an automata and its corresponding language increases dramatically with its use of state. (Turing Tarpit https://en.wikipedia.org/wiki/Turing_tarpit https://en.wikipedia.org/wiki/Turing_tarpit) You can avoid complexity by avoiding complex interactions with state. Also, always copying objects by value every time you call a function seems very expensive In the case of parallel/concurrent computation, it can be the less expensive option. < https://mechanical-sympathy.blogspot.com/2011/07/false-sharing.html https://mechanical-sympathy.blogspot.com/2011/07/false-shari... > As always, the devil is in the details, and it's all about context. So you are correct. Sometimes mutations are useful. However, sometimes, you can get a benefit from avoiding them.
didibus 10y ago
In Erlang, the pureness allows a clean split between processes and enables that clustering and hot loading magic. While it's less efficient for a single operation, it scales to handle many parallel operations way better. This is generally why pure functional is hyped. It's just easier to think of a pure functional construct, there's less possibility for mistake. No one claims it to be efficient at single operations. Though some people blame the hardware for that, as in theory, there's nothing slower about it.
pdimitar 10y ago
> Also, always copying objects by value every time > you call a function seems very expensive This is a non-point. In Erlang/Elixir everything is immutable and 95% of the time data is passed by an immutable reference thus effectively eliminating data copying. Also, if you use iolists for text processing (instead of appending strings), you absolutely will reuse all string chunks you use in the entire Erlang/Elixir OS process, even if you don't want to. It's mega-efficient. EDIT: @josevalim (Elixir's creator) explains it much better than I can, right here in this thread: https://news.ycombinator.com/item?id=13499328 https://news.ycombinator.com/item?id=13499328.

I still don't understand what all the hype is about pure functional programming. Sometimes mutations are useful. There are lot of good programming design patterns which depend on mutations. Also, always copying objects by value every time you call a function seems very expensive; especially if you're dealing with very large objects/structs/maps/strings which have to be processed by many functions.

jondubois 10y ago

I just had a thought; if arguments always get cloned by value every time they are passed to a function, doesn't that mean that the time complexity for an insertion operation in Elixir can never be better than O(n)? According to this answer http://stackoverflow.com/questions/11055391/time-complexity-of-erlang-dict http://stackoverflow.com/questions/11055391/time-complexity-... it claims that for dictionaries it's O(log n). How is that possible if mutations are not allowed? Wouldn't the function have to process at least n items? Or it uses parallel processing to get a speedup there?

andy_ppp 10y ago
If I create an immutable string "hello world" why would it be passed by copy; it can never be changed only garbage collected. The BEAM seems to do magic here and do much less work than you might think when creating "new" things.
owaislone 10y ago
If you are only dealing with Immutable structures that no one can really change, there is no point in passing by value. You can always pass by reference. The language will not allow any code to modify it. Instead a new variable will have to be assigned if the function changes the values. So, it can always be pass by reference until a change needs to be made aka copy on write.

fetbaffe 10y ago

You only need to copy the data if the consumer of the data changes it, i.e. copy-on-write.

jondubois 10y ago
That sounds a bit better than I thought but it still doesn't change the worst-case complexity.
- fetbaffe 10y ago
  Depends on the scenario, if you know a value never changes, you can share that between variables under the hood, as the article explains with the example about sorting arrays. Passing around complex mutable structures feels more like procedural programs.
- jlouis 10y ago
  Consider a binary tree. You don't have to copy the whole tree, which is O(n) but rather only the "spine" path from the altered element to the top, which is O(lg n). In practice, there are also many cases which ends up on the stack and never reaches the heap, so the memory allocation needs are somewhat smaller than what people think. Another point is that short-lived garbage is collected in O(1) time in the GC. So you don't pay for its collection either. Things are slower than a mutation, but the overhead is lower than people tend to think.
- axiomabsolute 10y ago
  The canonical text discussing how this is achieved refers to data structures optimized for immutability as "purely functional data structures". [1] These type of data structures are the default for Clojure as well, and there are a number of blog posts and presentations discussing their implementation. [2] [3] It's a reasonably complicated topic, but the basic idea is that since the data structures are immutable, much of their structure can be shared between versions with few changes. Most of these data structures end up using a Tree of some sort. Performance characteristics can be influenced to an extent by using bucketing to control the width/height of the tree. [1] : Purely Functional Data Structures (Amazon: https://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504 https://www.amazon.com/Purely-Functional-Structures-Chris-Ok...) [2] http://hypirion.com/musings/understanding-persistent-vector-pt-1 http://hypirion.com/musings/understanding-persistent-vector-... [3] https://www.youtube.com/watch?v=7BFF50BHPPo https://www.youtube.com/watch?v=7BFF50BHPPo

danielnesbitt 10y ago

Pure functional languages often do not use the same data structures common in imperative languages. Instead there's an emphasis on persistent structures that copy on write while sharing as much data as possible. For instance, prepending to a linked list results in a new head node, but nothing is actually copied. Appending requires a full copy. A developer has to be aware of where the limitations of these data structures are, but I think that's true of using any library in any language. https://en.wikipedia.org/wiki/Persistent_data_structure https://en.wikipedia.org/wiki/Persistent_data_structure

mohaine 10y ago
The performance issue still stands. Linked Lists are often MUCH slower then array backed lists on modern hardware. This is true even when doing lots of inserts. Having all your list in the CPU cache is just too much of a performance gain over having it spread out in random locations.
- whateveracct 10y ago
  Depending on your GC, linked lists won't be "spread out in random locations." The nodes will be allocated right next to each other in the case where you're building up a list iteratively.
  - mohaine 10y ago
    How does the GC change allocations? While I agree that this Linked list memory layout should be optimized, with real world tests Array backed normally win by a large margin.

jordwest 10y ago

This is something I think Rust solves very nicely. The ownership model gives the benefits of immutability (no shared mutable state and race conditions) without the need to copy most of the time.

digitalzombie 10y ago

Erlang isn't purely functional... the time function is an example. To be pure, iirc, a function call have to return the same result everytime, there's a one to one mapping for each parameter there's a unique value. time() is an arity 0 (no parameters) and yet it return different value every time you call it depending on the time currently. You can mutate by making a new copy, you modify the old one and save it to a new variable. The old variable is unchanged. If you set x <- 1, you can't change x anymore but you can do y <- x + 1. Your modification is in a new variable. Elixir you can change x to a new value but that's just a new copy, unless you pin it.. You can also keep state by passing an accumulator via function parameter, it's also how you to tail call optimization. It's a weird pattern and I haven't use functional paradigm enough to give one on top of my head.

josevalim 10y ago

In practice, functional languages typically use persistent data structures, which represent collections such as dictionaries, vectors, sets internally as trees. Adding, removing and updating data requires changing a path in this tree while sharing the remaining of the structure. It is not a deep a copy and a really large map won't be very expensive to modify. Rich Hickey has a good talk on the matter: https://www.youtube.com/watch?v=dzP05hEDNvs https://www.youtube.com/watch?v=dzP05hEDNvs There are also optimizations that are straight-forward to understand and implement once you assume immutability. For example, take the following function in Elixir: def some_list do [1, 2, 3] end Because a list is immutable, when code is compiled we put such data structures that appear literally in the code into something called a literal pool. Anything in literal pool is loaded when the code is loaded. Now every time you call that function, we return the same list and we don't create new instances/copies on every call. That list may be embedded in a map, another list, whatever, and still point to the same memory representation because nothing will ever change it. Here is an example that leverages this in the context of a web framework for great rendering performance https://www.bignerdranch.com/blog/elixir-and-io-lists-part-2-io-lists-in-phoenix/ https://www.bignerdranch.com/blog/elixir-and-io-lists-part-2.... While this is definitely achievable in other languages, we get it pretty much for free with immutable data structures and it is a natural mechanism to reason about. IanCal talked about it a couple comments above: https://news.ycombinator.com/item?id=13498532 https://news.ycombinator.com/item?id=13498532 Regardless, you are still correct when you say that mutations are useful. There are many algorithms that will be more performant if implemented on top of mutations. Luckily, most functional programming languages, including the pure ones, provide mutable data structures or memory references for such cases. For example, when working on GenStage/Flow for Elixir, I optimized the hot paths by using mutable dictionary and called it a day. Many claim immutable data structures are a better "default" for writing software since it is conceptually simple to reason about code when data cannot change right under your feet. However, I won't try to argue if this is actually the case or not, as this reply is already quite long as is. The point is that many concerns regarding immutable data structures are solved and functional languages also provide alternate paths when you need mutability.

keymone 10y ago

> Sometimes mutations are useful especially in a hello-world sized projects. as you scale up mutations become a constant source of bugs, bottlenecks and complexity. > always copying objects by value every time you call a function seems very expensive; especially if you're dealing with very large objects/structs/maps/strings which have to be processed by many functions structural sharing in functional persistent data structures makes this problem go away 99% what you get in exchange for giving up mutability are programs that are easier to reason about, have less bugs, better modularity, less man-hours wasted on maintenance. all the good stuff.

Bahamut 10y ago
I think the person's point was that you sacrifice performance - having the ability to mutate is only a good thing there, as immutability without being able to exit out of that is too inflexible and potentially could cause other hacks to appear when trying to solve that problem. FP with a focus on immutability is good for the default, but ignoring its limitations is bad.
- acomar 10y ago
  Sure, but I don't know any pure languages that provide no facilities for mutation whatsoever, they just ask you to be explicit about it and add some syntactic weight (which is a good thing, you want mutation called out as a reader). Haskell provides several different mutation options from simple references to various kinds of thread-safe references depending on what semantics you need. There's even a "no-really-trust-me" option. So where does the myth that you can't exit out of immutability come from?
  - lobster_johnson 10y ago
    Erlang is purely immutable and doesn't have any "facilities for mutation" that I know about, although it does have side effects (I/O, but no Haskell-style effect system).
    - 10y ago

deleted 10y ago

[deleted]

pka 10y ago

I don't know why people keep spreading the misconception that mutation isn't possible in pure languages. ref <- newIORef 0 writeIORef ref 1 y <- readIORef ref print y > 1 There you go, mutation in Haskell.

stcredzero 10y ago

I still don't understand what all the hype is about pure functional programming. Sometimes mutations are useful. There are lot of good programming design patterns which depend on mutations. Study the Chomsky Hierarchy and the Theory of Automata. < https://en.wikipedia.org/wiki/Automata_theory https://en.wikipedia.org/wiki/Automata_theory > Here it is in a nutshell: Languages are synonymous with computation. These can be divided into just a few types, based on how they can use state. One can observe that the complexity of an automata and its corresponding language increases dramatically with its use of state. (Turing Tarpit https://en.wikipedia.org/wiki/Turing_tarpit https://en.wikipedia.org/wiki/Turing_tarpit) You can avoid complexity by avoiding complex interactions with state. Also, always copying objects by value every time you call a function seems very expensive In the case of parallel/concurrent computation, it can be the less expensive option. < https://mechanical-sympathy.blogspot.com/2011/07/false-sharing.html https://mechanical-sympathy.blogspot.com/2011/07/false-shari... > As always, the devil is in the details, and it's all about context. So you are correct. Sometimes mutations are useful. However, sometimes, you can get a benefit from avoiding them.

didibus 10y ago

In Erlang, the pureness allows a clean split between processes and enables that clustering and hot loading magic. While it's less efficient for a single operation, it scales to handle many parallel operations way better. This is generally why pure functional is hyped. It's just easier to think of a pure functional construct, there's less possibility for mistake. No one claims it to be efficient at single operations. Though some people blame the hardware for that, as in theory, there's nothing slower about it.

pdimitar 10y ago

> Also, always copying objects by value every time > you call a function seems very expensive This is a non-point. In Erlang/Elixir everything is immutable and 95% of the time data is passed by an immutable reference thus effectively eliminating data copying. Also, if you use iolists for text processing (instead of appending strings), you absolutely will reuse all string chunks you use in the entire Erlang/Elixir OS process, even if you don't want to. It's mega-efficient. EDIT: @josevalim (Elixir's creator) explains it much better than I can, right here in this thread: https://news.ycombinator.com/item?id=13499328 https://news.ycombinator.com/item?id=13499328.