Trouver un chemin Schéma

Question

Je suis nouveau à Scheme et aujourd'hui j'ai rencontré le problème suivant que je n'ai pas pu résoudre. J'ai la représentation suivante pour les nœuds d'un arbre représentant un système de fichiers:

(contenu directory_name) pour les répertoires
nom_fichier pour les fichiers
(directory_name null) pour un répertoire vide

Par exemple, (» etc/"((" network/"(" interfaces ")))) est l'arbre pour le chemin etc/network/interfaces.

Ce que je dois faire est d'écrire une fonction qui prend comme arguments ce type d'arbre et un répertoire/nom de fichier et retourne le chemin, s'il y en a un. Si le répertoire/fichier n'existe pas, il renvoie #f.

Par exemple:

(define tree '("/" 
       (("etc/" ("network/" ("interfaces"))) 
       ("root/" null)))) 

Supposant nom est get-chemin de la fonction, en cours d'exécution (get-chemin arbre "interfaces"), il affichera "/ etc/network/interfaces". Tout ce que je veux est une idée, si vous pouvez m'en donner un, je serai reconnaissant.

Answer 1

Voici une réponse pour vous. J'ai utilisé des symboles pas de chaînes pour le répertoire/fichiers et légèrement changé le format de l'arborescence.

(define tree '(root (etc (passwd) (profile)) (usr (bin) (lib)))) 

(define (get-path tree name) 
    (define (reverse-if l) (and l (reverse l))) 
    (reverse-if 
    (let descending ((tree tree) (path '())) 
    (and (not (null? tree)) 
      (let ((root (car tree)) 
       (subs (cdr tree))) 
      (if (eq? root name) 
       (cons root path) 
       (let looking ((subs subs)) 
        (and (not (null? subs)) 
         (or (descending (car subs) (cons root path)) 
          (looking (cdr subs))))))))))) 

Avec des résultats:

> (get-path tree 'etc) 
(root etc) 
> (get-path tree 'bin) 
(root usr bin) 
> (get-path tree 'profile) 
(root etc profile) 
> (get-path tree 'foo) 
#f 
>