Do you find you still need variables you can change, and if so why?

Question

One of the arguments I've heard against functional languages is that single assignment coding is too hard, or at least significantly harder than "normal" programming.

But looking through my code, I realized that I really don't have many (any?) use patterns that can't be written just as well using single assignment form if you're writing in a reasonably modern language.

So what are the use cases for variables that vary within a single invocation of their scope? Bearing in mind that loop indexes, parameters, and other scope bound values that vary between invocations aren't multiple assignments in this case (unless you have to change them in the body for some reason), and assuming that you are writing in something a far enough above the assembly language level, where you can write things like

values.sum 

or (in case sum isn't provided)

function collection.sum --> inject(zero, function (v,t) --> t+v ) 

and

x = if a > b then a else b 

or

n = case s    /^\d*$/ : s.to_int   ''      : 0   '*'     : a.length   '?'     : a.length.random   else    fail "I don't know how many you want" 

when you need to, and have list comprehensions, map/collect, and so forth available.

Do you find that you still want/need mutable variables in such an environment, and if so, what for?

To clarify, I'm not asking for a recitation of the objections to SSA form, but rather concrete examples where those objections would apply. I'm looking for bits of code that are clear and concise with mutable variables and couldn't be written so without them.

My favorite examples so far (and the best objection I expect to them):

1. Paul Johnson's Fisher-Yates algorithm answer, which is pretty strong when you include the big-O constraints. But then, as catulahoops points out, the big-O issue isn't tied to the SSA question, but rather to having mutable data types, and with that set aside the algorithm can be written rather clearly in SSA:

    shuffle(Lst) ->      array:to_list(shuffle(array:from_list(Lst), erlang:length(Lst) - 1)).  shuffle(Array, 0) -> Array;  shuffle(Array, N) ->      K = random:uniform(N) - 1,      Ek = array:get(K, Array),      En = array:get(N, Array),      shuffle(array:set(K, En, array:set(N, Ek, Array)), N-1). 

2. jpalecek's area of a polygon example:

   def area(figure : List[Point]) : Float = {   if(figure.empty) return 0   val last = figure(0)   var first= figure(0)   val ret = 0   for (pt <- figure) {     ret+=crossprod(last - first, pt - first)     last = pt   }   ret } 

   which might still be written something like:

   def area(figure : List[Point]) : Float = {     if figure.length < 3         0       else         var a = figure(0)         var b = figure(1)         var c = figure(2)         if figure.length == 3             magnitude(crossproduct(b-a,c-a))           else              foldLeft((0,a,b))(figure.rest)) {                 ((t,a,b),c) => (t+area([a,b,c]),a,c)                } 

   Or, since some people object to the density of this formulation, it could be recast:

   def area([])    = 0.0   # An empty figure has no area def area([_])   = 0.0   # ...nor does a point def area([_,_]) = 0.0   # ...or a line segment def area([a,b,c]) =     # The area of a triangle can be found directly     magnitude(crossproduct(b-a,c-a)) def area(figure) =      # For larger figures, reduce to triangles and sum     as_triangles(figure).collect(area).sum  def as_triangles([])      = []  # No triangles without at least three points def as_triangles([_])     = [] def as_triangles([_,_])   = [] def as_triangles([a,b,c | rest) = [[a,b,c] | as_triangles([a,c | rest])] 

3. Princess's point about the difficulty of implementing O(1) queues with immutable structures is interesting (and may well provide the basis for a compelling example) but as stated it's fundamentally about the mutability of the data structure, and not directly about the multiple assignment issue.

4. I'm intrigued by the Sieve of Eratosthenes answer, but unconvinced. The proper big-O, pull as many primes as you'd like generator given in the paper he cited does not look easy to implement correctly with or without SSA.

---

Well, thanks everyone for trying. As most of the answers turned out to be either 1) based on mutable data structures, not on single-assignment, and 2) to the extent they were about single assignment form easily countered by practitioners skilled in the art, I'm going to strike the line from my talk and / or restructure (maybe have it in backup as a discussion topic in the unlikely event I run out of words before I run out of time).

Thanks again.

Answer 1

The hardest problem I've come across is shuffling a list. The Fisher-Yates algorithm (also sometimes known as the Knuth algorithm) involves iterating through the list swapping each item with a random other item. The algorithm is O(n), well known and long-since proven correct (an important property in some applications). But it requires mutable arrays.

That isn't to say you can't do shuffling in a functional program. Oleg Kiselyov has written about this. But if I understand him correctly, functional shuffling is O(n . log n) because it works by building a binary tree.

Of course, if I needed to write the Fisher-Yates algorithm in Haskell I'd just put it in the ST monad, which lets you wrap up an algorithm involving mutable arrays inside a nice pure function, like this:

-- | Implementation of the random swap algorithm for shuffling.  Reads a list -- into a mutable ST array, shuffles it in place, and reads out the result -- as a list.  module Data.Shuffle (shuffle) where   import Control.Monad import Control.Monad.ST import Data.Array.ST import Data.STRef import System.Random  -- | Shuffle a value based on a random seed. shuffle :: (RandomGen g) => g -> [a] -> [a] shuffle _ [] = [] shuffle g xs =      runST $ do       sg <- newSTRef g       let n = length xs       v <- newListArray (1, n) xs       mapM_ (shuffle1 sg v) [1..n]       getElems v  -- Internal function to swap element i with a random element at or above it. shuffle1 :: (RandomGen g) => STRef s g -> STArray s Int a -> Int -> ST s () shuffle1 sg v i = do   (_, n) <- getBounds v   r <- getRnd sg $ randomR (i, n)   when (r /= i) $ do     vi <- readArray v i     vr <- readArray v r     writeArray v i vr     writeArray v r vi   -- Internal function for using random numbers getRnd :: (RandomGen g) => STRef s g -> (g -> (a, g)) -> ST s a getRnd sg f = do   g1 <- readSTRef sg   let (v, g2) = f g1   writeSTRef sg g2   return v