在SML中合并无限列表

Question

在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;   

Answer 1

首先,您可能需要考虑简化谓词函数,因为它们不必要地冗长.在我的拙见中,这相当于更好的风格:

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)

在这里,自然是包含所有自然数的无限流.你可以看到Cons只包含第一个元素,第二个元素是一个函数,在评估时,它可以生成另一个stream元素,这次包含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流中获取偶数元素的函数.
• 等等,

Fibonacci数的无限流

假设Fibonacci数量无限:

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函数来过滤掉偶数或奇数的Fibonacci数,然后使用zip这两个结果的函数来获得(odds,evens)Fibonacci数的压缩流,并且从生成的流中,您可以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)