Racket에서 재귀를 사용하여 목록 반환

Question

이중 재귀가있는 메서드에서 목록 (BST, 이진 검색 트리)을 반환하려고합니다. 나는 다음과 그것을 구현하기 위해 노력하고 있습니다 :

(define (mapBST BST someFunct) 
    (cond 
    [(null? BST) 
    '()] 
     [else (cons (car BST) (someFunct (car (cdr BST)))) (mapBST (car (cdr (cdr BST))) someFunct) (mapBST (car (cdr (cdr (cdr BST)))) someFunct) ] 

) 
) 

이것은 내가이 조각을 시도

(define bst 
      '(3 "3" 
        (1 "1" 
        () 
        (2 "2"()()) 
       ) 
        (5 "5"()()) 
      ) 
) 
(mapBST bst string->number) 

코드의이 작은 조각으로 호출되는하지만 ((()())()) 반환

[else (printf (car (cdr BST))) (cons (mapBST (car (cdr (cdr BST))) someFunct) (mapBST (car (cdr (cdr (cdr BST)))) someFunct)) ] 

을 결과는 동일한 BST를 반환해야하지만 string 대신 숫자를 값으로 사용합니다.

Answer 1

다른 표현식에서는 이진 검색 트리를 제대로 재구성하지 않으므로 빈 목록이 나타납니다.

... 
[else 
(cons (car BST) 
     (cons (someFunct (car (cdr BST))) 
      (cons (mapBST (car (cdr (cdr BST))) someFunct) 
        (cons (mapBST (car (cdr (cdr (cdr BST)))) someFunct) empty))))] 
... 

또는

... 
[else 
(list (car BST) 
     (someFunct (car (cdr BST))) 
     (mapBST (car (cdr (cdr BST))) someFunct) 
     (mapBST (car (cdr (cdr (cdr BST)))) someFunct))] 
... 

에 else 사건을 변경하면 문제를 ((cons 1 (cons 2 empty))이 (list 1 2)에 해당하기 때문에 두 옵션 모두 같은리스트를) 해결됩니다. 여기

이 mapBST의 전체 업데이트입니다 : 예를 들어

(define (mapBST proc BST) 
    (cond 
    [(null? BST) empty] 
    [else 
    (list (car BST) 
      (proc (cadr BST)) 
      (mapBST proc (caddr BST)) 
      (mapBST proc (cadddr BST)))])) 

,

(define BST '(3 "3" (1 "1"() (2 "2"()())) (5 "5"()()))) 
(mapBST string->number BST) 
=> '(3 3 (1 1() (2 2()())) (5 5()())) 

Answer 2

으로는 다른 답변에서 지적, 당신은 실제로 당신이 else 절에 어떤 생각 반환되지 않습니다 . 이를 수정하면 프로그램이 작동합니다. 그러나 이런 종류의 (car (cdr (cdr ...)))은 사람들이 1960 년대에 Lisp을 작성하는 방법이었습니다. Lisp은 완전히 불투명하기 때문에 나쁜 이름을 얻었습니다. caddr과 같은 것을 사용하는 것이 더 좋지만, 약간만 (그리고 그 중 얼마나 많은 언어가 제공됩니까? 기억이 안납니다). 데이터가 개념적으로 목록 경우 그들은 당신이 실제로 무슨 뜻인지 말 때문에 여전히 더 나은, first & second 같은 이름을 가진 함수를 사용하는 것입니다 (데이터가 다음, 개념적으로 conses의 나무 인 경우 car & 다 더 나은 아마). 그러나 그들은 여전히 ​​'얼마나 많은 이들이 이번 주에 문제가 있는지'를 가지고있다.

적절한 해결책은 데이터 구조에 따라 변수를 바인딩하는 패턴 화 또는 &/destructuring을 사용하는 것입니다. 이렇게하면 코드가 실제로 명확 해집니다. 라켓은이를 위해 포괄적 인 메커니즘을 가지고 있습니다. 실제로는 자세하게 이해하지 못하지만, 충분히 이해할 수 있습니다.

(define (map-bst bst fn) 
    (match bst 
    ['() '()] 
    [(list 1st 2nd 3rd 4th) 
    (list 1st 
      (fn 2nd) 
      (map-bst 3rd fn) 
      (map-bst 4th fn))] 
    [_ (error "botch")])) 

(더 나은 변수 이름과 함께 할 수있는이 주 : 나는 구조의 다양한 비트가 무슨 뜻인지 모르는) 다음 작업을 할 match를 사용하는 함수의 (고정 된) 버전입니다.