在SML中合并无限列表 [英] Merge infinite lists in SML

问题描述

在SML中，我创建了三个无限列表，分别是fibonacci，evenfib和oddfib.现在，我要创建第四个列表，其中包含前10个数字evenfib和前10个数字oddfib，并使用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;   

解决方案

首先，您可能要考虑简化谓词函数，因为它们不必要地冗长.在我的拙见中，这是等效的并且具有更好的样式:

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或为包含某些类型为'a的值和能够生成下一个流元素的函数的Cons.

因此，在评估第二个元素之前，我们可以有所不同，直到我们实际调用该函数为止.

无限的自然数流

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

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

此处自然是包含所有自然数的无限流.您可以看到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函数来获得(奇数，偶数)斐波那契压缩后的数据流数字，然后从生成的流中，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)

In SML I have created three infinite lists namely fibonacci, evenfib and oddfib. Now what I want to do is create a fourth list which will contain the first 10 numbers of evenfib and the first 10 numbers of oddfib and merge them into pairs of one evenfib and one oddfib using the zip function and create a fourth list.

I have written a zip function as follows but it doesn't work.

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;   

解决方案

First, you may want to consider simplifying your predicate functions, because they are unnecessarily verbose. This is equivalent and of better style in my humble opinion:

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

About the Stream Data Type

Since SML has strict evaluation, the traditional list won't do the trick. You must start by defining your own stream data type. A stream is a delayed list.

Your definition of the fibs function seems to imply the existence of such data type:

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

As you can see an element of type 'a stream can either be Empty or be a Cons containing some value of type 'a and a function that is capable of generating the next stream element.

By this we can differ when that second element is evaluated until we actually invoke the function.

An Infinite Stream of Natural Numbers

For instance, you could define an infinite stream of natural numbers like this:

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

Here naturals is an infinite stream containing all natural numbers. You can see the Cons contains only the first element, and the second element is a function, that, when evaluated, could generate yet another stream element, this time containing 2, and so on.

The Need of a Library of Stream Functions

Evidently, you cannot use this data structure with the traditional list functions. You would need to write your own functions to deal with this data type.

For instance, you could write your own take function, that takes n elements out a stream creating a finite stream out of the original one:

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()))

Or you could create your own filter function to filter elements out of the stream creating yet a new stream in the process.

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())

And you would need a zip function that zips the elements of two streams into yet another zipped stream, like so:

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()))

You may even like to have a function that converts a finite stream into a list, just for debugging purposes, since lists are simpler to read in the REPL:

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

For instance:

• toList (take 10 (from 1)) would get the first 10 natural numbers as a list.
• filter odd would produce a function that only gets odd elements out of a int stream.
• filter even would produce a function that only gets even elements out of a int stream.
• etc,

Infinite Stream of Fibonacci Numbers

Assuming an infinite streams of Fibonacci numbers:

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

You could now use the filter odd and filter even functions to filter out only even or odd Fibonacci numbers, and then use the zip function with these two results to obtain a zipped stream of (odds,evens) Fibonacci numbers and from the generated stream, you can take out the first 10 elements...

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

...which you can ultimately turn into a list like so:

val r = toList (take 10 zipped)

这篇关于在SML中合并无限列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！