list - 合并 SML 中的无限列表

Question

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

我写了一个 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;   

Answer 1

首先，您可能需要考虑简化谓词函数，因为它们不必要地冗长。在我看来，这是等效的且具有更好的风格:

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

关于流数据类型

由于 SML 具有严格的评估，因此传统的列表将无法解决问题。您必须首先定义自己的流数据类型。 stream是延迟列表。

您对 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 流中获取偶数元素。
• 等等，

无限的斐波那契数列

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

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

您现在可以使用 filter odd 和 filter even 函数仅过滤掉偶数或奇数斐波那契数，然后使用 zip函数与这两个结果一起获得压缩的(奇数，偶数)斐波那契数流，从生成的流中，您可以取出前 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)