Explaining functional programming to object-oriented programmers and less technical people

Functional Programming for the Object-Oriented Programmer by by Brian Marick. I'm not associated, or anything, just came by it right now:

https://leanpub.com/fp-oo

Uncle Bob likes it! :)

The ones with little programming experience are probably easier, since they won't have as many programming concepts to get in the way: functional programming is very similar to mathematical functions as expressions, so show them some math.

For the OO crowd, you could show how closures are like encapsulation, and thus how functional programming encompasses OOP. You could also show how useful higher-order functions are, in particular how they cause some OOP patterns (such as the Strategy and Template patterns, and the Visitor pattern in languages with multimethods) fade away into the language (Peter Norvig asserts that 16 of the 23 GOF patterns are simpler in Dylan and Lisp). As a counterpart, message-passing based OOP (rather than the CLOS approach) is a pattern in FP that is invisible in OOP.

Demonstrate how easy it is to write general arithmetic expressions, along with function composition and differentiation, as programming constructs and you've got both of them.

You may or may not want to show the OO people CLOS's multimethods; they'll either riot or have a geekgasm. Either way, it's likely to be messy.

Some other possibilities to show how flexible FP is: lazy evaluation can be implemented using nullary anonymous functions. FP can support both class-based and prototype-based OOP. There are plenty of other examples (e.g. continuation-passing style), but they generally require familiarity with FP before learning.

SICP has plenty of interesting examples and problems; it should prove inspirational.

Compare it to sentence structure.

I hit the ball, catch the ball, throw the ball:
Procedural
Hit(ball)
Catch(ball)
Throw(ball)

OO
Ball.Hit()
Ball.Catch()
Ball.Throw()

Immutable data structures

You know, I've commented to people about functional programming before and have brought up the whole "immutable data structure" thing. This usually blows people's mind -- how are you supposed to add something to a collection if you can't actually add it?

The immediate answer is "well you don't, you just create a new version of your data structure with the object added", and the immediate response is "that doesn't sound very efficient". Well it is.

Immutable stack

Canonical immutable data structure is an immutable stack, which is basically a node containing two readonly values: a head and a tail. Pushing and popping from the stack are O(1). Indexed lookups, inserts/deletes in the middle of the list require O(n) time, which incidentally is the same as a mutable stack.

using System;

namespace Juliet
{
    public abstract class Stack<T>
    {
        public static readonly Stack<T> Empty = new Nil();

        public abstract T Head { get; }
        public abstract Stack<T> Tail { get; }
        public abstract bool IsEmpty { get; }
        public Stack<T> Push(T value) { return new Cons(value, this); }
        public Stack<T> Append(Stack<T> other)
        {
            if (this.IsEmpty) { return other; }
            else { return new Cons(this.Head, this.Tail.Append(other)); }
        }

        sealed class Nil : Stack<T>
        {
            public override T Head { get { throw new Exception("Empty stack"); } }
            public override Stack<T> Tail { get { throw new Exception("Empty stack"); } }
            public override bool IsEmpty { get { return true; } }
        }

        sealed class Cons : Stack<T>
        {
            private readonly T _head;
            private readonly Stack<T> _tail;

            public override T Head { get { return _head; ; } }
            public override Stack<T> Tail { get { return _tail; } }
            public override bool IsEmpty { get { return false; } }

            public Cons(T head, Stack<T> tail)
            {
                _head = head;
                _tail = tail;
            }
        }
    }

    class Program
    {       
        static void Main(string[] args)
        {
            var s = Stack<int>.Empty.Push(1).Push(2).Push(3).Push(4).Push(5);
            while (!s.IsEmpty)
            {
                Console.Write("{0} ", s.Head);
                s = s.Tail;
            }
            Console.ReadKey(true);
        }
    }
}

Immutable AVL Tree

Most people aren't impressed by stacks because it isn't a "serious" data structure, but AVL trees and other self-balancing data structures are pretty impressive. Trees are actually very easy to write as immutable data structures.

This version supports O(log n) inserts and lookups, delete isn't shown but it can be implemented in O(log n) as well. In other words, the immutable AVL tree has the same computational complexity as as its mutable variant:

using System;
using System.Linq;

namespace Juliet
{
    public abstract class AvlTree<T>
        where T : IComparable<T>
    {
        static AvlTree<T> Make(AvlTree<T> left, T value, AvlTree<T> right)
        {
            return new Node(left, value, right, Math.Max(left.Height, right.Height) + 1, left.Count + right.Count + 1);
        }

        public static readonly AvlTree<T> Empty = new Nil();

        protected abstract AvlTree<T> Left { get; }
        protected abstract AvlTree<T> Right { get; }
        protected abstract T Value { get; }
        public abstract int Height { get; }
        public abstract int Count { get; }

        public bool Contains(T v)
        {
            if (this.Height == 0) { return false; }
            else
            {
                int compare = v.CompareTo(this.Value);
                if (compare < 0) { return this.Left.Contains(v); }
                else if (compare > 0) { return this.Right.Contains(v); }
                else { return true; }
            }
        }

        public AvlTree<T> Insert(T v)
        {
            if (this.Height == 0) { return Make(this, v, this); }
            else
            {
                int compare = v.CompareTo(this.Value);
                if (compare < 0) { return Balance(Make(this.Left.Insert(v), this.Value, this.Right)); }
                else if (compare > 0) { return Balance(Make(this.Left, this.Value, this.Right.Insert(v))); }
                else { return this; }
            }
        }

        private static AvlTree<T> Balance(AvlTree<T> tree)
        {
            if (tree.Height > 0)
            {
                int outerBalanceFactor = tree.Left.Height - tree.Right.Height;
                if (outerBalanceFactor <= -2 && tree.Right.Height > 0) // right-side too heavy
                {
                    int innerBalanceFactor = tree.Right.Left.Height - tree.Right.Right.Height;
                    if (innerBalanceFactor <= -1) // right-right case
                    {
                        return LeftRotate(tree);
                    }
                    else if (innerBalanceFactor >= 1) // right-left case
                    {
                        return DoubleLeftRotate(tree);
                    }
                }
                else if (outerBalanceFactor >= 2 && tree.Left.Height > 0) // left-side too heavy
                {
                    int innerBalanceFactor = tree.Left.Left.Height - tree.Left.Right.Height;
                    if (innerBalanceFactor <= -1) // left-left case
                    {
                        return DoubleRightRotate(tree);
                    }
                    else if (innerBalanceFactor >= 1) // left-right case
                    {
                        return RightRotate(tree);
                    }
                }
            }
            return tree;
        }

        private static AvlTree<T> LeftRotate(AvlTree<T> tree)
        {
            if (tree.Height > 0 && tree.Right.Height > 0)
            {
                T p = tree.Value;
                T q = tree.Right.Value;
                AvlTree<T> a = tree.Left;
                AvlTree<T> b = tree.Right.Left;
                AvlTree<T> c = tree.Right.Right;
                return Make(Make(a, p, b), q, c);
            }
            return tree;
        }

        private static AvlTree<T> RightRotate(AvlTree<T> tree)
        {
            if (tree.Height > 0 && tree.Left.Height > 0)
            {
                T q = tree.Value;
                T p = tree.Left.Value;
                AvlTree<T> a = tree.Left.Left;
                AvlTree<T> b = tree.Left.Right;
                AvlTree<T> c = tree.Right;
                return Make(a, p, Make(b, q, c));
            }
            return tree;
        }

        private static AvlTree<T> DoubleLeftRotate(AvlTree<T> tree)
        {
            if (tree.Height > 0)
            {
                // right-rotate right child, left-rotate root
                return LeftRotate(Make(tree.Left, tree.Value, RightRotate(tree.Right)));
            }
            return tree;
        }

        private static AvlTree<T> DoubleRightRotate(AvlTree<T> tree)
        {
            if (tree.Height > 0)
            {
                // left-rotate left child, right-rotate root
                return RightRotate(Make(LeftRotate(tree.Left), tree.Value, tree.Right));
            }
            return tree;
        }


        sealed class Nil : AvlTree<T>
        {
            protected override AvlTree<T> Left { get { throw new Exception("Empty tree"); } }
            protected override AvlTree<T> Right { get { throw new Exception("Empty tree"); } }
            protected override T Value { get { throw new Exception("Empty tree"); } }
            public override int Height { get { return 0; } }
            public override int Count { get { return 0; } }
        }

        sealed class Node : AvlTree<T>
        {
            readonly AvlTree<T> _left;
            readonly AvlTree<T> _right;
            readonly T _value;
            readonly int _height;
            readonly int _count;

            protected override AvlTree<T> Left { get { return _left; } }
            protected override AvlTree<T> Right { get { return _right; } }
            protected override T Value { get { return _value; } }
            public override int Height { get { return _height; } }
            public override int Count { get { return _count; } }

            public Node(AvlTree<T> left, T value, AvlTree<T> right, int height, int count)
            {
                _left = left;
                _right = right;
                _value = value;
                _height = height;
                _count = count;
            }
        }
    }

    class Program
    {       
        static void Main(string[] args)
        {
            var tree = AvlTree<int>.Empty;
            foreach(int i in Enumerable.Range(1, 1000000).OrderBy(_ => Guid.NewGuid()))
            {
                tree = tree.Insert(i);
            }

            Console.Write("Tree height: {0}, tree count: {1}", tree.Height, tree.Count);

            Console.ReadKey(true);
        }
    }
}

Why Functional Programming Matters by John Hughes has some good examples, but even better, it explains the why of functional programming languages, not just the how. You could do much worse than build a presentation based on that paper!

OO is about nouns while functional programming is about verbs. Read this rather good blog on the subject by Steve Yegge.

We used this tutorial for Haskell, and it worked very well, its light hearted but does a good job with explanations:

Learn you a Haskell for Great Good

I don't think you can, frankly. Functional programming (like 'good' OO programming, vs. 'procedural with classes') requires a mental model shift. You just can't understand it as a procedural coder without actually taking the time and working through using it.

If you really want someone to understand functional programming, get them a copy of the Little Schemer or some other equivalent book, and have them sit down and work through the exercises. Nothing else will help them build the necessary mental model.

It might be easier to describe functional programming by its fundamental characteristics first:

1. Functions (obviously)
2. There are no side effects
3. Immutability
4. Recursion is very important
5. Very Parallelizable

Of these, the most important characteristic is the notion of no side effects, as the other characteristics follow from that.

Functional programming is used in places you might not expect. It is used to run traffic lights and communications switches (Ericsson switches run Erlang), for example.

Try looking at this article called Functional Programming for the Rest of Us, below is an excerpt.

In this article I will explain the most widely used ideas from functional languages using examples written in Java (yes, you could write functional programs in Java if you felt particularly masochistic). In the next couple of sections we'll take Java as is, and will make modifications to it to transform it into a useable functional language. Let's begin our quest.