Глубина атомов в списке

Question

Я пытаюсь найти глубину каждого элемента в списке и одновременно создать выход, где сплющенный выход записывается с их уровнем глубины, до сих пор я придумал следующую логику -

(define nestingDepth 
(lambda (lst1) 
    (cond ((null? lst1) 1) 
      ((list? (car lst1)) 
      (cons(+ 1(nestingDepth (car lst1)))) (nestingDepth (cdr lst1)))   
      ((null? (cdr lst1)) (cons (1 (cdr lst1))) (nestingDepth (cdr lst1)))))) 

Но это не печатает ничего на выходе. Пожалуйста, уточните, где я ошибаюсь. Ожидаемый результат будет выглядеть - вход - «(а (б) в) выход - (1 2 б 1 с)

Answer 1

Как некоторые другие ответы уже упоминалось, это важно убедитесь, что каждый случай возвращает нечто подходящее. Если вход представляет собой пустой список, то выход должен быть пустым. Если вход представляет собой пару, тогда вам необходимо обрабатывать автомобиль и cdr пары и подключать их. Если вход не является ни пустым списком, ни парой, то результатом будет список глубины и ввода.

Теперь может быть полезно создать результат поэтапно. Вы можете построить из справа налево, и добавляете каждый элемент и его глубину, используя такой подход, как следующее:

(define (depths tree) 
    (let depths ((tree tree) 
       (depth 0) 
       (results '())) 
    (cond 
     ((null? tree) results) 
     ((pair? tree) (depths (car tree) 
          (+ 1 depth) 
          (depths (cdr tree) 
            depth 
            results))) 
     (else (cons depth (cons tree results)))))) 

> (depths '(a ((b) c ((d))) e)) 
(1 a 3 b 2 c 4 d 1 e) 

Answer 2

Вот один из возможных решений (я изменил формат вывода немного, чтобы сделать решение проще кодировать). append-map определен в SRFI 1.

(define (depths x) 
    (cond ((list? x) 
     (append-map (lambda (y) 
         (map (lambda (z) 
           (cons (car z) (+ (cdr z) 1))) 
          (depths y))) 
        x)) 
     (else `((,x . 0))))) 

(я пишу код, как опытный Schemer бы писать его, а не как кто-то написал бы домашнее задание. Если это ваша ситуация, попытайтесь понять, что мой код делает, а затем переформулировать его в чем-то домашнем задании приемлемого .)

Answer 3

Исходный код неправильный (вы не можете вернуть 1, если вы намерены вывести список в результате), способ, которым рекурсия продвигается, не создает список как вывод ... полная переписывание необходимости; следующее решение является портативным и должен работать на любой интерпретатор Scheme, используя только основных процедур:

(define (nestingDepth lst) 
    (let depth ((lst lst) (n 1)) 
    (cond ((null? lst) '()) 
      ((not (pair? (car lst))) 
      (cons n 
       (cons (car lst) 
         (depth (cdr lst) n)))) 
      (else 
      (append (depth (car lst) (+ 1 n)) 
        (depth (cdr lst) n)))))) 

Выход, как ожидалось:

(nestingDepth '(a (b (c (d e))) f g)) 
=> '(1 a 2 b 3 c 4 d 4 e 1 f 1 g) 

Answer 4

Всех предыдущих решений работает хорошо для правильных (вложенных) списков , для тех, кто работает для неправильных списков, я не уверен, что они верны.

Например, (depths '(a . b)) дает (1 a 0 b) для Джошуа и (((a . b) . 0)) для Криса, но я бы сказал, что это должно быть (1 a 1 b).

я поэтому пойти на

(define (depths sxp) 
    (let loop ((sxp sxp) (res null) (level (if (cons? sxp) 1 0))) 
    (cond 
     ((null? sxp) res) 
     ((pair? sxp) (let ((ca (car sxp))) 
        (loop ca 
          (loop (cdr sxp) res level) 
          (if (pair? ca) (add1 level) level)))) 
     (else  (cons level (cons sxp res)))))) 

и мои тестовые случаи:

(check-equal? (depths '(a . b)) '(1 a 1 b)) 
(check-equal? (depths 'a) '(0 a)) ; 0 
(check-equal? (depths '(a)) '(1 a)) 
(check-equal? (depths '(a a)) '(1 a 1 a)) 
(check-equal? (depths '(a (b . c) d (e (f (g h . i) . j)))) '(1 a 2 b 2 c 1 d 2 e 3 f 4 g 4 h 4 i 3 j)) 

(check-equal? (depths '(a (b) c)) '(1 a 2 b 1 c)) 
(check-equal? (depths '(a ((b) c ((d))) e)) '(1 a 3 b 2 c 4 d 1 e)) 
(check-equal? (depths '(a (b (c (d e))) f g)) '(1 a 2 b 3 c 4 d 4 e 1 f 1 g))