什么样的任务最好用函数式编程方式完成?

最近我有机会做一个关于如何减少吸烟的演讲 软件开发工作,以及我 想介绍一下 函数式编程。

如果你刚刚发现函数式编程,我 不要 建议尝试就这个主题发表权威性的讲话。我知道在我学习F#的前6个月里,我所有的代码都是C#,语法有点笨拙。然而,在这段时间之后,我能够以惯用的、功能性的风格编写出始终如一的好代码。

我建议您也这样做:等待6个月左右,直到函数式编程风格变得更加自然,然后进行演示。

我正在努力 编程,我想到了 向人们展示2组代码 命令式,另一种是 非常实用的方式,来证明这一点 函数式编程可以编写代码 更简短、更容易理解和理解 因此保持。有没有这样的例子,, Luca Bolognese的例子?

我向我所在地区的.NET用户组做了一次F#演示,我所在组的许多人对F#的模式匹配印象深刻。具体来说,我演示了如何在C和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);
        }
    }
}

上面的代码是用惯用的C#风格编写的。它使用访问者模式而不是类型测试来保证类型安全。这大约是218 LOC。

#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

这里是65 LOC。因为它使用模式匹配而不是访问者模式,所以我们不会丢失任何类型安全性,代码也很容易阅读。

任何 这种符号处理比C更容易用F来写。

形状

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)

要用C语言简洁地编写这段代码是不可能的。

我的建议是在代码库中选择一些常见的问题点和一些核心点,并以函数式的方式重写它们。如果你能证明一个更好的解决方案,它将大大有助于赢得同事的支持。

Practical Functional C# (我不太愿意在这里链接到我自己的东西,但我认为这与本案有关)。如果您有一个通用的“企业”应用程序,那么显示(比如)模式匹配中表达式的可爱程度不会太有说服力。

但在现实世界的应用程序中,有大量的模式在低编码级别上弹出。使用高阶函数,可以使它们消失。正如我在这组博客文章中所展示的,我最喜欢的例子是WCF的“try close/finally abort”模式。“try/finally dispose”模式非常常见,以至于它变成了一个语言关键字:using。“锁”也是一样。这两个函数都被简单地表示为高阶函数,只有因为C#最初不支持它们,我们才需要硬编码的语言关键字来支持它们。(快速:切换“锁”块以使用ReaderWriter锁。哎呀,我们必须先编写一个高阶函数。)

但也许说服力只需要看看微软。泛型又称参数多态性?这几乎不是OO,而是一个很好的功能概念,现在,每个人都喜欢它。没有它,可爱的Ninject框架就无法工作。兰博达斯?作为表达树,它们是LINQ、Fluent NHibernate等获得所有能力的方式。同样,这不是来自OO或命令式编程。新线程库?没有闭包就很难看。

因此,在过去的十年中,函数式编程一直是.NET之类的东西的福音。主要的进步(如泛型,“LINQ”)直接来自函数式语言。为什么不意识到其中的某些东西并更多地参与其中呢?这就是我对怀疑论者所说的话。

更大的问题 实际上是让人们对高阶函数的理解有了飞跃。虽然这很容易,但如果你一生中从未见过它,它可能会令人震惊,令人费解。(见鬼,似乎很多人认为泛型只是用于类型安全集合,而LINQ只是嵌入式SQL。)

所以,您应该做的是浏览您的代码库,并找到那些过于复杂的地方。搜索底层模式,并使用函数将其很好地串在一起。如果你找不到,你可以满足于只演示列表。例如“查找此列表中的所有foo并将其删除”。这是功能样式“myList.Remove(x=>x.Bla>0)”中的1行内容,而C#样式中的7行内容(创建临时列表、循环和添加以删除项目、循环并删除项目)。

祝你好运

约翰·休斯(John Hughes)的一篇名为 Why Functional Programming Matters . 我建议你自己做一些例子,直到你能令人信服地提出论文中的论点为止。

论文中的许多例子都是数字的,不能与今天的读者产生共鸣。我给学生们做的另一个当代练习是利用那篇论文中的思想将大型媒体文件打包到4.7GB DVD上进行备份。他们使用Michael Mitzenmacher的“气泡搜索”算法生成替代包装,使用该算法和Hughes的技术,很容易获得99.9%的DVD(最后一张除外)。很甜。

你要注意,这里,是不是尽快 正如你所想的那样,map和reduce都是 每个人都可以使用的功能,以及 一个写硬代码的天才 大规模并行计算机阵列, 好吧,当你还在循环的时候 只起作用了速度快了无数倍 这意味着它可以用来解决 一瞬间就出现了巨大的问题。

循环的概念,你可以 以任何方式实现循环, 包括以某种方式实施它 这与额外的

http://www.joelonsoftware.com/items/2006/08/01.html

另一个例子是 Quicksort algorithm

qsort []     = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

但是需要更多的迭代语言编码。在被引用的网站上,你还可以找到许多其他语言之间比较的例子。

为了实现您的目标,并与组织中的其他人沟通,您需要以更好的方式展示您公司的业务。

如果函数式编程对您的业务领域毫无用处,那么使用两种算法来演示函数式编程的威力是没有用的。因此,使用一些现有代码并在功能上重写它。如果你能证明这是更好的,人们会听你的——你已经向他们展示了一个具体的、相关的例子。如果不能,那么函数式编程可能不是您一直在寻找的解决方案。

例如,在python中,您可以重新实现Haskell qsort crackmigg,如下所示:

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

虽然最后一行写的是

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

可以说是更“蟒蛇式的”。

但这显然比这里的实现更简洁:

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

功能版本非常清晰 如果 和 filter 将像熟练的C++程序员一样轻松地完成一个 for 循环,甚至不需要考虑太多。显然,这才是真正的问题所在:函数式“风格”编程是一种 完全不同的心态 . 如果与您一起工作的人不习惯递归思维,也不是那种令人兴奋的类型,不仅仅是一种新技术,而是解决他们问题的另一种思维方式,那么任何数量的代码比较都无法赢得他们的支持。

一个很好的例子是使用现有的编程语言创建您自己的编程语言,您必须使用它 Monads .

看看这篇文章: Functional .NET - LINQ or Language Integrated Monads?

涉及回溯搜索和简化GUI中撤销支持的算法是我在实践中使用函数式的两个地方。

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

向他们展示jQuery在DOM元素上的迭代方式:

$(".magic-divs").click(function(){
    // FYI, in this context, "this" will be the element clicked on.
    alert("somebody clicked on " + this.id);
    this.hide();

});

$(".magic-divs").show();

var arrayOfElements = // this is filled with the elements somehow
for(var i=0,j=arrayOfElements.length; i<j; i++) {
   alert("now I get to add an onclick event somehow " + i);
}
// i dont even want to type the ugly for-loop stuff to hide every div...

函数式编程在上述日常工作中非常有用!

我最近想出了一个小把戏,让传递到扩展方法中的lambdas看起来更像F#ish。 下面是:

我想做的是:

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

现在,可轻松实现的扩展方法:

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

ForEach(index => action()) 虽然它从未被使用过,所以我用一个 _ 得到 ForEach(_ => action())

这很好,但现在我有动力让我的调用代码看起来类似

(我从来都不喜欢lambda表达式开头的“()”),因此: 3.Times(() => ...); 我想要 3.Times(_ => ...);

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

这让我可以这样称呼它:

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

虽然没有太大的改变,但我仍然很享受,可以如此轻松地进行小调整,同时去除“()”噪音,使其更具可读性。

不是真的回答这个问题,但是对于那些想了解C函数式编程的人来说,这是一个非常好的链接#

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

1. 演示如何对数组的不同部分进行编码。Distinct在SQL中非常简单,但在内存数组中很难实现。现在很容易用LINQ区分数组。

3. 向他们解释LINQ是一种处理所有不同类型数据的查询语言。内存、数据库、excell、web服务、xml文件、JSON文件。它是某种通用SQL。然而,不喜欢SQL的人就不那么信服了。

有趣的是,没有人真正回答了这个问题:什么任务最好以“功能性风格”完成?

程序/算法由两部分组成:逻辑控制和数据结构。我认为功能性风格中最好的任务是那些涉及列表或数组的任务,它们的行为类似于列表(例如qsort)。函数式编程语言对列表有很好的支持,这并非巧合。

当数据结构偏离列表时,我认为使用函数式编程风格有点“不自然”。