3

我需要帮助编写这样的代码：

给定两个函数，比如 f1 和 f2 以及 f1 的初始输入 i1，我会将 i1 提供给 f1，无论它返回什么输出，我都会提供给 f2，而无论 f2 返回什么，我都会提供给 f1，依此类推......

因此它看起来像这样： fun pair(m1, m2, i1) = ...

这里的 m1 和 m2 实际上代表有限状态传感器，使得 m1 = (state, f1)。这里的状态是我们拥有的初始状态 i1。f1 接收 (state, input) 并返回一个输出 (next state, oput)，然后将 oput 馈送到 m1 等等..

为澄清起见，这代表一个传感器系统。这意味着两个具有互补输入和输出的 FST 可以并行运行，每个 FST 的输出作为另一个的输入。

这应该返回生成的输出列表。

为了提供帮助，我已经编写了一个函数 run，它接受 fst m 和输入列表，给出通过在输入上运行 m 获得的输出列表。

然而，当我尝试编写这个函数时，我的头晕了，因为我进入了一个无限循环，而且我的代码长得令人难以置信，而这可以使用我的辅助函数 run 轻松完成。

有任何想法吗？

4

2 回答 2

1

有趣的问题。我认为您应该以某种方式使用惰性评估。我不知道如何使用它，因为我从来没有这样做过，我不得不承认我并没有真正深入研究它，但在短暂的“谷歌搜索”之后，我想我可以提供一些有用的链接。

所以，我的第一个猜测是：

fun pairFirst f1 f2 i1 =
    fn () => pairFirst f2 f1 (f1 i1)

正如你在 LISP 中所做的那样，但它显然在 SML 中不起作用。所以我用谷歌搜索了它。

首先，我发现 SML 确实支持惰性求值： http ://www.cs.cmu.edu/~rwh/introsml/core/lazydata.htm

引用：“首先，必须通过评估以下声明来启用 SML/NJ 的惰性评估机制：

Compiler.Control.Lazy.enabled := true; open Lazy;"

我试过了，但也没有用，所以我用谷歌搜索了更多： https ://github.com/trptcolin/euler-sml/blob/master/lazy_utils.sml

引用：“（* 最懒惰的细节来自标准 ML 编程，Robert Harper * 值得注意的例外：Compiler.Control.Lazy.enabled 已移至 Control.lazysml *）

Control.lazysml := true; open Lazy;"

从这两个链接的内容，我构建了我的第二个猜测：

Control.lazysml := true;
open Lazy;

fun lazy pair (f1: 'a -> 'a, f2: 'a -> 'a, i1: 'a) : 'a susp  =
    pair (f2, f1, (f1 i1))

SML 以某种方式“吞下”了它：

- [opening /home/spela/test.sml]
val it = () : unit
opening Lazy

  datatype 'a susp = $ of 'a
val pair = fn : ('a -> 'a) * ('a -> 'a) * 'a -> 'a susp
val pair_ = fn : ('a -> 'a) * ('a -> 'a) * 'a -> 'a
val it = () : unit

它有效吗？我不知道 ：）

- pair ((fn x => x + 1), (fn y => y - 1), 1);
val it = $$ : int susp

我没有阅读这些链接，但我还找到了一篇我也没有阅读的文章，但我相信它提供了您正在寻找的答案：

http://www.cs.mcgill.ca/~bpientka/courses/cs302-fall10/handouts/lazy-hof.pdf

我相信这些链接可以回答您的问题。

如果有人熟悉这个话题，请回答这个问题，我认为这对我们许多人来说会很有趣。

最好的问候，斯佩拉

于 2014-12-21T20:14:09.943 回答
1

谢谢你的推波助澜！你的想法是在正确的轨道上。

所以通常情况是这样的：您实际上确实使用了惰性评估。无论如何，我们在这里使用我们自己的惰性结构（您可以在 ml 中创建自己的结构）。

使用我前面提到的函数 run，我可以创建一个在 i1 上运行 m1 的函数，然后在它下面的一个相互递归函数中调用它。最后我会一起调用这个函数！这是它的样子：

  fun pair(m1, m2, i1)=
    let
      fun p1 () = run (m1) (delay(fn() => Gen(i1,p2())))
      and p2 () = run (m2) (p1())
    in
      p1()
    end

这里 delay 和 Gen 是我结构的一部分。Gen 表示一个流，i1 作为第一个元素，p2() 作为其余元素。delay 接受一个函数，通常代表此实现中的惰性部分。使用相互递归函数（相互调用的函数，通过键入“and”而不是上面的“fun”来启用）我可以来回移动等等。

信不信由你，还有另一种更简单的方法可以实现，但这是针对初学者的。如果您有任何方法可以改进此答案（或其他解决方案），欢迎您分享！谢谢

于 2015-01-03T02:39:46.777 回答