recursion - SCHEME - number of same atomic elements in a list like (a (a b) (b c)) -

i ask following:

when apply procedure number-of-elements on list, need list of pairs, on first place in pair element , on second place (after dot) there number of elements occured in list.

for example, when typing this:

(number-of-elements '((a b c) (b c) c (a b b))) 

i got this:

((a . 3) (b . 4) (c . 3)) 

so far have code working on regular list (a b d).

(define number-of-elements  (lambda (lst)   (define exclude   (lambda (sznm key)     (foldr (lambda (ass result)              (if (equal? (car ass) key)                  result                  (cons ass result)))            '()            sznm))) (foldr (lambda (key bag)          (cond ((assoc key bag)                 => (lambda (old)                      (let ((new (cons key (+ (cdr old) 1))))                        (cons new (exclude bag key)))))                (else (let ((new (cons key 1)))                        (cons new bag)))))        '()        lst))) 

but if use on:

(number-of-elements '((a b c) (b c) c (a b b))) 

i got this:

(((a b c) . 1) (a . 1) ((b c) . 1) (c . 1) ((a b b) . 1)) 

i know need use deep recursion, not know, how implement code have.

thanks lot help.

ondrej

you did of work counting elements - see different implementations of bagify simpler implementation. 1 straightforward solution dealing nested sublists flatten input list before counting elements:

(number-of-elements  (flatten   '((a b c) (b c) c (a b b))))  => '((a . 3) (b . 4) (c . 3)) 

if interpreter doesn't define flatten, it's easy implement:

(define (flatten lst)   (if (not (list? lst))       (list lst)       (apply append (map flatten lst)))) 

this idiomatic way think solutions in scheme: decompose problem in parts, use built-in procedures solve each subpart, , combine them.