CODEWITHSUNDEEP
listzipsml
jack
jack

Reputation: 313

Merge infinite lists in SML

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;

Upvotes: 2

Views: 2198

Answers (2)

Edwin Dalorzo
Edwin Dalorzo

Reputation: 78629

First, you may want to consider simplifying your predicate functions, because they are unnecessarily verbose. This is equivalent and of better style in my 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)

Upvotes: 7

Tayacan
Tayacan

Reputation: 1826

You're trying to take infinite lists and zip them into a normal list of tuples. The problem with this is that normal lists can't really handle infinity. Instead, you can zip them into your own list type:

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

Don't use HD and TL (or hd and tl for built-in lists, for that matter) if you can avoid it. Pattern-match instead:

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

Upvotes: 2

Related Questions