这个标准ML代码究竟做了什么?
问题描述:
我正在阅读Chris Okasaki的纯功能数据结构,并且有一个例子遇到了问题。它位于here。我特别不理解rotate
和exec
功能是如何工作的:这个标准ML代码究竟做了什么?
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的语言。 :-)
答
这看起来不像我学习的标准ML(在数据构造函数前面有$字符),但可能事情已经改变。总之:
首先有对旋转2线小错字,你加一个逗号$Cons
基本上旋转需要经过三个列表的元组和顺序组装它们:第一个++(反向第二个)++第三个。但它通过从列表1和列表2中同时提取元素来线性地执行此操作。列表1的头部是最终结果(a o(1)操作)。但是列表2的尾部作为参数传递给递归调用,它的头部被放在第三个参数上,这相当于倒转它。
第三个参数基本上作为累加器。在使用累加器作为参数的函数式编程中,可以避免更昂贵的计算。
我承认不理解exec的目的。上下文是什么?
答
这并不能说明整个事情,但需要注意的是,在fun rotate($Nil, y::_, a)
的y::_
是其中您标记列表(第一个元素)作为y
和头部列表的尾部(每个匹配列表模式第一个元素之后的项目)为_
。 _
充当通配符模式。
检出SML on Wikipedia,特别是Mergesort实现,更多地使用::
模式和_
。
美元符号是他对懒惰评价的表示法。实质上,这是一个实时的持续队列,您可以将项目从尾部旋转到前部。 – 2009-11-12 23:03:28