CODEWITHSUNDEEP
schemeracketmembersublistaccumulate
Funnel
Funnel

Reputation: 13

Implementing sublist? using accumulate in Racket

I need to implement sublist? as a one-liner function that uses accumulate. It is suppose to return true if set1 is in set2.

Something like this:

(define subset?
  (lambda (set1 set2)
    (accumulate member? (car set1) (lambda (x) x) set2)))

Honestly I think I'm just confused on how accumulate is suppose to work with member, or if member is even the right choice for the operator.

My accumulate function is:

(define accumulate
  (lambda (op base func ls)
    (if (null? ls)
      base
      (op (func (car ls))
        (accumulate op base func (cdr ls))))))

and member?:

(define member?
  (lambda (item ls)
    (cond ((null? ls) #f)
      ((equal? item (car ls)) #t)
        (else (member? item (cdr ls))))))

Upvotes: 1

Views: 839

Answers (1)

Renzo
Renzo

Reputation: 27424

To give the correct definition of subset? first we must understand how the function accumulate works and the meaning of its parameters.

If we “unfold” the recursive definition, we can see that accumulate applies the binary operator op to all the results of applying func to the elements of list ls. And since the list can be empty, in these cases the function is defined to give back the value base.

So, for instance, assuming the recursive execution of the function, the following expression

(accumulate + 0 sqr '(1 2 3))

produces 14, since it is equivalent to:

(+ (sqr 1) (+ (sqr 2) (+ (sqr 3) 0)))

that is 1 + 4 + 9 + 0.

To solve your problem, you have to define a call to accumulate that applies the same operator to a list of elements and then combine the results. In you case, the operation to be applied is a test if an element is member of a list (member?), and you can apply it to all the elements of set1. And you should know, from the definition of the subset, that a set s1 is subset of another set s2 if and only if all the elements of s1 are contained in s2. So the operator that must be applied to combine all the results of the test is just the and boolean operator, so that it will be true if all the elements of s1 are member of s2 and false otherwise. The last thing to decide is the base value: this should be true, since an empty set is always contained in another set.

So this is a possible definition of subset?:

(define (subset? set1 set2)
  (accumulate
    (lambda (x y) (and x y))      ;; the combination operator
    #t                            ;; the value for the empty list
    (lambda(x) (member x set2))   ;; the function to be applied to all the elements of
    set1))                        ;; the set set1

Upvotes: 1

Related Questions