2

在 SML 中，我创建了三个无限列表fibonacci，即evenfib和oddfib。现在我要做的是创建第四个列表，其中将包含前 10 个数字evenfib和前 10 个数字，并使用函数oddfib将它们合并成一对一evenfib和一并创建第四个列表。oddfibzip

我已经编写了一个如下的 zip 函数，但它不起作用。

fun fib a b = CONS(a, fn () => fib b (a + b));
fun odd n = if ( n mod 2 = 1) then true else false;
fun even n = if (n mod 2 = 0) then true else false;
val fibs = fib 0 1;
fun evenfibs l = FILTER even l;
fun oddfibs l = FILTER odd l;
fun zip x = case x of (L 'a inflist , N 'b inflist) => (HD L, HD N) :: zip (TL L, TL N) | => _ nil;
4

2 回答 2

6

首先，您可能需要考虑简化谓词函数，因为它们不必要地冗长。以我的拙见，这是等效的并且样式更好：

fun even n = n mod 2 = 0
fun odd n = n mod 2 <> 0

关于流数据类型

由于 SML 有严格的评估，传统的列表是行不通的。您必须从定义自己的流数据类型开始。流是延迟列表。

您对 fibs 函数的定义似乎暗示了这种数据类型的存在：

datatype 'a stream =  Empty | Cons of 'a  *  (unit -> 'a stream)

如您所见，类型元素'a stream可以是Empty或Cons包含某个类型值'a和能够生成下一个流元素的函数。

这样，在我们实际调用该函数之前，我们可以在评估第二个元素时有所不同。

自然数的无限流

例如，您可以定义一个无限的自然数流，如下所示：

fun from n = Cons(n, fn () => from(n +1))
val naturals = from(1)

这里的 naturals 是一个包含所有自然数的无限流。你可以看到 Cons 只包含第一个元素，而第二个元素是一个函数，当计算时，它可以生成另一个流元素，这次包含 2，依此类推。

流函数库的需求

显然，您不能将此数据结构与传统的列表函数一起使用。您需要编写自己的函数来处理这种数据类型。

例如，您可以编写自己的take函数，从一个流中取出 n 个元素，从原始流中创建一个有限流：

fun take n xs =
    if n = 0
    then Empty
    else case xs of
            Empty => Empty
          | Cons(h,t) => Cons(h, fn() => take (n-1) (t()))

或者，您可以创建自己的filter函数以从流中过滤元素，从而在此过程中创建一个新流。

fun filter f xs = 
   case xs of
      Empty => Empty
    | Cons(h,t) => if f(h)
                   then Cons(h, fn () => filter f (t()))
                   else filter f (t())

您需要一个将zip两个流的元素压缩到另一个压缩流中的函数，如下所示：

fun zip(xs,ys) = 
    case (xs,ys) of
        (Empty,_) => Empty
      | (_, Empty) => Empty
      | (Cons(h1,t1), Cons(h2,t2)) => Cons( (h1,h2), fn () => zip(t1(),t2()))

您甚至可能希望拥有一个将有限流转换为列表的函数，仅用于调试目的，因为列表在 REPL 中更易于阅读：

fun toList xs =
    case xs of
        Empty => []
      | Cons(h,t) => h::toList(t())

例如：

  • toList (take 10 (from 1))将获得前 10 个自然数作为列表。
  • filter odd将产生一个只从 int 流中获取奇数元素的函数。
  • filter even将产生一个仅从 int 流中获取偶数元素的函数。
  • ETC，

斐波那契数列的无限流

假设有无限的斐波那契数流：

fun fibonacci() = 
   let
      fun fib(a,b) = Cons(a+b, fn() => fib(b,a+b))
   in
      Cons(0, fn() => fib(0,1))
   end

您现在可以使用filter oddandfilter even函数仅过滤掉偶数或奇数斐波那契数，然后使用zip具有这两个结果的函数来获得（奇数，偶数）斐波那契数的压缩流，并从生成的流中，您可以take取出第一个10个元素...

val fibs = fibonacci()
val evens = filter even
val odds = filter odd
val zipped = zip(evens fibs, odds fibs)

...您最终可以变成这样的列表：

val r = toList (take 10 zipped)
于 2013-11-02T22:22:53.560 回答
2

您正在尝试获取无限列表并将它们压缩到正常的元组列表中。这样做的问题是普通列表不能真正处理无穷大。相反，您可以将它们压缩到您自己的列表类型中：

zip : 'a inflist * 'b inflist -> ('a * 'b) inflist

如果可以避免，请不要使用HDand TL（或hd用于tl内置列表）。改为模式匹配：

fun zip (CONS (a, f), CONS (b, g)) = CONS (...) (* try to fill this one in yourself *)
  | zip _ = NIL (* assuming your inflist datatype has a constructor for the
                   empty list called NIL *)
于 2013-11-02T08:22:37.823 回答