2

我正在阅读 Chris Okasaki 的纯函数式数据结构，我遇到了一个问题。它位于这里。特别是，我不明白rotateandexec函数是如何工作的：

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 的语言。:-)

4

2 回答 2

1

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

查看Wikipedia 上的 SML，特别是 Mergesort 实现，以了解更多使用::模式和_.

于 2009-11-25T19:22:09.407 回答
1

这看起来不像我学习的标准 ML（在数据构造函数前面有 $ 字符），但也许事情已经改变了。无论如何：

首先在第 2 行 rotate 有一个小错字，你在后面加了一个逗号$Cons

基本上 rotate 采用三个列表的元组并按顺序组装它们：第一个 ++（第二个的反转）++ 第三个。但它通过同时从列表 1 和列表 2 中提取元素来线性地做到这一点。列表 1 的头部是最终结果（ao(1) 操作）。但是列表 2 的尾部作为参数传递给递归调用，并且它的头部被 cons'd 到第三个参数上，这相当于反转它。

第三个论点基本上是作为一个累加器。在函数式编程中，使用累加器作为这样的参数可能是避免更昂贵计算的技巧。

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

于 2009-11-12T22:08:42.433 回答