강의20 - kyagrd/introCS2018spring GitHub Wiki

이항관계와 closure 등에 대한 정리

기말고사 Haskell 문제들에 관한 힌트

시험시간이 1시간으로 짧으므로 약간 더 힌트를 주는 것이 좋을 것 같아 2분반은 수업때 좀더 자세히 했는데 3분반에서는 그럴 기회가 없어서 2분반 마지막 수업때 했던 내용을 여기에 정리합니다.

일단 plus :: Nat -> Nat -> Nat 함수를 수업시간에 살펴봤고 과제에서도 활용했었죠. 그걸 다시 떠올려 봅시다.

-- 일진수 자연수 데이타타입 정의
data Nat = Z | S Nat  deriving Show

plus Z     m = m
plus (S n) m = S (plus n m)

시험에 나는 함수들 plus의 구조와 비슷한 함수인데 예를 들면 아래와 같이 변형했다고 쳐봅시다.

plls Z     m = plus m m      -- m을 그냥 돌려주는 대신 plus m m 을 호출
plls (S n) m = S(plls n m)  -- plus의 귀납적 경우와 같은 구조를 유지

시험에는 다음과 같은 식의 값을 구하라는 유형의 문제를 냈습니다.

plls (S(S Z)) Z
plls (S(S Z)) (S Z)

그럼 한번 구해 봅시다.

일단 첫번째 식의 경우처럼 둘째 항이 Z인 경우는 사실 plus와 값이 똑같이 S(S Z)로 결과가 계산됩니다. 왜냐하면 어차피 맨 마지막에 계산되는 plus Z Z의 값이 어치피 Z가 되니까요.

plls (S(S Z)) Z = S(plls (S Z) Z)
                = S(S(plls Z Z))
                = S(S(plus Z Z))
                = S(S Z)

두번째로 둘째 항이 Z가 아닌 경우는 plus와 좀 다른 값이 나오겠죠. 한번 계산해 봅시다.

plls (S(S Z)) (S Z) = S(plls (S Z) (S Z))
                    = S(S(plls Z (S Z)))
                    = S(S(plus (S Z) (S Z)))
                    = S(S(S(S Z)))

맨 마지막에 그냥 Z를 돌려주는 plus의 경우와 달리 plls는 맨 마지막 귀납기초에 해당하는 경우를 처리하기 위해 그냥 m을 돌려주는 대신 plus m m 즉 우리가 다루는 식의 경우에는 plus (S Z) (S Z)을 마지막에 계산하게 되는거죠.

그러니까 좀더 일반적으로 차이점을 정리해 보자면 plus n m은 보통 우리가 자주 사용하는 수식 형태로 표현하자면 n+m을 하는 함수이고 plls n m은 맨 마지막에 그냥 m을 돌려주는 plus와 달리 아니라 m을 한번 더 더해주니까 n+(m+m) 즉 n+2m을 계산하는 함수가 되는거죠. 이렇게 함수를 보고 일반화된 식까지 분석할 수 있으면 계산을 일일히 풀어쓰지 않아도 금방 답을 예상할 수 있겠죠.

실제 기말고사에서는 plls보다 살짝 더 복잡한, 그러니까 귀납단계에 해당하는 두번째 등식도 plus의 귀납단계와는 조금 다르게 바꾼 함수가 두 개 주어지고 함수마다 각각 두 문제씩 식의 값을 계산하는 문제가 나올겁니다.