CODEWITHSUNDEEP
listscheme
kliz
kliz

Reputation: 1

Scheme: remove elements from nested list

Given a propositional formula, i. e. ((a and (b implies c) or (d and (e implies f)))), I need to write a Scheme function to remove the connectives, and, implies, or. The the return of the function contains all variables in the formula. For instance, (a b c d e f).

I am not sure how to even get started on this, because I am unsure how to get inside the nested lists and remove and cons certain variables and connectives.

Upvotes: 0

Views: 2424

Answers (1)

Yasir Arsanukayev
Yasir Arsanukayev

Reputation: 9676

I would start up with something like the following:

(define somelist
  (list 'a 'and (list 'b 'implies 'c) 
        'or (list 'd 'and (list 'e 'implies 'f))))

(define (remove-vars xs ys)
  (let ((xs-f (flatten xs)))
    (filter-two xs-f ys)))

(define (filter-two xs ys)
  (foldr (lambda(y acc)
           (filter (lambda(x) (not (eq? x y))) acc))
         xs
         ys))

Test:

> (remove-vars somelist (list 'and 'or 'implies))
(a b c d e f)
> (remove-vars somelist (list 'and 'or))
(a b implies c d e implies f)

UPDATE: OK, @karategeek6 reported, that he doesn't have flatten and filter in his Scheme interpreter, and I'm not sure you do, so let's implement them manually, because there are no filter and flatten in R^6RS either:

(define (my-flatten xs)
  (foldr
   (lambda(x acc)
     (if (list? x)
         (append (my-flatten x) acc)
         (cons x acc)))
   (list)
   xs))

(define (my-filter pred xs)
  (let recur ((xs xs)
              (acc (list)))
    (if (empty? xs)
        (reverse acc)
        (if (pred (car xs))
            (recur (cdr xs) (cons (car xs) acc))
            (recur (cdr xs) acc)))))

Modify remove-vars and filter-two appropriately:

(define (remove-vars xs ys)
  (let ((xs-f (my-flatten xs)))
    (filter-two xs-f ys)))

(define (filter-two xs ys)
  (foldr (lambda(y acc)
           (my-filter (lambda(x) (not (eq? x y))) acc))
         xs
         ys))

You should get the same output as with previous versions of the above procedures.

Upvotes: 1

Related Questions