今天，我们正在完成有关函数式编程的系列文章。 原来有11个部分。 我相信这是一项成就。 在本文中，我们实现了一个简单的堆栈计算器（也称为“反向波兰符号”）。 该实现几乎完全建立在函数的基础上，只有一种特殊类型，并且通常不与示例进行比较，因此这是本系列中所涵盖概念的绝佳测试平台。
我要分别感谢@kleidemos 。 是他担任了整个系列文章的主要翻译和经理。 谢谢你
如果您不熟悉这样的计算器，则它的工作方式如下：将数字压入堆栈，然后进行运算（例如加法和乘法），从堆栈顶部选取数字，然后放回运算结果。
堆栈上的简单计算方案：
在设计这样的系统之前，您应该考虑如何使用它。 遵循类似Forth的语法，我们将为每个操作赋予适当的标签，以便在上面的示例中您可以编写类似以下内容的内容：
EMPTY ONE THREE ADD TWO MUL SHOW
也许不可能完全获得这种语法，但让我们尝试尽可能地接近此语法。
堆栈数据类型
首先，您需要定义堆栈的数据结构。 为简单起见，您可以使用浮点数列表。
type Stack = float list
但是最好将其包装在单个case联合类型中，以使该类型更直观，如下所示：
type Stack = StackContents of float list
为什么这样做更好，您可以在这里阅读。
现在使用StackContents作为构造函数创建一个新堆栈：
let newStack = StackContents [1.0;2.0;3.0]
要从现有堆栈中提取内容，请使用与StackContents匹配的模式：
let (StackContents contents) = newStack // "contents" // float list = [1.0; 2.0; 3.0]
推送功能
接下来，我们需要一种将数字放入此堆栈的方法。 为此，只需使用“ :: ”将新值添加到列表顶部。
功能示例：
let push x aStack = let (StackContents contents) = aStack let newContents = x::contents StackContents newContents
此功能具有许多值得讨论的功能。
首先，您应注意list结构是不可变的，这意味着该函数必须采用现有堆栈并返回一个新堆栈。 这不仅仅是对现有堆栈的更改。 实际上，此示例中的所有函数都将具有类似的格式：
Input: Stack - Output: Stack
其次，为什么参数按该顺序排列？ 为什么堆栈应该排在最前或最后？ 在关于使用部分应用程序设计功能的部分中，据说最频繁更改的参数应该排在最后。 很快将有可能验证是否遵循了这些建议。
最后，通过与功能参数本身中的模式匹配，而不是let进入函数主体，可以使函数更简洁。
改写的版本：
let push x (StackContents contents) = StackContents (x::contents)
好多了！
顺便说一句，看看她优美的签名：
val push : float -> Stack -> Stack
如前所述 ，签名告诉了我们很多。
在这种情况下，我仅凭其签名就可以猜出该函数的作用，甚至不知道它被称为“推”。
这是拥有显式类型名称的一个好主意的另一个原因。 如果堆栈只是浮点数的列表，那么该函数就不会如此自我记录。
一种或另一种方法，检查：
let emptyStack = StackContents [] let stackWith1 = push 1.0 emptyStack let stackWith2 = push 2.0 stackWith1
很棒！
使用push堆叠顶部上标
使用此简单功能，您可以轻松定义将特定数字压入堆栈的操作。
let ONE stack = push 1.0 stack let TWO stack = push 2.0 stack
但是请稍等！ 您看到表达式的两边都提到了stack参数吗？ 实际上，没有必要再提两次。 相反，您可以省略参数，并使用部分应用程序编写函数：
let ONE = push 1.0 let TWO = push 2.0 let THREE = push 3.0 let FOUR = push 4.0 let FIVE = push 5.0
现在很明显，如果push函数的参数顺序不同，则必须两次提及stack 。
还值得定义一个创建空堆栈的函数：
let EMPTY = StackContents []
检查收到的功能：
let stackWith1 = ONE EMPTY let stackWith2 = TWO stackWith1 let stackWith3 = THREE stackWith2
这些中间堆栈烦人吗？ 有可能摆脱它们吗？ 当然可以！ 请注意，一个，两个和三个函数具有相同的签名：
Stack -> Stack
因此，它们完美地连接在一起！ 一个功能的输出可以输入以下内容：
let result123 = EMPTY |> ONE |> TWO |> THREE let result312 = EMPTY |> THREE |> ONE |> TWO
从堆栈中弹出
解决了堆栈问题之后， pop函数又如何呢？
从堆栈中检索时，显然有必要返回堆栈的顶部，但是仅仅是这样吗？
在面向对象的风格中， 答案是肯定的 。 但是对于OOP，将在后台更改堆栈，以便删除顶部项目。
但是，在功能风格上，堆栈是不可变的。 删除顶部元素只有一种方法-创建一个没有该元素的新堆栈 。 为了使调用者可以访问新的精简堆栈，它必须与top元素一起返回。
换句话说， pop函数应返回两个值，即top元素和新堆栈。 在F＃中执行此操作的最简单方法是简单地使用元组。
实现方式：
/// /// let pop (StackContents contents) = match contents with | top::rest -> let newStack = StackContents rest (top,newStack)
产生的功能也非常简单。
和以前一样，直接从参数contents提取contents 。
然后，使用match..with表达式检查内容的contents 。
然后将顶部元素与列表的其余部分分开，根据其余元素创建一个新的堆栈，最后将所有这些作为元组对返回。
尝试运行此代码，看看会发生什么。 您会得到一个编译错误！
编译器检测到一个尚未解决的情况-如果堆栈为空会怎样？
您必须决定如何处理它。
我通常更喜欢对错误使用特殊的状态，但是在这种特殊情况下，我更喜欢抛出异常。 固定版本的pop带有空的案例处理：
let pop (StackContents contents) = match contents with | top::rest -> let newStack = StackContents rest (top,newStack) | [] -> failwith "Stack underflow"
检查：
let initialStack = EMPTY |> ONE |> TWO let popped1, poppedStack = pop initialStack let popped2, poppedStack2 = pop poppedStack
和异常测试：
let _ = pop EMPTY
算术函数
现在添加和删除已经到位，您可以开始使用“ add”和“ multiply”功能了：
let ADD stack = let x,s = pop stack // let y,s2 = pop s // let result = x + y // push result s2 // let MUL stack = let x,s = pop stack // let y,s2 = pop s // let result = x * y // push result s2 //
在线测试：
let add1and2 = EMPTY |> ONE |> TWO |> ADD let add2and3 = EMPTY |> TWO |> THREE |> ADD let mult2and3 = EMPTY |> TWO |> THREE |> MUL
有效！
重构时间...
显然，这两个函数中有大量的代码重复。 我们该如何解决？
这两个函数都从堆栈中提取两个值，对它们应用某个二进制函数，然后将结果推回堆栈中。 您可以将通用代码输出到二进制函数，该函数采用带有两个参数的数学函数：
let binary mathFn stack = // let y,stack' = pop stack // let x,stack'' = pop stack' // let z = mathFn xy // push z stack''
请注意，在此实现中，“相同”对象的不同版本用不同数量的引号标记。 这是因为数字后缀很容易导致混淆。
问题：为什么参数完全按此顺序排列，而不是在stack之后添加mathFn ？
现在您有了一个binary函数，定义ADD和其他函数要容易得多：
第一次尝试使用binary实现ADD：
let ADD aStack = binary (fun xy -> x + y) aStack
但是您可以摆脱lambda，因为 它表示内置函数+的确切定义：
let ADD aStack = binary (+) aStack
同样，可以使用部分应用程序来隐藏堆栈参数。 最终定义：
let ADD = binary (+)
其他数学函数的定义：
let SUB = binary (-) let MUL = binary (*) let DIV = binary (../)
在线尝试：
let div2by3 = EMPTY |> THREE|> TWO |> DIV let sub2from5 = EMPTY |> TWO |> FIVE |> SUB let add1and2thenSub3 = EMPTY |> ONE |> TWO |> ADD |> THREE |> SUB
同样，您可以为一元运算创建辅助功能
let unary f stack = let x,stack' = pop stack push (fx) stack'
并定义一些一元函数：
let NEG = unary (fun x -> -x) let SQUARE = unary (fun x -> x * x)
互动模式：
let neg3 = EMPTY |> THREE|> NEG let square2 = EMPTY |> TWO |> SQUARE
全部放在一起| 全部放在一起
在最初的要求中，提到我们希望能够显示结果，因此值得定义SHOW函数。
let SHOW stack = let x,_ = pop stack printfn "The answer is %f" x stack //
请注意，在这种情况下，将忽略通过pop接收到的堆栈的新版本。 最终结果是原始堆栈，就好像它从未更改过一样。
最后，您可以根据原始要求编写以下示例
EMPTY |> ONE |> THREE |> ADD |> TWO |> MUL |> SHOW
继续前进
这很有趣，但是您还能做什么？
您可以定义几个附加功能：
/// let DUP stack = // let x,_ = pop stack // push x stack /// let SWAP stack = let x,s = pop stack let y,s' = pop s push y (push x s') /// let START = EMPTY
使用这些附加功能，您可以编写一些精美的示例：
START |> ONE |> TWO |> SHOW START |> ONE |> TWO |> ADD |> SHOW |> THREE |> ADD |> SHOW START |> THREE |> DUP |> DUP |> MUL |> MUL // 27 START |> ONE |> TWO |> ADD |> SHOW // 3 |> THREE |> MUL |> SHOW // 9 |> TWO |> SWAP |> DIV |> SHOW // 9 div 2 = 4.5
使用合成代替流水线
但这还不是全部。 实际上，还有另一种有趣的方式来表示这些功能。
如前所述，它们都具有相同的签名：
Stack -> Stack
由于输入和输出是同一类型，因此也可以使用组合运算符>>组合这些函数，而不仅是通过管道运算符。
一些例子：
// let ONE_TWO_ADD = ONE >> TWO >> ADD START |> ONE_TWO_ADD |> SHOW // let SQUARE = DUP >> MUL START |> TWO |> SQUARE |> SHOW // let CUBE = DUP >> DUP >> MUL >> MUL START |> THREE |> CUBE |> SHOW // let SUM_NUMBERS_UPTO = DUP // n >> ONE >> ADD // n+1 >> MUL // n(n+1) >> TWO >> SWAP >> DIV // n(n+1) / 2 START |> THREE |> SQUARE |> SUM_NUMBERS_UPTO |> SHOW
在每个这些示例中，使用其他功能的组合定义了一个新功能。 这是构建功能的“组合”方法的一个很好的例子。
输送机与成分
我们看到了使用模型的两种不同方法。 使用输送机和成分。 但是有什么区别呢？ 为什么一个人比另一个人更受青睐？
区别在于，从某种意义上说，管道是“实时转换”操作。 在使用管道时，将通过传输特定堆栈立即执行操作。
另一方面，合成就像我们要实现的“计划”一样，无需直接应用即可从一组组件构建功能。
例如，您可以通过结合一些小操作来创建一个“计划”来计算数字的平方：
let COMPOSED_SQUARE = DUP >> MUL
我不能根据管道给出等效的结果。
let PIPED_SQUARE = DUP |> MUL
这将导致编译错误。 我需要一些特定的堆栈实例才能使表达式起作用：
let stackWith2 = EMPTY |> TWO let twoSquared = stackWith2 |> DUP |> MUL
即使在这种情况下，我也只能针对此特定输入获得答案，而不能像基于COMPOSED_SQUARE的示例那样基于任何输入获得通用的计算计划。
创建“计划”的另一种方法是将lambda显式传递给更多原始函数：
let LAMBDA_SQUARE = unary (fun x -> x * x)
这是一种更明确的方法（并且可能更快），但是失去了组合方法的所有优点和清晰度。
通常，如果可能的话，您应该争取一种合成方法！
完整代码
上面所有示例的完整代码：
// ============================================== // // ============================================== type Stack = StackContents of float list // ============================================== // // ============================================== /// let push x (StackContents contents) = StackContents (x::contents) /// /// let pop (StackContents contents) = match contents with | top::rest -> let newStack = StackContents rest (top,newStack) | [] -> failwith "Stack underflow" // ============================================== // () // ============================================== // // // let binary mathFn stack = let y,stack' = pop stack let x,stack'' = pop stack' let z = mathFn xy push z stack'' // // // let unary f stack = let x,stack' = pop stack push (fx) stack' // ============================================== // () // ============================================== /// let SHOW stack = let x,_ = pop stack printfn "The answer is %f" x stack // /// let DUP stack = let x,s = pop stack push x (push xs) /// let SWAP stack = let x,s = pop stack let y,s' = pop s push y (push x s') /// let DROP stack = let _,s = pop stack // s // // ============================================== // , // ============================================== // // ------------------------------- let EMPTY = StackContents [] let START = EMPTY // // ------------------------------- let ONE = push 1.0 let TWO = push 2.0 let THREE = push 3.0 let FOUR = push 4.0 let FIVE = push 5.0 // // ------------------------------- let ADD = binary (+) let SUB = binary (-) let MUL = binary (*) let DIV = binary (../) let NEG = unary (fun x -> -x) // ============================================== // , // ============================================== let SQUARE = DUP >> MUL let CUBE = DUP >> DUP >> MUL >> MUL let SUM_NUMBERS_UPTO = DUP // n >> ONE >> ADD // n+1 >> MUL // n(n+1) >> TWO >> SWAP >> DIV // n(n+1) / 2
结论
我们有一个简单的基于堆栈的计算器。 我们看到了如何从一些原始操作（ push ， pop ， binary ， unary ）和其他操作开始，构建出易于实现和使用的功能完善的DSL。
您可能会猜到，这个示例几乎是基于Forth语言的。 我强烈推荐免费的书籍《 Thinking Forth》 ，该书不仅讲述了Forth语言，而且还讲解了其他分解方法的方法（这些方法通常适用于函数式编程）。
我从Ashley Feniello的华丽博客中获得了这篇文章的想法。 如果您想更深入地研究基于F＃的基于堆栈的语言，请从它开始。 玩得开心！
其他资源
F＃的教程很多，包括那些具有C＃或Java经验的人的材料。 当您深入了解F＃时，以下链接可能会很有用：
还介绍了其他几种开始学习F＃的方法 。
最后，F＃社区非常适合初学者。 在Slack上，由F＃Software Foundation支持的聊天非常活跃，您可以自由加入初学者室。 我们强烈建议您这样做！
不要忘记访问俄语社区F＃的网站 ！ 如果您对学习语言有任何疑问，我们将很乐意在聊天室中讨论这些问题：
关于翻译作者
由@kleidemos翻译
在F＃开发人员的俄语社区的努力下进行了翻译和编辑更改。 我们也感谢@schvepsss和@shwars为本文准备发表。