[OSSU] <UBCx HtC1x_How to Code> / 10_Accumulator

| Accumulator

 

말 그대로 뭔가를 누적해서 기억해야 한다는 뜻이다

만약 홀수 번째에 있는 숫자만 추출하겠다고 하면, 모든 애들의 포지션을 기억하고 있어야하는 거

파이썬으로 풀면 겁나 쉬운데, 이렇게 줄줄이 써놓으니까 눈에 진짜 안 들어오네 .... 이게 맞나 ... .ㅜㅜㅜ

 

이렇게 세 파트로 코드의 구조가 분리되어 있는 걸 눈으로 볼 수 있는게 진짜 중요한 자질이래!!

 

 

| Tail Recursion

 

 

이 식의 result가 함수 전체의 결과가 될 것이니까, 이게 바로 tail position이다 !

 

 

여기서는 bar 이 enclosing function이니까 ! 

그냥 최종적으로 실행되는 애가 tail이라고 보면 된다

 

 

in a tailrecursive function, there are no pending operations to be performed after the recursive call returns. This is important because it allows the compiler or interpreter to optimize the function so that it uses constant stack space, rather than growing the stack with each recursive call.

 

Tail recursion is particularly useful in functional programming languages, as many of them optimize tail-recursive calls automatically, making them as efficient as iterative loops in terms of memory usage. This is important because traditional recursive functions can potentially cause a stack overflow if the recursion goes too deep, while tail-recursive functions avoid this issue by reusing the same stack frame for each recursive call.

 

한 마디로, 계속 스택을 새로 만드는게 아니라, 있는 애를 사용하는라 훨씬 효율적이다 !!! 

숫자가 엄청 많아지면 리스트가 계속 커지니까, 그렇게 하는 대신 accumulator를 사용해보자

;; (listof Number) -> Number
;; produce sum of all elements of lon
(check-expect (sum empty) 0)
(check-expect (sum (list 2 4 5)) 11)

(define (sum lon)
  (cond [(empty? lon) 0]
        [else
         (+ (first lon)
            (sum (rest lon)))]))

(sum (list 1 2 3 4 5))

 

 

 

 

acc 를 사용해서 local 로 감싸주는거가 훨씬 효율적이다 

: add this to the result so far, and keep going 

 

 

 

 

 

| 전체 구조

 

 

 

잘 봐봐

 

0번 인덱스부터 시작해서, 매 n번째에 있는 애들 drop하고 나머지 리스트를 반환할거야

(check-expect (dropn empty 0) empty) ;base case
(check-expect (dropn (list "a" "b" "c" "d" "e" "f") 0) empty)
(check-expect (dropn (list 1 2 3 4 5 6 7) 1) (list 1 3 5 7))
(check-expect (dropn (list 1 2 3 4 5 6 7) 2) (list 1 2 4 5 7))

0번째 인덱스들을 계속 drop 할건지

rest의 1번째 인덱스들을 계속 drop할건지 등등

(define (dropn lon0 n)
  ;acc; number; the number of element to keep before dropping the next one
  ;(drop (list 1 2 3 4 5) 2) ;outer call
  
  ;(drop (list 1 2 3 4 5) 2) ;keep
  ;(drop (liss  2 3 4 5)  1) ;keep
  ;(drop (list    3 4 5)  0) ;drop
  ;(drop (list      4 5)  2) ;keep
  ;(drop (list        5)  1) ;keep
  
  (local [(define (dropn lon acc)
            (cond [(empty? lon) empty] ;base
                  [else
                   (if (zero? acc) ;include the first in the list
                       (dropn (rest lon) n) ;drop nth index 
                       (cons (first lon) (dropn (rest lon) (sub1 acc))))]))]
    (dropn lon0 n)))

일단,

비어있으면 empty

acc = 0일때는 drop 한다 바로

아닐때는, 남은 애들에서 첫번째거를 포함하고, 그게 포함됐으니까 나머지 중에서 sub1 acc 한 인덱스의 것을 drop

 

---

 

Problem1 : Contains? in tree

Starting with the following data definition for a binary tree (not a binary search tree), design a tail-recursive function called contains? that consumes a key and a binary tree  and produces true if the tree contains the key.

이진트리에서 search 문제인거다. 해당 트리의 모든 노드를 검색해서, key가 있는지 찾는 코드를 짜는 거!

 

1. 이것도 작동하긴해. Non-tail-recursive라서 그냥 노가다성인거다. 모든 걸 비교해나가는 식

(define (contains? k bt)
  (cond [(false? bt) false]
        [else
         (or (= (node-k bt) k)             ;in root node
             (contains? k (node-l bt))     ;in left node
             (contains? k (node-r bt)))])) ;in right node

 

 

 

2. Accumulator를 사용한 문제 해결

(define (contains? k bt)
  ;; todo: (listof BT); the list of so far univisited right branches
  (local [(define (contains/one? bt todo)
            (cond [(false? bt) (contains/list? todo)]
                  [else
                   (if (= (node-k bt) k)
                       true
                       (contains/one? (node-l bt)
                                      (cons (node-r bt) todo)))]))
          
          (define (contains/list? todo)
            (cond [(empty? todo) false]
                  [else
                   (contains/one? (first todo) (rest todo))]))]
    (contains/one? bt empty)))

todo라는 accumulator를 사용하는거다. 방문해야 하는 tree를 저장하는 todo

 

contains/one? bt todo

일단, false? bt 해서 지금 이진트리가 false면, 아직 확인을 하지 않은 todo 리스트에 있는지 확인하는 걸로 넘어간다

만약에 false가 아니면  bt의 노드 키 값과 k를 비교한다. 만약 같으면 true를 반환하고, 다르면 왼쪽 서브트리를 탐색하고 오른쪽 서브트리를 todo 리스트에 추가하여 재귀적으로 호출합니다.

 

그러면 contains/list? 는 이제 또 확인해봐야할 acc에 대해 키가 있는지 확인하는 거다

contains/list? todo

todo가 비어있으면, 확인할 필요도 없으니 false고

남아있는게 있다면, key랑 일치하는지 확인해야겠지

일단 contains/one? 으로 첫번째 노드부터 확인하고, 나머지는 acc로 넣는다

 

최종적으로 부를 놈은 contains/one? bt (우리가 볼 트리) empty (아직은 뭐 안들어 있는 리스트)

이렇게 되는거다!!!

이해하면 쉬운데 내가 짜면 어렵노

 

 

 

(define (contains? k bt)
  ;; todo: (listof BT); the list of so far univisited subtrees
  (local [(define (contains/one? bt todo)
            (cond [(false? bt) (contains/list? todo)]
                  [else
                   (if (= (node-k bt) k)
                       true
                       #여기 이 부분이 다르다
                       (contains/list? (cons (node-l bt)
                                            (cons (node-r bt)
                                                  todo))))]))
          
          (define (contains/list? todo)
            (cond [(empty? todo) false]
                  [else
                   (contains/one? (first todo) (rest todo))]))]
    
    (contains/one? bt empty)))

 

아예 contains/one?으로 왼쪽노드부터 확인하는게 아니라,

아예 왼쪽 오른쪽 다 cons (왼쪽) cons (오른쪽) todo  이렇게 해서 todo 에 죄다 몰아넣어버린 후, contains/list? 로 한번에 확인해주는 방법도 있다 !!! 

 

---

 

Problem2 : Average

#;
; <template from (listof Number) + 2 accumulators>
(define (average lon)
  ;; cnt: Number; how many numbers so far 
  ;; sum: Number; sum of numbers so far  
  ;;
  ;; (average (list 2 3 4)  0 0)
  ;; (average (list   3 4)  1 2)
  ;; (average (list     4)  2 5)
  ;; (average (list      )  3 9)
  (local [(define (average lon cnt sum)
            (cond [(empty? lon) (/ sum cnt)]
                  [else
                   (average (rest lon) (add1 cnt) (+ (first lon) sum))]))]
    (average lon 0 0)))

 

 

cnt , sum 을 따로 만들어서

lon 안에는 최소 1개 이상 element 가 있다고 가정한다 (0으로 나눌 수는 없으니까)

 

남아있는 lon이 emtpy인 경우 sum/cnt 해주고,

아닌 경우 리스트를 계속 accumulate 해주는거다 : (rest lon) (cnt +=1) (+ sum (first lon)))