8 ms·

I don't really get the joke. Generally functional languages will share more data than imperative languages, and therefore will copy less data. In an imperative

• TylerE 13y ago
  No, typically functional languages end up copying more, not less, since typical algorithms will e.g. return a fresh copy of the modified structure - the purists detest mutation. The benefits of data sharing, are, imo, overstated outside of a few niche, datastore-y type areas.
  • trevorhartman 13y ago
    They may appear to be returning a fresh copy, but internally much of the structure is shared rather than copied. See Persistent data structure: http://en.wikipedia.org/wiki/Persistent_data_structure http://en.wikipedia.org/wiki/Persistent_data_structure
    • TylerE 13y ago
      Much is shared, yes, but compared to a traditional approach with static arrays, there is a _lot_ of copying in a typical FP approach.
      • mercurial 13y ago
        Sure, but in Haskell, a lot of it will be deforested by the compiler.
  • chrismonsanto 13y ago
    Functional languages generally encourage the use of persistent data structures. Algorithms that modify persistent data structures do not generally return 'fresh copies'. If you use the proper data structures in Haskell or Clojure your 'typical algorithms' will not return fresh copies. That being said, whether data sharing is a good thing or not depends on the situation. For example, copying to a cache can expose more memory parallelism in an application. I feel like you are taking this opportunity to take a jab at FP here ("the purists detest mutation"). While FP is my preferred paradigm of development, I wasn't trying to push it on anyone--I was merely making a technical point.
    • TylerE 13y ago
      You might be surprised just how much churn there is if you look at the source of, for instance, Haskell's Data.Map, which in the name of immutability is implemented as a balanced binary-tree representation, rather than the more common hash table. Many operations that are amortized O(1) with a hash table are O(log N) with a balanced B-tree, since for instance after an update a all the sub-trees around the update site will be made afresh, since the balancing will change.
      • cgag 13y ago
        Somehow the difference between O(1) and O(log32 n) has never actually been an issue for me in Clojure.
        • detrino 13y ago
          Have you profiled the difference? Do you use these containers in places where it matters?
          • cgag 13y ago
            I'm sure there is a difference, I just don't care. They're still damn fast and the semantics of immutability would be worth quite a large speed difference to me. If you do happen to be doing something where the difference is truly going to matter, or you're writing a library anticipating needing that kind of performance, using mutability internally in your functions isn't discouraged as long as they remain referentially transparent: http://clojure.org/transients http://clojure.org/transients
            • tel 13y ago
              And Haskell's ST monad.
            • orclev 13y ago
              That's a good point. People don't understand that functional purity in Haskell, while a nice goal, isn't a law, you can break it if you have a good reason to. IO is sort of the canonical example, it isn't there to prevent you from doing IO, it's there to act as a giant warning sign that either this function, or one of the functions it uses isn't pure. Likewise mutable data structures while not the default, can be implemented in Haskell, they just have some caveats attached and shouldn't be used lightly. In other words, all things being equal, use the immutable data structure, but if you have a good reason to, you can use a mutable data structure instead, just be sure you know what you're getting into.
  • tych0 13y ago
    While I agree that a functional implementation of something usually copies more, it's a little disingenuous to say that most algorithms return a "fresh copy" of a structure. Most of the collections in most of the functional runtimes use clever tricks (hash array mapped tries, hash consing, etc.) to avoid copying the whole structure. In the face of these techniques (and others, e.g. re-structuring things to use zippers and being clever manually or whatever), I suspect the actual amount of redundant data might be quite a bit less than you might think.
  • SilasX 13y ago
    At the level of source code logic it appears to be copying and returning a new data structure. That doesn't mean the compiled, optimized code is performing all the copies that the the program appears to be doing. Pure FP = don't mutate variables in the program. Of course the actual implementation can reuse memory blocks or else pure FPers would have to keep buying new memory!
    • TylerE 13y ago
      Pure FP doesn't have variables. It has bindings.
      • groovy2shoes 13y ago
        Function parameters are variables even in pure FP. If your definition of variable requires assignment, then even mathematics doesn't have variables.
        • Aloisius 13y ago
          Sure it does. The summation sigma has a variable right under it. Though they like to call it the index of summation, it is a variable with assignment.
          • nightski 13y ago
            Pretty sure summation definition is recursive. So no assignment/mutation is necessary.
      • alipang 13y ago
        What do the bindings bind then? So, no, even in pure functions like f x = x + 1 x is a bound variable. It doesn't 'vary' in the sense that the value it refers to can be mutated, as in a imperative language, but it varies between calls to the function f.
        • TylerE 13y ago
  • mbrock 13y ago
    What kind of evidence do you have for this claim? The amount of copying in a functional or imperative program depends on how they're written, how they're optimized, and how they've compiled or evaluated. For example, in programs with mutable state, it's not uncommon for modules to return deep copies of objects to avoid mutation-related bugs. Java's String objects are immutable precisely to avoid having to do this.
• Fishkins 13y ago
  He's just saying that, in pure functional code, "updating" a data structure means creating a new copy of it with the desired changes instead of actually changing the structure in place. Of course, since the structures are immutable, large parts of them can often be reused. That's not how it's presented to the language user, though.
• detrino 13y ago
  It's not so black and white, if you don't actually need multiple versions of a data structure, then you are strictly copying more. There are scenarios where you do want versioning, of course, but this is why its good to have choices.
• laureny 13y ago
  > Generally functional languages will share more data than imperative languages, and therefore will copy less data. It's the opposite: functional programs prefer immutable data and the only way to achieve this is to copy a lot more data than you would if you were just overwriting existing objects.