哪些任务最适合用函数式编程风格完成？

Question

我最近才发现了函数式编程风格，我相信这种风格可以减少开发工作量，使代码更易读，使软件更易于维护。然而，问题是我不擅长说服别人。

最近，我有机会发表关于如何减少软件开发和维护工作的演讲，并想介绍函数式编程的概念以及它如何使团队受益。我想展示两组完成相同任务的代码，一组采用非常命令式的方式编写，另一组采用非常函数式的方式编写，以此来说明函数式编程可以使代码更短、更易理解，从而更易于维护。除了 Luca Bolognese 的著名平方和示例之外，是否还有其他的示例可用？

- Hao Wooi Lim

---

有人能提供一下"Luca Bolognese 的著名平方和例子"的链接吗？谢谢。 - dance2die

好的，我会尽力进行翻译。以下是需要翻译的内容：Luca的演讲：http://channel9.msdn.com/pdc2008/TL11/Luca是微软公司的一位工程师，他在这次演讲中介绍了一种名为“云服务”的新技术。云服务可以让用户通过互联网使用各种软件和服务，而无需将它们安装在自己的计算机上。这意味着用户可以随时随地访问自己所需的资源，而无需担心计算机的配置或存储空间不足。Luca还介绍了云服务与传统软件的区别，以及它们对企业和消费者的影响。他指出，云服务可以大幅降低企业和个人的成本，并提高生产力和灵活性。同时，云服务还能带来更好的安全性和可靠性，保护用户的数据和隐私。总的来说，Luca认为云服务是未来发展的方向，它将改变人们使用和管理计算机系统的方式，为用户带来更加便捷和高效的体验。 - Brian

Answer 1

我最近才发现函数式编程风格[...] 最近，我有机会做一个关于如何减少软件开发工作量的演讲， 我想介绍一下函数式编程的概念。

如果你只是最近才发现函数式编程，我不建议试图在这个主题上表现得很有权威性。我知道在学习F#的头6个月里，我的所有代码都只是带有更加笨拙语法的C#。然而，在那段时间之后，我能够以符合习惯的函数式风格编写一致好的代码。

我建议你也这样做：等待6个月左右，直到函数式编程风格变得更加自然，然后再进行演讲。

我正在尝试阐述函数式编程的好处，我想展示人们两组做同样事情的代码，一组采用非常命令式的方式编码，另一组采用非常函数式的方式编码，以此展示函数式编程可以使代码更短、更易于理解，从而更容易维护。除了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行代码。

这是F#版本：

#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行。由于它使用模式匹配而不是访问者模式，我们不会失去任何类型安全性，并且代码非常易于阅读。

任何类型的符号处理在F#中编写比C#容易几个数量级。

[编辑以添加:] 哦，而模式匹配不仅是访问者模式的替代，还允许您针对数据的形状进行匹配。例如，这是一个将Nand转换为它们等效物的函数：

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#中根本无法简洁地编写此代码。

- Princess

---

“let rec loop = function” 这句话是什么意思？我知道这是一个递归函数的声明，但这里的 “function” 关键字是什么意思？它是一种简单的声明只有一个参数的函数的方式吗？并且在这个单一参数上进行模式匹配？（因此我们省略了参数名称和“match”关键字） - Dmitrii Lobanov

@DmitryLobanov 我的意思和以下代码一样： let rec loop = match loop with - user522860

@CheckMate9500 你是指 let rec loop x = match x with... 吗？ - Mauricio Scheffer

有人能给我指一下如何实际使用上面的 c# 接口 IExprVisitor<t> 代码的例子吗？ - Alex Gordon

维基百科关于访问者模式的 动机 描述了在 CAD 系统中将对象导出为图像（或在屏幕上呈现）。在表达式节点中，您没有任何特定于评估/处理的代码，并且如果您“忘记”新创建的 Expr 子类型的实现，您也会在编译时出现错误，因为 Expr 知道 IExprVisitor，而 IExprVisitor 知道每种可能的 Expr 类型。如果您使用 switch/case 实现它，很容易忘记专门为新类型进行操作。 - sunside

Answer 2

有许多示例，但没有哪个能像使用与你工作项目相关的示例那样具有影响力。像Luca的 "平方和" 这样的示例非常棒，但如果有人将其用作证明我们的代码库可以写得更好的证据，我是不会被说服的。所有的例子都只证明了有些东西在函数式编程中写得更好。你需要证明的是你的代码库在函数式编程中写得更好。

我的建议是选择一些常见的问题和代码库中的核心部分，并以函数式风格重写它们。如果您可以展示出明显更好的解决方案，这将有助于赢得同事的信任。

- JaredPar

Answer 3

在函数式编程中需要完成的任务是什么？任何时候你都可以使用它来减少常见的编码模式。不久前，我写了一篇关于如何在C#中使用函数式风格的博客文章，并确保它是实用的：实用的函数式C#（我不确定是否应该在这里链接到自己的东西，但我认为在这种情况下它很相关）。如果你有一个常见的“企业”应用程序，展示表达式在模式匹配中的美妙之处可能不太令人信服。

但在现实世界的应用程序中，有许多低级别的模式出现。使用高阶函数，你可以使它们消失。正如我在那组博客文章中所展示的那样，我的最爱例子是WCF的“try-close/finally-abort”模式。 “try/finally-dispose”模式是如此常见，以至于它被转换成语言关键字：using。对于“lock”也是同样的情况。这两个模式都可以轻松地表示为高阶函数，只是因为C#最初不支持它们，我们才需要硬编码的语言关键字来支持它们。 （快速：将您的“lock”块切换为使用ReaderWriter锁。糟糕，我们首先需要编写一个高阶函数。）

但也许说服只需要看看Microsoft。泛型（即参数化多态）？那几乎不是面向对象的，但现在，每个人都喜欢这个很好的函数式概念。可爱的Ninject框架没有它就无法工作。Lambda表达式？作为表达树，它们是LINQ、Fluent NHibernate等获取所有功能的方式。再次强调，这并不来自面向对象或命令式编程。新的线程库？如果没有闭包，它会非常丑陋。

因此，函数式编程在过去十年中一直是类似.NET这样的事物的福音。主要进展（例如泛型，“LINQ”）直接来自函数式语言。为什么不意识到其中的价值，并更加深入地参与其中呢？这就是我向怀疑者表达的方式。 更大的问题实际上是让人们理解高阶函数的跨越。虽然这相当容易，但如果你从未见过它，可能会感到震惊和难以理解。（嘿，似乎很多人认为泛型只用于类型安全集合，LINQ只是内嵌的SQL。）

因此，你应该浏览你的代码库，并找到过于复杂的命令式噩梦的地方。搜索底层模式，并使用函数将它们漂亮地串在一起。如果你找不到任何东西，你可能会满足于演示列表。例如“查找此列表中的所有Foo并删除它们”。在函数式风格中，这是一个1行的事情“myList.Remove(x=>x.Bla > 0)”，而在C#风格中需要7行（创建一个临时列表，循环遍历并添加要删除的项目，循环遍历并删除项目）。

希望即使语法有些奇怪，人们也能认识到"哇，这简单多了"。如果他们能暂时放下"冗长等于可读性强"和"那看起来很费解"的想法，你就有机会了。

祝好运。

- MichaelGG

---

https://web.archive.org/web/20160316073516/http://www.atrevido.net/blog/2007/08/12/Practical+Functional+C+Part+I.aspx - Kristoffer Jälén

Answer 4

最好的函数式编程倡导论文是由约翰·休斯（John Hughes）撰写的一篇名为《为什么函数式编程很重要》的论文。我建议你自己做一些例子，直到你能够有说服力地阐述该论文中所阐述的观点。

该论文中的许多示例都是关于数字的，与今天的读者不太相关。我给我的学生们提供了一个更具时代感的练习，即使用该论文中的思想将大型媒体文件打包成4.7GB的DVD备份。他们使用迈克尔·米茨恩马赫（Michael Mitzenmacher）的“冒泡搜索”算法生成备选方案，并使用这个算法和休斯的技术，很容易使每个DVD（除了最后一个）达到99.9%的容量利用率。非常棒。

- Norman Ramsey

---

@compie已修复。我讨厌链接失效。 - Norman Ramsey

Answer 5

本质上，函数式编程范式非常适合并行处理：

“我想让你注意到的真正有趣的事情是，一旦你将map和reduce视为每个人都可以使用的函数，并且他们使用它们，你只需要让一个超级天才编写硬代码来在全局大规模并行计算机阵列上运行map和reduce，所有旧代码仍然像以前一样工作，只是快了无数倍，这意味着它可以用于瞬间解决巨大的问题。

让我重复一遍。通过抽象出循环的概念，您可以以任何希望的方式实现循环，包括以与额外硬件良好扩展的方式实现它。” http://www.joelonsoftware.com/items/2006/08/01.html

- ken

Answer 6

为了实现您想要的，并向组织中的其他人传达它，您需要展示公司业务以更好的方式构建。如果功能编程对于您的业务领域毫无用处，那么使用几个算法来展示其强大的能力是没有用的。因此，拿出一些现有的代码并以功能方式重写它。如果你可以通过这种方式证明它更好，人们会听取你的意见 - 你已经向他们展示了一个具体、相关的例子。如果不能，那么也许函数式编程不是你一直在寻找的解决方案。

- gbjbaanb

Answer 7

另一个例子是快速排序算法。它可以在像Haskell这样的函数式语言中非常简洁地描述：

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

但需要在迭代语言中进行更多编码。在引用的网站上，您还可以找到许多其他语言之间的比较示例。

- crackmigg

---

在相同的链接中，您还可以发现这种方法效率比较低下，因为每次迭代都要遍历xs列表两次。因此，尽管这是一个非常流行的例子，但我并不特别喜欢它。 - Kurt Schelfthout

此外，这并不会让代码更加简洁，这段代码似乎相当“巧妙”（如果你明白我的意思的话），我们在这里进行了很多复制，效率不是很高，我认为。 - hasen

@tokland：快速排序算法是专门为了通过原地交换来减少内存开销而设计的。这种改良版导致大量完全不必要的复制，因此比真正的快速排序慢了数个数量级。 - J D

历史上，这是函数式编程中的一个难题。另一个难题是埃拉托斯特尼筛法，在FP社区的知名人士教授了数以万计的学生关于美丽的纯函数实现之前，Melissa O'Neill写了一篇论文解释了为什么他们多年来都是错误的。http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf - J D

@Jon：我不是算法方面的专家，但我很惊讶，因为我在许多（严肃的）地方看到了这种快速排序的实现。维基百科上说：“虽然快速排序通常不作为原地排序实现，但可以创建这样的实现”。你能提供任何网址吗？[检查筛选器，还有关于快速排序的吗？] - tokland

Answer 8

如果你所说的“函数式风格”是指使用像“map”、“apply”、“reduce”、“filter”、“lambda 函数”和列表理解等概念，那么很明显，在处理列表操作的代码上，使用“函数式风格”编写的代码几乎总是更加简洁的。但如果你在大多数情况下是在一个主要是命令式的语言中混合使用“函数式风格”和命令式代码，那么这只是一种风格问题。

例如，在 Python 中，你可以这样重新实现Haskell qsort：

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

可以说更符合Python的风格。

但这显然比此处的实现更简洁：

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

顺便说一下，在我学习 Haskell 之前，这是我想要实现它的方式。

如果你已经适应了函数式编程并像老练的 C++ 程序员一样轻松理解 filter 的作用，那么函数式版本就非常清晰。这显然是实际问题的关键：函数“风格”编程是一种完全不同的思维方式。如果你合作的人不习惯递归思考，并且不是那种对于解决问题有全新思路的方法感到兴奋的类型，那么任何数量的代码比较都无法说服他们。

- ebencooke

---

您发布的内容并不是快速排序算法的实现，因为它会对列表进行两次划分。请参阅http://augustss.blogspot.com/2007/08/quicksort-in-haskell-quicksort-is.html。 - RossFabricant

你是正确的。缺少O(n)数组操作是函数式编程最大的缺点（尽管您可以在Lisp中使用向量完成它们！） - Zachary Hamm

将列表分成两个部分可以在单次遍历中轻松完成。我认为F#内置了这样的函数。虽然两次遍历也是O(n)，但您还可以拥有等效于数组操作的东西。请查看Chris Okasaki的“纯函数数据结构”。 - Jørgen Fogh

这不是快速排序，但并非因为双重遍历。 - J D

Answer 9

一个好的例子是使用现有的编程语言创建自己的编程语言，这时你将不得不使用单子。

使用F#编写解析逻辑比使用C#简单得多。

看一下这篇文章：Functional .NET - LINQ还是语言集成单子？

- Koistya Navin

Answer 10

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

- Pete Kirkham