Dynamic+imperative wins over type-Nazi-ist+functional?

jbone at place.org jbone at place.org
Mon Oct 20 21:28:49 PDT 2003

A rather mind-boggling post from LtU, for the theorists on the list and  
the practitioners that care about how hard they have to work. ;-)

So, intuitive rant:  first, I appreciate type-checking when I know what  
I'm doing concretely, but abhor it when I'm exploring or abstracting.   
I've always recognized a certain beauty in Haskell (and its precursor,  
Miranda) but...   my God.... writing a few lines in Haskell is an  
undertaking beyond toy mathematical / CS101 constructs, while Python  
(or even more so, the UNIX shell --- any shell) has always been much  
less tedious, much more terse, and a lot more fun.

Erik Meijer (mentioned in a recent previous post for his efforts in  
abstracting across and unifying a "language" or expressive grammar for  
relational tables, object-oriented class extents, and XML documents)  
has an interesting rant ref'd by LtU of which the premise is that  
certain imperative generator+looping based constructs --- or even list  
comprehensions---are in somewhat "more" abstract than their equivalent  
and functionally-expressed (particularly w/ strong explicit typing)  

Note that he calls out Python as leading the herd in finding the  
expressive Pareto optimal solution for working programmers.  Yay!



Visual Basic Programmers Love Anamorphisms

Most functional programmers are familiar with the notions of folding  
(catamorphisms) and unfolding (anamorphisms). These concepts are the  
rice and potatoes of every self-respecting functional programmer. In  
case this all sounds greek to you, stop reading now and buy one of the  
few remaining second-hand copies of Introduction to Functional  
Programming by Bird and Wadler (I still consider this book a great  
improvement on its successors) and then move on to the more advanced  

While it is amazing that all this theory applies to arbitrary  
data-types and that you can even lift it to the meta-level and do  
polytypic programming, in practice lists is still the most versatile  
type of them all (sorry that I send you on a detour to read all that  
other stuff ;-)

Using list-comprehensions, or map, filter, and fold/unfold you can  
express lots of interesting functions on lists (if you want to know the  
precise answer ask Jeremy Gibbons, Graham Hutton, Thorsten Altenkirch).  
What many people do not realize, is that Visual Basic, C# and Java  
programmers use the same concepts, and in contrast to functional  
programmers, they deeply appreciate unfold!

Let's look at the following definition of unfold in Haskell

     unfoldr :: (b -> Maybe (a,b)) -> b -> [a]
     unfoldr f b = case (f b) of
                     Nothing -> []
                     Just (a,b) -> a : unfoldr f b

The unfold function takes a generator function f of type b ->  
Maybe(a,b) and a seed value b of type b and generates the list a0, a1,  
... by repeatedly applying the generator function f to the next seed  
value bi, roughly:

   b -f-> (a0,b0) -f-> (a1,b1)
     -f-> ...

Now let's look at the C# IEnumerator and the Java Enumeration  
interfaces (C# also has an additional IEnumerable factory interface  
that allows you to regenerate a list multiple times):

   // this is Java
   interface Enumeration


         boolean hasMoreElements()

         T nextElement()


         // this is C#

         public interface IEnumerator

             bool MoveNext()

             T Current { get ; }

             void Reset() // usually not implemented


Even if you are not deep into object encodings using existantial types  
and co-algebras, it should be immediately clear that the C# and Java  
interfaces are just the imperative versions of our functional unfold.  
The boolean in MoveNext/hasMoreElements corresponds to the Maybe, and  
nextElement/Current corresponds to consing a onto the result list.

To be honest, I think that the imperative version of unfold is more  
elegant, more abstract, and more efficient than the functional one. The  
imperative formulation uses two methods in its contract instead of the  
clunky Maybe construction. It hides the type of the actual state of the  
generator, which would require existential types, or monads in the  
functional version. The imperative variant does not actually create a  
list; when consuming the list generated by an unfold in the purely  
functional program, the very first thing you are going to do is to  
deconstruct the cons cell that was just allocated by the unfold.  
Bertrand Meyer notes that for object-oriented software construction the  
reality that it addresses is, at best, a cousin twice removed.  
Functional programs often model models, hence the reality that a  
functional program addresses is, at best, a cousin three times removed.

When it comes down to actually defining types or functions that  
implement unfolds, the imperative programmer is also way ahead of the  
poor functional programmer. For example here is how you would define  
the FromTo anamorphism in C# using the new yield statement and in  
Haskell using the unfold construct:


         FromTo(int n, int m) {

         for(int i=n; i<=m;i++) yield return i;


         fromTo n m = let next i = if i>m then Nothing else Just(i,i+1)

         in unfoldr next n

I know what I prefer to write! Note that the seasoned Haskell  
programmer would probably write [n..m] instead of the complicated  
unfold, but that is just delaying execution because soon you do have to  
write an unfold, or as most people will do, resort to using explicit  

The imperative and the functional programmer are equally well off when  
it comes to consuming list, although I expect that many programmers  
find it easier to just write

  int y = 0; foreach(int x in xs) y += x;

instead of trying to remember which of the three variants foldr, foldl  
or foldl' to use (picking the wrong one is quite common a trap for  
Haskellers to fall into) and writing the following expression that is  
just 7 characters shorter then the C# code:

   y = foldl' (\y -> x -> y+x) 0 xs

Merging and transforming lists is only case where functional  
programming still wins. Map/filter/fold and list comprehension allow  
very concise descriptions of list transformers, such as the following  
version of quicksort:

   qsort []     = []
   qsort (x:xs) = [y | y <- xs, y < x]++ [x] ++ [y | y <- xs, y >= x]

While this is a nice specification, it is a very naive implementation.  
Its cuteness quickly dissolves when you do try to make it efficient,  
i.e. by using a more efficient concatenation of lists (carelessly using  
list concatenation ++ is another trap many Haskellers fall into) or by  
doing the sort in situ.

Most importantly many list transformers, including map and filter can  
be defined as both catamorphisms and anamorphisms, and list  
comprehensions are ultra sweet, but very thin syntactic sugar on top of  
the base language. In principle there is nothing that prevents special  
list transformers and comprehensions from being introduced into  
imperative languages as well. We know how to do it. In fact, as is the  
case for many other features, Python has already taken the lead in this.

Pure functional programmers, your days are numbered. The grim reaper is  
knocking at your door.

10/19/2003 11:35 PM 

More information about the FoRK mailing list