I am trying to build filter (a built-in function) using Racket just as a matter of practice.
I created the following code:
(define (filter lista-1 check-function)
(define (fil-iter lista-1 check-function lista-2)
(cond ((null? lista-1) lista-2)
((check-function (car lista-1)) (fil-iter (cdr lista-1) check-function (append lista-2 (list (car lista-1)))))
(else (fil-iter (cdr lista-1) check-function lista-2))))
(trace fil-iter)
(fil-iter lista-1 check-function '()))
I made a few tests with "odd?", "even?" and "number?" as the "check-function".
All of the outputs were correct. But I might be not seeing something... My intuition says that there is something wrong here.
Your function is correct, only it has a complexity of n² while it could have a complexity of n.
The reason is that you use append instead of cons to build the result, and append has a cost proportional to the length of the list, while cons has a constant cost. So, if you want a function with linear complexity you should write something like:
(define (filter lista-1 check-function)
(define (fil-iter lista-1 check-function lista-2)
(cond ((null? lista-1) (reverse lista-2))
((check-function (car lista-1))
(fil-iter (cdr lista-1) check-function (cons (car lista-1) lista-2)))
(else (fil-iter (cdr lista-1) check-function lista-2))))
(fil-iter lista-1 check-function '()))
Note that at the end the result must be reversed, but this does not change the complexity of the function since reverse has a linear complexity with the size of the list and is executed only once, at the end of the function.
You can also simplify the function noting that the parameter check-function is not modified at each invocation of the helper fil-iter, so it could be omitted inside it:
(define (filter lista-1 check-function)
(define (fil-iter lista-1 lista-2)
(cond ((null? lista-1) (reverse lista-2))
((check-function (car lista-1))
(fil-iter (cdr lista-1) (cons (car lista-1) lista-2)))
(else (fil-iter (cdr lista-1) lista-2))))
(fil-iter lista-1 '()))