这个标准ML代码究竟做了什么？

Question

我正在阅读Chris Okasaki的纯功能数据结构，并且有一个例子遇到了问题。它位于here。我特别不理解rotate和exec功能是如何工作的：

fun rotate($Nil, y::_, a) = $Cons (y, a) 
    | rotate ($Cons (x, xs), y :: ys, a) = 
     $Cons(x, rotate (xs, ys, $Cons (y, a))) 

fun exec (f, r, $Cons (X, s)) = (f, r, s) 
    | exec (f, r, $Nil) = let val f' = rotate (f, r, $Nil) in (f', [], f') end 

可能有人把这个愚蠢的人民条款？我仍然在学习基于ML的语言。 :-)

Answer 1

这看起来不像我学习的标准ML（在数据构造函数前面有$字符），但可能事情已经改变。总之：

首先有对旋转2线小错字，你加一个逗号$Cons

基本上旋转需要经过三个列表的元组和顺序组装它们：第一个++（反向第二个）++第三个。但它通过从列表1和列表2中同时提取元素来线性地执行此操作。列表1的头部是最终结果（a o（1）操作）。但是列表2的尾部作为参数传递给递归调用，它的头部被放在第三个参数上，这相当于倒转它。

第三个参数基本上作为累加器。在使用累加器作为参数的函数式编程中，可以避免更昂贵的计算。

我承认不理解exec的目的。上下文是什么？

Answer 2

这并不能说明整个事情，但需要注意的是，在fun rotate($Nil, y::_, a)的y::_是其中您标记列表（第一个元素）作为y和头部列表的尾部（每个匹配列表模式第一个元素之后的项目）为_。 _充当通配符模式。

检出SML on Wikipedia，特别是Mergesort实现，更多地使用::模式和_。