What task is best done in a functional programming

Question

I've just recently discovered the functional programming style and I'm convinced that it will reduce development efforts, make code easier to read, make software more maintainable. However, the problem is I sucked at convincing anyone.

Well, recently I was given a chance to give a talk on how to reduce software development and maintenance efforts, and I wanted to introduce them the concept of functional programming and how it benefit the team. I had this idea of showing people 2 set of code that does exactly the same thing, one coded in a very imperative way, and the other in a very functional way, to show that functional programming can made code way shorter, easier to understand and thus maintainable. Is there such an example, beside the famous sum of squares example by Luca Bolognese?

Answer 1

I came up with a little trick recently to make lambdas, passed into my extension methods look more F# ish. Here it goes:

What I wanted to do was something like:

3.Times(() => Console.WriteLine("Doin' it"));

Now the extension method for that is easily implemented:

    public static void Times(this int times, Action action)
    {
        Enumerable.Range(1, times).ToList().ForEach(index => action());
    }

What I didn't like is that I am specifying the index here: ForEach(index => action()) although it never is used, so I replaced it with a _ and got ForEach(_ => action())

That's nice, but now I was motivated to have my calling code look similar

(I never liked the "()" at the beginning of the lambda expression), so instead of: 3.Times(() => ...); I wanted 3.Times(_ => ...); The only way to implement this was to pass a fake parameter to the extension method, which never gets used and so I modified it like so:

    public static void Times(this int times, Action<byte> action)
    {
        Enumerable.Range(1, times).ToList().ForEach(_ => action(byte.MinValue));
    }

This allows me to call it like this:

3.Times(_ => Console.WriteLine("Doin' it"));

Not much of a change, but I still enjoyed, that it was possible to make that little tweak so easily and at the same time removing the "()" noise makes it much more readable.

Answer 2

A simple example of a task that is often easiest done in a functional style is the transformation of data from one form to another. "Sum of squares" is a trivial example of data transformation. Luca's talk at last year's PDC showed how to use this sort of data transformation for something more practical, downloading and analyzing stock quotes. The demo is done in F#, but the concepts are the same and can be applied to C# or most other programming languages.

http://channel9.msdn.com/pdc2008/TL11/

Answer 3

Algorithms involving backtracking search and simplifying undo support in GUIs are two places I've used functional style in practice.

Answer 4

Not really answering the question, but this is a very good link for those who want to know about functional programming in C#

http://blogs.msdn.com/b/ericwhite/archive/2006/10/04/fp-tutorial.aspx

Answer 5

If by the 'functional style' you mean the usage of concepts like 'map', 'apply', 'reduce', 'filter', lambda functions and list comprehensions, then it should be evident that code that has to deal with operations on lists is almost always more concise when written in the 'functional style'. But if you're mixing 'functional style' with imperative code in a mostly imperative language, it really is just a matter of style.

In python for example, you can reimplement the Haskell qsort crackmigg posted like so:

def qsort(list):
    if list == []:
        return []
    else:
        x = list[0]; xs = list[1:]
        return qsort(filter(lambda y: y<x, xs)) + [x] + qsort(filter(lambda y: y>= x, xs))

Although writing the last line as

return qsort([y for y in xs if y<x]) + [x] + qsort([y for y in xs if y>=x])

is arguably more 'pythonic'.

But this is obviously more concise than the implementation here:

http://hetland.org/coding/python/quicksort.html

Which, incidentally, is how I would have thought about implementing it before I learned Haskell.

The functional version is extremely clear if and only if you are acclimated to functional programming and grok what filter is going to do as easily as the well-worn C++ programmer groks a for loop without even having to think much about it. And that's clearly what the real issue at stake here: functional 'style' programming is a completely different mindset. If the people you work with aren't used to thinking recursively, and aren't the type to get excited about, not just a new technology, but a whole other way of thinking about solving their problems, then any amount of code comparisons isn't going to win them over.

Answer 6

I've just recently discovered the functional programming style [...] Well, recently I was given a chance to give a talk on how to reduce software development efforts, and I wanted to introduce the concept of functional programming.

If you've only just discovered functional programming, I do not recommend trying to speak authoritatively on the subject. I know for the first 6 months while I was learnig F#, all of my code was just C# with a little more awkward syntax. However, after that period of time, I was able to write consistently good code in an idiomatic, functional style.

I recommend that you do the same: wait for 6 months or so until functional programming style comes more naturally, then give your presentation.

I'm trying to illustrate the benefits of functional programming, and I had the idea of showing people 2 set of code that does the same thing, one coded in a very imperative way, and the other in a very functional way, to show that functional programming can made code way shorter, easier to understand and thus maintain. Is there such example, beside the famous sum of squares example by Luca Bolognese?

I gave an F# presentation to the .NET users group in my area, and many people in my group were impressed by F#'s pattern matching. Specifically, I showed how to traverse an abstract syntax tree in C# and F#:

using System;

namespace ConsoleApplication1
{
    public interface IExprVisitor<t>
    {
        t Visit(TrueExpr expr);
        t Visit(And expr);
        t Visit(Nand expr);
        t Visit(Or expr);
        t Visit(Xor expr);
        t Visit(Not expr);

    }

    public abstract class Expr
    {
        public abstract t Accept<t>(IExprVisitor<t> visitor);
    }

    public abstract class UnaryOp : Expr
    {
        public Expr First { get; private set; }
        public UnaryOp(Expr first)
        {
            this.First = first;
        }
    }

    public abstract class BinExpr : Expr
    {
        public Expr First { get; private set; }
        public Expr Second { get; private set; }

        public BinExpr(Expr first, Expr second)
        {
            this.First = first;
            this.Second = second;
        }
    }

    public class TrueExpr : Expr
    {
        public override t Accept<t>(IExprVisitor<t> visitor)
        {
            return visitor.Visit(this);
        }
    }

    public class And : BinExpr
    {
        public And(Expr first, Expr second) : base(first, second) { }
        public override t Accept<t>(IExprVisitor<t> visitor)
        {
            return visitor.Visit(this);
        }
    }

    public class Nand : BinExpr
    {
        public Nand(Expr first, Expr second) : base(first, second) { }
        public override t Accept<t>(IExprVisitor<t> visitor)
        {
            return visitor.Visit(this);
        }
    }

    public class Or : BinExpr
    {
        public Or(Expr first, Expr second) : base(first, second) { }
        public override t Accept<t>(IExprVisitor<t> visitor)
        {
            return visitor.Visit(this);
        }
    }

    public class Xor : BinExpr
    {
        public Xor(Expr first, Expr second) : base(first, second) { }
        public override t Accept<t>(IExprVisitor<t> visitor)
        {
            return visitor.Visit(this);
        }
    }

    public class Not : UnaryOp
    {
        public Not(Expr first) : base(first) { }
        public override t Accept<t>(IExprVisitor<t> visitor)
        {
            return visitor.Visit(this);
        }
    }

    public class EvalVisitor : IExprVisitor<bool>
    {
        public bool Visit(TrueExpr expr)
        {
            return true;
        }

        public bool Visit(And expr)
        {
            return Eval(expr.First) && Eval(expr.Second);
        }

        public bool Visit(Nand expr)
        {
            return !(Eval(expr.First) && Eval(expr.Second));
        }

        public bool Visit(Or expr)
        {
            return Eval(expr.First) || Eval(expr.Second);
        }

        public bool Visit(Xor expr)
        {
            return Eval(expr.First) ^ Eval(expr.Second);
        }

        public bool Visit(Not expr)
        {
            return !Eval(expr.First);
        }

        public bool Eval(Expr expr)
        {
            return expr.Accept(this);
        }
    }

    public class PrettyPrintVisitor : IExprVisitor<string>
    {
        public string Visit(TrueExpr expr)
        {
            return "True";
        }

        public string Visit(And expr)
        {
            return string.Format("({0}) AND ({1})", expr.First.Accept(this), expr.Second.Accept(this));
        }

        public string Visit(Nand expr)
        {
            return string.Format("({0}) NAND ({1})", expr.First.Accept(this), expr.Second.Accept(this));
        }

        public string Visit(Or expr)
        {
            return string.Format("({0}) OR ({1})", expr.First.Accept(this), expr.Second.Accept(this));
        }

        public string Visit(Xor expr)
        {
            return string.Format("({0}) XOR ({1})", expr.First.Accept(this), expr.Second.Accept(this));
        }

        public string Visit(Not expr)
        {
            return string.Format("Not ({0})", expr.First.Accept(this));
        }

        public string Pretty(Expr expr)
        {
            return expr.Accept(this).Replace("(True)", "True");
        }
    }

    class Program
    {
        static void TestLogicalEquivalence(Expr first, Expr second)
        {
            var prettyPrinter = new PrettyPrintVisitor();
            var eval = new EvalVisitor();
            var evalFirst = eval.Eval(first);
            var evalSecond = eval.Eval(second);

            Console.WriteLine("Testing expressions:");
            Console.WriteLine("    First  = {0}", prettyPrinter.Pretty(first));
            Console.WriteLine("        Eval(First):  {0}", evalFirst);
            Console.WriteLine("    Second = {0}", prettyPrinter.Pretty(second));
            Console.WriteLine("        Eval(Second): {0}", evalSecond);;
            Console.WriteLine("    Equivalent? {0}", evalFirst == evalSecond);
            Console.WriteLine();
        }

        static void Main(string[] args)
        {
            var P = new TrueExpr();
            var Q = new Not(new TrueExpr());

            TestLogicalEquivalence(P, Q);

            TestLogicalEquivalence(
                new Not(P),
                new Nand(P, P));

            TestLogicalEquivalence(
                new And(P, Q),
                new Nand(new Nand(P, Q), new Nand(P, Q)));

            TestLogicalEquivalence(
                new Or(P, Q),
                new Nand(new Nand(P, P), new Nand(Q, Q)));

            TestLogicalEquivalence(
                new Xor(P, Q),
                new Nand(
                    new Nand(P, new Nand(P, Q)),
                    new Nand(Q, new Nand(P, Q)))
                );

            Console.ReadKey(true);
        }
    }
}

The code above is written in an idiomatic C# style. It uses the visitor pattern rather than type-testing to guarantee type safety. This is about 218 LOC.

Here's the F# version:

#light
open System

type expr =
    | True
    | And of expr * expr
    | Nand of expr * expr
    | Or of expr * expr
    | Xor of expr * expr
    | Not of expr

let (^^) p q = not(p && q) && (p || q) // makeshift xor operator

let rec eval = function
    | True          -> true
    | And(e1, e2)   -> eval(e1) && eval(e2)
    | Nand(e1, e2)  -> not(eval(e1) && eval(e2))
    | Or(e1, e2)    -> eval(e1) || eval(e2)
    | Xor(e1, e2)   -> eval(e1) ^^ eval(e2)
    | Not(e1)       -> not(eval(e1))

let rec prettyPrint e =
    let rec loop = function
        | True          -> "True"
        | And(e1, e2)   -> sprintf "(%s) AND (%s)" (loop e1) (loop e2)
        | Nand(e1, e2)  -> sprintf "(%s) NAND (%s)" (loop e1) (loop e2)
        | Or(e1, e2)    -> sprintf "(%s) OR (%s)" (loop e1) (loop e2)
        | Xor(e1, e2)   -> sprintf "(%s) XOR (%s)" (loop e1) (loop e2)
        | Not(e1)       -> sprintf "NOT (%s)" (loop e1)
    (loop e).Replace("(True)", "True")

let testLogicalEquivalence e1 e2 =
    let eval1, eval2 = eval e1, eval e2
    printfn "Testing expressions:"
    printfn "    First  = %s" (prettyPrint e1)
    printfn "        eval(e1): %b" eval1
    printfn "    Second = %s" (prettyPrint e2)
    printfn "        eval(e2): %b" eval2
    printfn "    Equilalent? %b" (eval1 = eval2)
    printfn ""

let p, q = True, Not True
let tests =
    [
        p, q;

        Not(p), Nand(p, p);

        And(p, q),
            Nand(Nand(p, q), Nand(p, q));

        Or(p, q),
            Nand(Nand(p, p), Nand(q, q));

        Xor(p, q),
            Nand(
                    Nand(p, Nand(p, q)),
                    Nand(q, Nand(p, q))
                )
    ]
tests |> Seq.iter (fun (e1, e2) -> testLogicalEquivalence e1 e2)

Console.WriteLine("(press any key)")
Console.ReadKey(true) |> ignore

This is 65 LOC. Since it uses pattern matching rather than the visitor pattern, we don't lose any type-safety, and the code is very easy to read.

Any kind of symbolic processing is orders of magnitude easier to write in F# than C#.

[Edit to add:] Oh, and pattern matching isn't just a replacement for the visitor pattern, it also allows you to match against the shape of data. For example, here's a function which converts Nand's to their equivalents:

let rec simplify = function
    | Nand(p, q) when p = q -> Not(simplify p)
    | Nand(Nand(p1, q1), Nand(p2, q2))
        when equivalent [p1; p2] && equivalent [q1; q2]
                    -> And(simplify p1, simplify q1)
    | Nand(Nand(p1, p2), Nand(q1, q2))
        when equivalent [p1; p2] && equivalent [q1; q2]
                    -> Or(simplify p1, simplify q1)
    | Nand(Nand(p1, Nand(p2, q1)), Nand(q2, Nand(p3, q3)))
        when equivalent [p1; p2; p3] && equivalent [q1; q2; q3]
                    -> Xor(simplify p1, simplify q1)
    | Nand(p, q) -> Nand(simplify p, simplify q)
    | True          -> True
    | And(p, q)     -> And(simplify p, simplify q)
    | Or(p, q)      -> Or(simplify p, simplify q)
    | Xor(p, q)     -> Xor(simplify p, simplify q)
    | Not(Not p)    -> simplify p
    | Not(p)        -> Not(simplify p)

Its not possible to write this code concisely at all in C#.