SML with lazy list function

Question

I'm trying to make a function which can return the specific nth element of lazylist.

Here is what I made:

datatype 'a lazyList = nullList
                 | cons of 'a * (unit -> 'a lazyList)

fun Nth(lazyListVal, n) = (* lazyList * int -> 'a option *)
    let fun iterator (laztListVal, cur, target) =
        case lazyListVal of
             nullList => NONE
           | cons(value, tail) => if cur = target
                                  then SOME value
                                  else iterator (tail(), cur+1, target)
    in
        iterator(lazyListVal,1,n)
    end

I expected the result that as recusing proceeds, eventually the variable cur gets same as the variable target, and then the function iterator returns SOME value so it will return the final nth element.

But when I compile it and run, it only returns the very first element however I test with the lazylist objects.

Please figure what is the problem. I have no idea...

cf) I made another function which is relevant to this problem, the function that transforms lazylist into SML original list containing the first N values. Codes above:

fun firstN (lazyListVal, n) = (* lazyList * int -> 'a list *)
    let fun iterator (lazyListVal, cur, last) =
        case lazyListVal of
             nullList => []
           | cons(value, tail) => if cur = last
                                  then []
                                  else value::iterator(tail(),cur+1,last)
    in
        iterator(lazyListVal,0,n)
    end          

The strange thing is the function firstN is properly working.

Answer 1

The problem is that your iterator function does case lazyListVal of ..., but the recursive tail is called laztListVal, so for every iteration, it keeps looking at the first list. Use better variable names to avoid this kind of "invisible" bug.

For a simpler definition of nth:

datatype 'a lazyList = NullList | Cons of 'a * (unit -> 'a lazyList)

fun nth (NullList, _) = NONE
  | nth (Cons (x, xs), 0) = SOME x
  | nth (Cons (_, xs), n) = nth (xs (), n-1)

val nats = let fun nat n = Cons (n, fn () => nat (n+1)) in nat 0 end

val ten = nth (nats, 10)

Edit: While function pattern matching is ideal here, you could also have used a case ... of ... here. A helper function seems unnecessary, though, since you can simply use the input argument n as the iterator:

fun nth (L, n) =
    case (L, n) of
         (NullList, _) => NONE
       | (Cons (x, xs), 0) => SOME x
       | (Cons (_, xs), n) => nth (xs (), n-1)

You may however want to make the function more robust:

fun nth (L, n) =
    let fun nth' (NullList, _) = NONE
          | nth' (Cons (x, xs), 0) = SOME x
          | nth' (Cons (_, xs), n) = nth' (xs (), n-1)
    in if n < 0 then NONE else nth' (L, n) end

Here having a helper function ensures that n < 0 is only checked once.

(You could also raise Domain, since negative indices are not well-defined.)