问在SML中合并无限列表
EN

Stack Overflow用户

提问于 2013-11-02 06:04:54

回答 2查看 2K关注 0票数 2

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

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

list

zip

sml

回答 2

Stack Overflow用户

发布于 2013-11-02 22:22:54

首先，您可能想要考虑简化谓词函数，因为它们是不必要的冗长。在我的浅见中，这是等同的，风格更好：

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，也可以是包含一些'a类型的值和能够生成下一个流元素的函数的Cons。

这样，我们就可以在计算第二个元素时有所不同，直到我们实际调用该函数。

自然数的无限流

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

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个自然数，因为list.
filter odd将生成一个仅从int中获取奇数元素的函数stream.
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函数来获得一个压缩的(奇数，偶数)斐波那契数流，并且可以从生成的流中take出前10个元素……

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

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

val r = toList (take 10 zipped)

票数 6

Stack Overflow用户

发布于 2013-11-02 08:22:38

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

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

如果可以避免的话，不要使用HD和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 *)