CODEWITHSUNDEEP
scheme
daveyjones
daveyjones

Reputation: 123

Scheme looping through an expression that contains lists

I am doing a question in Scheme which is to create a function which takes in an object and an expressions e.g (foo 'x '(x 10 x x 4)) and has to return all of the objects that follow the given object, so the above function call would return (10 x 4). However, the expression can also contain lists e.g (foo 'y '(y (3 y 5 y y 8 9) (10 y 12 13 y 15 y) 17)) should return ((3 y 5 y y 8 9) 5 y 8 12 15). I am having trouble when they contain lists. Here is my code so far.

(define (foo target expression)
  (cond [(null? expression)]
        [(list? (first expression)) (foo target (first expression))]
        [(eqv? (first expression) target) (cons (first (rest expression)) (foo target (rest expression)))]
        [(not (eqv? (first expression) target)) (foo target (rest expression))]))

So when the expression contains a list, I am trying to recursively call the function on that list, however, I do not know how to get back to the original expression to continue searching.

So when I call (foo 'y '(y (3 y 5 y y 8 9) (10 y 12 13 y 15 y) 17)) I am getting ((3 y 5 y y 8 9) 5 y 8 . #t) so it successfully loops through the first list however it stops after that and does not reach the second list in the expression

Also, one other problem I am having is the boolean at the end of my result, I know this is because of the line cond [(null? expression)], I added this because I was getting an error when it gets to the end of the expression, how can I fix this?

Upvotes: 1

Views: 187

Answers (1)

assefamaru
assefamaru

Reputation: 2789

Note that (cons x (cons y ... becomes a proper list only when you terminate it with the empty list '(). Hence (cons x (cons y ... empty)) is proper, and equivalent to (list x y ...), as opposed to what you have: (cons x (cons y ... #t)). You can fix this by making '() the result of your base case.

But you also need a second base case to test when the input list has less than 2 elements. This is because your function tries to access the second element later as (first (rest expression)). So in order to make sure that this is valid, you need to ensure that expression constains at least 2 elements. This can be done as ... (null? (rest expression)) ... in your cond cases.

On the other hand, you function only iterates the first list element it encounters because of this line:

[(list? (first expression)) (foo target (first expression))]

In this case, you only handle (first expression), but you need to handle both (first expression) and (rest expression). Since you are reconstructing a list, you could use cons as:

(cons (foo target (first expression))
      (foo target (rest expression)))

but this recreates the depth of your original list. From your desired output examples, it seems that you want to flatten the result, so a better option would be to append them as:

(append (foo target (first expression))
        (foo target (rest expression)))

Consider the following rewrite:

(define (foo obj expr)
  (cond
    [(null? expr) #f]
    [(null? (rest expr)) '()]
    [(pair? (first expr))
     (append (foo obj (first expr))
             (foo obj (rest expr)))]
    [(equal? obj (first expr))
     (cons (second expr)
           (foo obj (rest expr)))]
    [else
     (foo obj (rest expr))]))

then you will have:

(foo 'x '(x 10 x x 4))
=> '(10 x 4)
(foo 'y '(y (3 y 5 y y 8 9) (10 y 12 13 y 15 y) 17))
=> '((3 y 5 y y 8 9) 5 y 8 12 15)

but you will also have:

(foo 'x '())
=> #f
(foo 'x '(x))
=> '()

Upvotes: 1

Related Questions