Season 1 아카이브/프로그래밍
Functional Programming with Haskell - Recursion
문장전달자
2018. 4. 17. 16:28
728x90
함수 자신을 직접 또는 간접적으로 호출하는 함수를 재귀함수라고 한다.
정수의 팩토리얼(N!) 을 계산하는 것이 전형적인 재귀의 예시이다.
그럼 이를 하스켈로 작성해보자. 그리고 그 타입이 무엇인지 알아보자.
1 2 | factorial n | n == 0 = 1 | otherwise = n * factorial (n-1) | cs |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | *Main> :load factorial [1 of 1] Compiling Main ( factorial.hs, interpreted ) Ok, modules loaded: Main. *Main> :type factorial factorial :: (Eq a, Num a) => a -> a *Main> factorial 40 815915283247897734345611269596115894272000000000 it :: (Eq a, Num a) => a | cs |
재귀 연산을 수동으로 추적하는 방법은 call 에 밑줄을 친 다음, 해당 call 을 textual expansion 을 가지고 다시 작성하는 것이다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | factorial 4 4 * factorial 3 4 * 3 * factorial 2 4 * 3 * 2 * factorial 1 4 * 3 * 2 * 1 * factorial 0 4 * 3 * 2 * 1 * 1 | cs |
나머지가 1이 될 때까지 반복적으로 나누는 연산을 생각해보자.
1 2 3 4 5 6 7 8 9 10 11 12 13 | *Main> 28 `quot` 3 9 it :: Integral a => a *Main> it `quot` 3 3 it :: Integral a => a *Main> it `quot` 3 1 it :: Integral a => a | cs |
나머지가 1이 될 때까지 몇 번 나눠야 하는지를 계산하는 재귀함수 numDivs 를 작성해보자.
1 2 | numDivs divisor x | (x `quot` divisor) < 1 = 0 | otherwise = 1 + numDivs divisor (x `quot` divisor) | cs |
1 2 3 4 5 6 7 8 9 10 11 12 13 | *Main> :load numdiv [1 of 1] Compiling Main ( numdiv.hs, interpreted ) Ok, modules loaded: Main. *Main> numDivs 3 28 3 it :: Num a1 => a1 *Main> numDivs 2 7 2 it :: Num a1 => a1 | cs |
타입은 무엇인가?
1 2 3 4 | *Main> :t numDivs numDivs :: (Integral a, Num a1) => a -> a -> a1 | cs |
그러면 numDivs 2 3.4 은 작동하는가?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | *Main> numDivs 2 3.4 <interactive>:64:1: Could not deduce (Integral a0) arising from a use of ‘numDivs’ from the context (Num a1) bound by the inferred type of it :: Num a1 => a1 at <interactive>:64:1-13 The type variable ‘a0’ is ambiguous Note: there are several potential instances: instance Integral Integer -- Defined in ‘GHC.Real’ instance Integral Int -- Defined in ‘GHC.Real’ instance Integral Word -- Defined in ‘GHC.Real’ In the expression: numDivs 2 3.4 In an equation for ‘it’: it = numDivs 2 3.4 <interactive>:64:9: Could not deduce (Num a0) arising from the literal ‘2’ from the context (Num a1) bound by the inferred type of it :: Num a1 => a1 at <interactive>:64:1-13 The type variable ‘a0’ is ambiguous Note: there are several potential instances: instance Integral a => Num (GHC.Real.Ratio a) -- Defined in ‘GHC.Real’ instance Num Integer -- Defined in ‘GHC.Num’ instance Num Double -- Defined in ‘GHC.Float’ ...plus three others In the first argument of ‘numDivs’, namely ‘2’ In the expression: numDivs 2 3.4 In an equation for ‘it’: it = numDivs 2 3.4 <interactive>:64:11: Could not deduce (Fractional a0) arising from the literal ‘3.4’ from the context (Num a1) bound by the inferred type of it :: Num a1 => a1 at <interactive>:64:1-13 The type variable ‘a0’ is ambiguous Note: there are several potential instances: instance Integral a => Fractional (GHC.Real.Ratio a) -- Defined in ‘GHC.Real’ instance Fractional Double -- Defined in ‘GHC.Float’ instance Fractional Float -- Defined in ‘GHC.Float’ In the second argument of ‘numDivs’, namely ‘3.4’ In the expression: numDivs 2 3.4 In an equation for ‘it’: it = numDivs 2 3.4 *Main> | cs |
아래와 같이 2개의 어플리케이션에 식별자를 붙여보자.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | *Main> let f = numDivs 2 f :: (Integral a, Num a1) => a -> a1 *Main> let g = numDivs 10 g :: (Integral a, Num a1) => a -> a1 *Main> f 9 3 it :: Num a1 => a1 *Main> g 1001 3 it :: Num a1 => a1 | cs |
f 나 g 보다 좀 더 직관적인 이름으로 바꿔보자.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | *Main> let floor_log2 = numDivs 2 floor_log2 :: (Integral a, Num a1) => a -> a1 *Main> floor_log2 1000 9 it :: Num a1 => a1 *Main> let floor_log10 = numDivs 10 floor_log10 :: (Integral a, Num a1) => a -> a1 *Main> floor_log10 1000 3 it :: Num a1 => a1 | cs |
728x90