SCHEMA - nombre de mêmes éléments atomiques dans une liste comme (un (ab) (bc))

Question

Je voudrais vous demander de l'aide avec les éléments suivants:

Quand j'appliquer une procédure de nombre de éléments sur la liste, j'ai besoin d'avoir une liste de paires, où la première place de la paire est l'élément et à la deuxième place (après le point) il y a un certain nombre d'éléments qui se sont produits dans la liste.

Par exemple, lorsque vous tapez ceci:

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

je suis arrivé ceci:

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

Je Jusqu'à présent, un code de travail sur la liste régulière (a b a 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))) 

Mais si je l'utilise sur:

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

Je suis arrivé ceci:

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

Je sais que je dois utiliser une récursivité profonde, mais je ne sais pas, comment l'implémenter dans le code que j'ai réellement.

Merci beaucoup pour votre aide.

Ondrej

Answer 1

Vous avez déjà fait la plupart des travaux en comptant les éléments - mais voir les différentes implémentations de bagify pour une mise en œuvre plus simple. Une solution simple pour faire face à des sous-listes imbriquées serait flatten la liste d'entrée avant de compter les éléments:

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

=> '((a . 3) (b . 4) (c . 3)) 

Si votre interprète ne définit pas flatten, il est facile à mettre en œuvre:

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

C'est la manière idiomatique de penser à des solutions dans Scheme: décomposer le problème en parties, puis utiliser des procédures intégrées pour résoudre chaque sous-partie, et enfin les combiner.