How to Avoid the Assignment Statement (2010)

Secondly, I think there's something to be said for familiarity. I think looping is second nature to most of us not because it's superior or more intuitive, but because traditionally this is one of the first things we're all taught. If functional programming were the norm and people were taught recursion early on instead I think your notion of simplicity would differ.

I've been teaching a little bit of programming to a beginner lately, and they've often found functional approaches to problems easier to grasp than their imperative equivalents because they're more mathematical. It's like an expression of something they already know versus looping, mutability, et al which are new concepts entirely.

  def min(foo: List[int], default=None) -> Optional[int]:
      if not foo:
          return default
      cur_min = foo[0] if default is None or foo[0] < default else default
      return min(foo[1:], cur_min)

    #!/usr/bin/env python3
    from functools import reduce
    from typing import List, Optional
    
    def min_pair(min: Optional[int], val: Optional[int]) -> Optional[int]:
        if min is None or val < min:
            return val
        else
            return min
    
    def min(foo: List[int]) -> Optional[int]:
        return reduce(min_pair, foo)

My view of a program is that of a dependence graph, ideally directed acyclic. Ideally we want that graph to be as sparse as possible: good old decoupling. Mutable state (not just global variables) tend to introduce hidden dependencies, making that graph denser than what it initially appears. That can be a killer.

Surprisingly though, as years pass, I am less and less certain what the "correct" structure of a program should be. I sure want to keep it small, simple, easy to maintain… but the method to achieve this still eludes me.

    let list_min l = 
      reduce min l

EDIT: for completeness, here's the definition of `reduce` and `min`:

    let reduce op l =
      match l with
      | [] -> invalid_arg "reduce: empty list"
      | [x] -> x
      | hd::tl -> op (hd) (reduce op tl)
    
    let min a b = 
      if a < b then a else b

In pseudo-Haskell notation:

    min1 : Int -> List Int -> Int
    min1 def Nil = def
    min1 def (Cons x xs) = min1 (def if def <= x else x) xs

    min : List Int -> Maybe Int
    min Nil = None
    min (Cons x xs) = min1 x xs

    def min(foo):
        it = iter(foo)
        try:
            m = next(it)
        except StopIteration:
            return None

        for val in it:
            if val < m:
                m = val

        return m

Here are two recursive ways to write a min function:

Idiomatic and structured, using (Maybe . Min) monoid:

    min = foldMap (Just . Min)

Unstructured, ad-hoc

    minimum [] = Nothing
    minimum (x:xs) = case minimum xs of Nothing -> Just x; Just y -> Just (min x y)

In Scala the idiomatic approach would be to favor the immutable/recursive version.

    def min(foos: List[Int]): Option[Int] = foos match {
      case Nil => None
      case x :: Nil => Some(x)
      case x :: xs =>
        min(xs).filter(_ < x) orElse Some(x)
    }

To take full advantage of the functional paradigm most settle for logarithmic access with tries.

This allows mutation to remain the performance optimisation it is, without allowing it to seep into the design of systems, which is where it causes badness.

As far as I know, Haskell is one of the few languages (if not the only one) that supports local mutation that is guaranteed to not be visible in any way to the caller.

Using separate variables instead of reusing the same variable will sometimes actually increase the optimizations that compilers can do. Why? Because the version where you overwrite the variable is introducing additional constraints (e.g. keeping X1 and X2 in the very same stack slot called X) that have costs, but whose semantics you aren’t necessarily (or even usually!) relying upon.

For example: you know all that spare register spill space in the x64 calling convention that you’re allocating either way, and which deallocates as a block on function exit? Can’t make efficient use of that if you’re telling the compiler it has to keep both of your pointers successively in the same memory address!

On the other hand, the opposite is also true: sometimes overwriting a variable will free the compiler from a constraint it was under. This mostly comes about as the result of X1 and X2 both holding a shared or overlapping pointer, introducing aliasing (as often happens in the pure-functional data structures OP advocates for.) By overwriting X1 with X2 (or, equivalently, by freeing X1 as soon as you’re done with it!) you can allow the compiler to be more confident that nothing will access the shared pointer through X1.Y any more, only through X2.Y—which may allow e.g. smart pointer classes to elide a synchronization point.

(Note that this assumes a language with a model where a variable directly relates to memory, such that assigning to the same variable implies assigning to the same memory. This is true in most low-level languages, but not in functional languages; in e.g. Elixir, a second assignment to the same variable is actually creating a second variable with a mangled name, and leaving it to the compiler’s lifetime analysis to figure out that the first one is dead after that point.)

I believe I didn't want to scare readers away. But more importantly, functional programming is more than just removing the assignment statement. If you take a language and just remove the assignment statement, the language you get isn't functional, it's just crippled.

Functional programming involves other techniques to compensate. Higher order functions are critical, and often used to hide recursion under the rug (see map & reduce). I have a more complete guide to functional programming there: http://loup-vaillant.fr/tutorials/from-imperative-to-functio...

I did like the article and how the author writes so simply. To the author's credit, right below, they do have the section on "When you can't help it", which if you do need insertion like that and performance matters, probably best to use a mutable data structure.