>

cons, first, rest, empty? 등과 같은 기본 작업 만 사용하여 목록을 바꾸는 방법이 궁금합니다.

도우미 함수 나 누산기가 허용되지 않으며, 함수는 하나의 입력 (목록) 만 취합니다.

머리를 감쌀 수는 없지만 가능하다고 들었습니다.

이것이 내가 지금까지 개념화 한 것입니다. 나머지 목록에 대해 재귀를 형성하는 방법을 모르겠습니다.

(defunc rev-list (x)
  (if (or (equal (len x) 0) (equal (len x) 1))
      x
      (cons (first (rev-list (rest x)))
            ???)))

분명히 목록의 첫 번째와 마지막을 바꾸는 함수로 비슷한 것을 할 수는 있지만 완전히 이해하지는 못합니다. 코드는 다음과 같습니다.

(define swap-ends (x)
  (if (or (equal (len x) 0) (equal (len x) 1))
      x
      (cons (first (swap-ends (rest x))) 
            (swap-ends (cons (first x) 
                             (rest (swap-ends (rest x))))))))

  • 답변 # 1

    (참고 : 답변은이 게시물의 맨 아래에 있습니다)두 번째 기능

    (define (swap-ends x)                                   ; swap [] = []
      (if (or (equal (length x) 0) (equal (length x) 1))    ; swap [x] = [x]
          x                                                 ; swap (x:xs) 
          (cons (first (swap-ends (rest x)))                ;    | (a:b) <- swap xs 
                (swap-ends (cons (first x)                  ;    = a : swap (x : b)
                                 (rest (swap-ends (rest x))))))))
    
    

    (댓글에 Haskell 번역) 당신은 무엇을합니까? if 의 데이터 흐름도 의 대체 조항은

                      /-> first ----------------------> cons
    x --> first ------/-------------> cons --> swap --/
      \-> rest -> swap ---> rest ---/
    
    

    (왼쪽에서 오른쪽으로 화살표를 따라 가십시오). 그래서

    [] -> []
    [1] -> [1]
                         /-> 2 -----------------------> [2,1]
    [1,2] --> 1 --------/------------> [1] --> [1] --/
          \-> [2] -> [2] ---> [] ---/
                               /-> 3 -------------------------> [3,2,1]
    [1,2,3] --> 1 ------------/----------> [1,2] --> [2,1] --/
            \-> [2,3] -> [3,2] -> [2] --/
                                 /-----> 4 ----------------------------> [4,2,3,1]
    [1,2,3,4] --> 1 ------------/---------------> [1,3,2] -> [2,3,1] -/
              \-> [2,3,4] -> [4,3,2] -> [3,2] -/
    
    

    지금까지는 목록의 끝 요소를 바 꾸었습니다. 자연 유도로 증명해 보자

    true(N-1) => true(N) :

                          /-> N --------------------------------------> [N,2..N-1,1]
    [1..N] --> 1 ---------/-----------> [1,3..N-1,2] -> [2,3..N-1,1] -/
           \-> [2..N] -> [N,3..N-1,2]   /
                        -> [3..N-1,2] -/
    
    

    그래서 증명되었습니다. 따라서 우리는 (N-1)-길이리스트를 뒤집는 가정하에 N- 길이리스트를 뒤집는 데이터 흐름도를 고안해야한다 :

    [1..N] --> 1 ------------------------------------\
           \-> [2..N] -> [N,N-1..2] -> N -------------\------------------\
                         \-> [N-1,N-2..2] -> [2..N-1] -> [1..N-1] -> rev -> cons
    
    

    우리에게 구현을 제공하는 것

    (define (rev ls)                                 ; rev [] = []
      (cond                                          ; rev [x] = [x]
        ((null? ls) ls)                              ; rev (x:xs) 
        ((null? (rest ls)) ls)                       ;   | (a:b) <- rev xs 
        (else                                        ;   = a : rev (x : rev b)
          (cons (first (rev (rest ls)))
                (rev (cons (first ls)
                           (rev (rest (rev (rest ls))))))))))
    (rev '(1 2 3 4 5))     ; testing
    ;Value 13: (5 4 3 2 1)
    
    
    주석의 Haskell 번역은 다이어그램을 매우 자연스럽게 따릅니다. 실제로는판독 가능입니다 : a  마지막 요소 인 b  반전 된 "핵심"(즉, 첫 번째 요소와 마지막 요소가없는 입력 목록)이므로 반전 된 코어를 뒤집고 첫 번째 요소를 앞에 추가하여 입력 목록의butlast부분을 가져온 다음 뒤집습니다. 마지막 요소 앞에 붙입니다.간단합니다.:)

  • 답변 # 2

    (define (reverse x)
      (let loop ((x x) (y '()))
        (if (null? x)
            y
            (let ((temp (cdr x)))
              (set-cdr! x y)
              (loop temp x))))))
    
    

    효율적으로 수행하는 몇 가지 방법 중 하나입니다. 그러나 여전히 일종의 도우미 절차입니다.

    다른 방법이지만 꼬리 재귀는 아니며 추가 프로그램이 set-cdr을 사용하지 않는 경우! 큰 목록에는 실제로 사용할 수 없습니다.

    (define (reverse L)
      (if (null? l)
          '()
           (append (reverse (cdr L)) (list (car L)))))
    
    

  • 답변 # 3

    last 가 있습니까  그리고 butlast  당신의 환경에서? 그렇다면 절차를 다음과 같이 정의 할 수 있습니다 (Oscar는 일반적으로 문제에 접근하려는 방식이 아님을 지적하지만).

    (define (rev lst)
      (if (null? lst)
          '()
          (cons (car (last lst))
                (rev (butlast lst)))))
    
    
    다음은 last 의 정의입니다.  그리고 butlast . 기본 환경의 일부가 아닌 경우이 과제에 적합하지 않은 것처럼 들리지만 처음 시작할 때는 많은 재귀 절차를 읽고 생각하는 것이 좋습니다.

    (define (butlast lst)
      (if (or (null? lst) (null? (cdr lst)))
          '()
          (cons (car lst) (butlast (cdr lst)))))
    (define (last lst)
      (if (or (null? lst) (null? (cdr lst)))
          lst
          (last (cdr lst))))
    
    

  • 이전 java - Lucene 지수에서 가장 높은 빈도의 항을 구하십시오
  • 다음 javascript - angularjs의 헤더를 변경하는 방법 $httpjsonp