Seuqences in ML (finite & infinnite)

Question

Okay,

I've got the next definition of sequence:

datatype 'a seq = Nil | Cons of 'a * (unit-> 'a seq);

I need to implement the next function:

filterq_n:('a -> bool) -> int -> 'a seq -> 'a seq

The function gets a predicate function which returns true or false, n (integer) and sequence.

The functionality:

1. if n<=0 return the same seq.
2. else return a seq that its first n elements are the first n elements in the original seq that predicate returns true for them and the rest will be the same.

For example, if the predicate is (x mod 2) and the seq is 1,2,3,4,5... and n is 3 so the new seq is 2,4,6,7,8,...

In addition, I should check another 2 options:

2.1) if the seq is finite and has less than n elements that predicate returns true for them then the new seq will contain only the elements that predicate returns true for them.

2.2) if the seq is infinite and has less than n elements that predicate returns true for them then the new seq will contain all the elements that predicate returns true for them and when trying to get the next element it will enter to an infinite loop.

My current code logically was planned for now without considering 2.1 and 2.2 (although I get errors and can find why?)

fun     filter_n (predicate: 'a -> bool ) (n: int)  Nil = Nil
|       filter_n (predicate: 'a -> bool ) (n: int) (Cons(x, xf)) =      
            if(n <= 0)  then Cons(x, xf) 
                        else 
                            if predicate x then Cons(x, fn() => filter_n predicate n-1 (xf()) ) 
                            else  filter_n predicate n-1 (xf())  
;

syntax errors or drastic change..I am not sure?

(also, for 2.1 ans 2.2 I just need to check that if I got (Nil and n>0) then return Nil? )

Thanks in advance for any help.

Answer 1

You need to wrap n-1 in parens, otherwise it's interpreted as multiple arguments. After you did that, it will compile.

However there's still a logic error in your code: You're decreasing n whether the predicate matches or not. However the specification says that you should select n elements where the predicate matches, not that you should check the predicate for n elements. So you should only decrease n if the predicate matches and keep the same n otherwise.

Once you've fixed that, your code should meet the specification (including 2.1 and 2.2).