Explaining functional programming to object-orient

问题:

What are some good examples that I can use to explain functional programming?

The audience would be people with little programming experience, or people who only have object-oriented experience.

回答1:

The audience would be people with little programming experience,

Is it really possible to explain functional programming, let along OO or procedural or any paradigm of programming to people without much programming experience?

or people who only have object-oriented experience.

Well probably the best examples would be converting known design patterns into their functional equivalent. Let's take the canonical example of converting a list of ints to a list of strings:

using System;

namespace Juliet
{
    interface IConvertor<T, U>
    {
        U Convert(T value);
    }

    class Program
    {
        static U[] Convert<T, U>(T[] input, IConvertor<T, U> convertor)
        {
            U[] res = new U[input.Length];
            for (int i = 0; i < input.Length; i++)
            {
                res[i] = convertor.Convert(input[i]);
            }
            return res;
        }

        class SquareInt : IConvertor<int, string>
        {
            public string Convert(int i)
            {
                return (i * i).ToString();
            }
        }

        class ScaleInt : IConvertor<int, string>
        {
            readonly int Scale;

            public ScaleInt(int scale)
            {
                this.Scale = scale;
            }

            public string Convert(int i)
            {
                return (i * Scale).ToString();
            }
        }

        static void Main(string[] args)
        {
            int[] nums = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

            string[] squared = Convert<int, string>(nums, new SquareInt());
            string[] tripled = Convert<int, string>(nums, new ScaleInt(3));
        }
    }
}

Its simple, readable, object-oriented, its even generic so it works for any arbitrary types, so what's the problem? For a start, its bloated: I have an interface definition and two interface implementations. What if I need another conversion? Well, I need another interface implementation -- it can get out of hand quickly.

When you think about it, the IConvertor<T, U> class is just a wrapper around a single function called Convert -- the class literally exists to help us pass Convert to other functions. If you can understand this much, then you already understand the basic principles behind functions as first-class values -- functional programming is all about passing functions to other functions in pretty much the same way you pass a person or an int or a string.

People usually prefer functional programming because it helps them avoid single-method interfaces and implementations. Instead of passing a class, we just pass a function by name or anonymously:

using System;

namespace Juliet
{
    class Program
    {
        static U[] Convert<T, U>(T[] input, Func<T, U> convertor)
        {
            U[] res = new U[input.Length];
            for (int i = 0; i < input.Length; i++)
            {
                res[i] = convertor(input[i]);
            }
            return res;
        }

        static string SquareInt(int i)
        {
            return (i * i).ToString();
        }

        static void Main(string[] args)
        {
            int[] nums = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

            string[] squared = Convert<int, string>(nums, SquareInt); // pass function by name
            string[] tripled = Convert<int, string>(nums, i => (i * 3).ToString()); // or pass anonymously
        }
    }
}

Alright, so now we have the exact same program in much fewer lines of code, its readable, and its very evident what its doing.

Now someone might say "that's a neat trick, but when would I use it" -- there are plenty of cases when you'd want to pass functions around like this. It gives you a lot more power to abstract your programs control flow in novel ways. Adapted from an example shown here, consider a class which handles files:

class FileFunctions
{
    internal void SaveFile()
    {
        SaveFileDialog fileDialog = new SaveFileDialog();
        fileDialog.Filter = "Text files (*.txt)|*.txt|All files (*.*)|*.*";
        if (fileDialog.ShowDialog() == DialogResult.OK)
        {
            File.AppendAllText(fileDialog.FileName, MyDocument.Data);
        }
    }

    internal void WriteFile()
    {
        OpenFileDialog fileDialog = new OpenFileDialog();
        fileDialog.Filter = "Text files (*.txt)|*.txt|All files (*.*)|*.*";
        if (fileDialog.ShowDialog() == DialogResult.OK)
        {
            MyDocument.Data = File.ReadAllText(fileDialog.FileName);
        }
    }
}

Yuck. The code is repetitious, but its performing operations on different classes and invoking different methods. How would you abstract away the duplicated code in the OO universe? In functional programing, it's trivial:

class FileFunctions
{
    internal void ShowDialogThen(FileDialog dialog, Action<FileDialog> f)
    {
        dialog.Filter = "Text files (*.txt)|*.txt|All files (*.*)|*.*";
        if (dialog.ShowDialog() == DialogResult.OK)
        {
            f(dialog);
        }
    }

    internal void SaveFile()
    {
        ShowDialogThen(
            new SaveFileDialog(),
            dialog => File.AppendAllText(dialog.FileName, MyDocument.Data));
    }

    internal void WriteFile()
    {
        ShowDialogThen(
            new OpenFileDialog(),
            dialog => { MyDocument.Data = File.ReadAllText(dialog.FileName); });
    }
}

Awesome.

回答2:

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.

回答3:

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.

回答4:

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.

回答5:

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

回答6:

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! :)

回答7:

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!

回答8:

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);
        }
    }
}

回答9:

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.

回答10:

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

回答11:

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()

回答12:

New answer. This will work for both non-programming power users and OO programmers.

Point out that Excel is functional.

Each cell in a spreadsheet is a variable that contains a function which declares a relationship between other cells/variables.