I'm trying to understand this piece of Scheme code, can someone explain it to me?

user_15661220 0
Viewed 87

I found this Scheme code on the internet, it outputs all subsets given a list, can someone explain how it works?

(define (subsets s) (if (null? s) 
  (list ()) 
    (let ((rest (subsets (cdr s))))(append rest (map (lambda (x) (cons (car s) x)) rest)))))

(subsets '(a b c))
scheme functional-programming
1 Answers

You really need to format it:

(define (subsets s)
  (if (null? s)
      (list ())
      (let ((rest (subsets (cdr s))))
        (append rest
                (map (lambda (x)
                       (cons (car s) x))
                     rest)))))

What it does is return (()) for the argument '()

For a one element argument eg. '(b) if binds rest to the subsets of every element execept the first.. Which is no elements so rest is (()) and then it returns a list consisting of all the elements in rest as well as each list element of rest with b added to front. Thus (() (b)).

For a two element argument eg. '(a b) it binds rest to the subsets of every element except the first. Which is (b) so we know from above that it is (() (b)) and we know it will use those as well as every element with a added to the beginning: (() (b) (a) (a b))

I could go on but I'm guessing you get the picture?

user_15656980
Related