하스켈로 배우는 함수형 언어 3

하스켈에서 repetition (반복) 은 recursion 을 통해 표현됩니다. 간단한 재귀부터 시작해서 mutual recursion 까지 알아보고, Higher order function (특히 fold) 에 대해 배운 뒤 적용을 위해 church numerals 를 구현해보고, 마지막으로 간단한 문자열 전송기를 모델링 해 보겠습니다.

Tail call?

recursion 을 주로 사용한다면 stack 이 많이 쌓일 수 있습니다. 이런 문제를 해결해 주는 것이 tail call elimination 입니다.

간단한 재귀 함수를 만들어서 스택이 어떻게 변하나 한번 보죠.

factorial 0 = 1
factorial n = n * factorial(n - 1)

이 때 factorial 3 을 평가한다면

factorial 3
3 * factorial 2
3 * (2 * factorial 1)
3 * (2 * (1 * factorial 0))
3 * (2 * (1 * 1))
3 * (2 * 1)
3 * 2
6

이렇게 각 단계가 확장되면서 n 이 매우 클 경우 마지막 단계에서 연산의 길이가 엄청나게 길어집니다. 함수 한번 호출당 스택이 하나씩 생긴다고 보면 어마어마한 스택이 생기는 것이죠.

다행히도 하스켈은 tail recursion optimization (꼬리 재귀 최적화) 를 가지고 있습니다. 꼬리 재귀에 대한 이야기는 나중에 더 이야기 하도록 하지요.

Recursion on Lists

리스트는 같은 타입을 여러개 저장할 수 있기 때문에 recursion 을 사용하기 적합하죠.

리스트 내의 모든 원소의 곱을 구하는 product 함수를 만들어 볼까요? 하스켈에 원래 있지만, 재미삼아 만들어 봅시다. 이름은 충돌이 안나게 productC 라 부릅시다.

productC :: [Int] -> Int
productC [] = 1
productC (n : ns) = n * productC ns

length 와 reverse 도 만들어 봅시다.

lengthC :: [a] -> Int
lengthC [] = 0
lengthC (x : xs) = 1 + length xs

reverseC :: [a] -> [a]
reverseC [] = []
reverseC (x : xs) = reverse(xs) ++ [x]

조금 더 복잡한 zip, drop 함수나 ++ 연산자도 어렵지 않습니다.

zipC :: [a] -> [b] -> [(a, b)]
zipC [] _ = []
zipC _ [] = []
zipC (x:xs) (y:ys) = (x, y) : zip xs ys

dropC :: Int -> [a] -> [a]
dropC 0 xs = xs
dropC _ [] = []
dropC n (x:xs) = drop (n-1) xs

(++) :: [a] -> [a] -> [a]
[] ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)

Quick sort

퀵소트 알고리즘은 간단합니다. 매 함수 호출에서, pivot 이라 불리는 리스트 내 원소를 고른 후 pivot 좌측에는 그 보다 작은 수를, 우측에는 pivot 보다 큰 수를 배치합니다. 그리고 pivot 을 제외한 좌측 과 우측에 대해 재귀 호출을 하지요.

(https://sadakurapati.wordpress.com)

지난 강의에서 배운 list comprehension 을 이용하면 매우 간단하게 quick sort 를 만들 수 있습니다.

qsort :: [Int] -> [Int]
qsort [] = []
qsort (x:xs) = qsort smaller ++ [x] ++ qsort larger
               where
                 smaller = [a | a <- xs, a <= x]
                 larger = [b | b <- xs, b > x]

위 코드에서는 매 재귀마다 인자로 받는 리스트의 첫번째 원소 x 를 pivot 으로 사용했습니다.

Recursion

위의 예에서 보았듯이 자기 자신을 호출하는 함수 패턴을 recursion (재귀) 라 부릅니다. 언제 유용할까요? 재귀를 이용하면 induction (귀납법) 을 이용해 함수의 성질을 증명할 수 있습니다. 제대로 동작하는지, 의도 했던대로 동작하는지 등을요.

Properties of functions defined using recursion can be proved using the simple but powerful mathematical technique of induction

Mutial recursion

mutual recursion 은 서로 다른 두개의 함수가 상호간 재귀를 이용해 정의되는 방식입니다.

odd 와 even 함수를 mutual recursion 을 이용해 정의할 수 있습니다. 일반적으로는 효율성을 위해 2로 나눈 나머지를 이용해 정의하지만, 양수에 대해서는 아래와 같이 mutual recursion 으로 만들 수 있죠.

even :: Int -> Bool
even 0 = True
even n = oddC (n-1)

odd :: Int -> Bool
odd 0 = False
odd n = evenC (n-1)

비슷하게 리스트에서 짝수번째, 혹은 홀수번째 원소들만 돌려주는 evens 와 odds 함수도 mutual recursion 을 이용해 정의할 수 있습니다. evens 는 0번째 부터 돌려줍니다. odds 는 턴을 넘기는데 쓰고 실제 작업은 evens 에서 한다고 생각하면 금방 이해할 수 있습니다.

evens :: [a] -> [a]
evens [] = []
evens (x:xs) = x : odds xs

odds :: [a] -> [a]
odds [] = []
odds (_:xs) = evens xs

Advice on recursion

재귀는 자전거 타기와 비슷합니다. 처음엔 불가능해 보이는데 한번 시도해보면 정말 쉽게 탈 수 있죠. 여기 재귀를 만드는데 도움이 될만한 5가지 스텝이 있습니다. init 함수를 예로 들어 설명하겠습니다.

(1) define the type

init :: [a] -> [a]

(2) enumerate the cases

init (x:xs) =

(3) define the simple case

init (x:xs) | null xs = []
            | otherwise =

(4) define the other cases

init (x:xs) | null xs = []
            | otherwise = x : init xs

(5) generalise and simplify

init :: [a] -> [a]
init [_] = []
init (x:xs) = x : init xs

Examples

예제 몇 가지를 좀 더 살펴봅시다. 먼저 곱셈 연산입니다.

(*) :: Int -> Int -> Int
m * 0 = 0
m * n = m + (m * (n - 1))

정렬된 리스트에 원소를 삽입하는 insert 함수입니다. 바로 다음에 만들 isort (insertion sort) 를 구현한 함수에서 사용합니다.

insert :: Ord a => a -> [a] -> [a]
insert x [] = [x]
insert x (y:ys) | x <= y = x : y : ys
                | otherwise = y : insert x ys

isort :: Ord a => [a] -> [a]
isort [] = []
isort (x:xs) = insert x (isort xs)

이번엔 merge sort 입니다.

merge :: Ord a => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys) =
  if x <= y then x : merge xs (y: ys) else y : merge (x:xs) ys

halve :: [a] -> ([a], [a])
halve xs = splitAt (length xs `div` 2) xs

msort :: Ord a => [a] -> [a]
msort [] = []
msort [x] = [x]
msort xs = merge (msort ys) (msort zs)
           where (ys, zs) = halve xs

Higher-order function

higher-order function 은 함수를 인자로 받아 다시 함수를 돌려주는 함수를 말합니다. 응?

A function is called higher-order if it takes a function as an argument or returns a function as a result

twice :: (a -> a) -> a -> a
twice f x = f (f x)

twice 는 인자 x 에 f 를 두번 적용한 뒤 값을 돌려줍니다. 더 정확히는 curried function 이므로 twice f 는 앞으로 뭘 인자로 받을지 모르지만 f 를 두번 적용하는 함수를 돌려줍니다.

이런 higher-order function (고차함수) 가 언제 유용할까요?

  1. Common programming idioms can be encoded as functions within the language itself.

  2. Domain specific languages can be defined as collections of higher-order functions.

  3. Algebraic properties of higher-order functions can be used to reason about programs.

map

먼저 map 함수를 살펴봅시다.

map :: (a -> b) -> [a] -> [b]

map (+1) [1, 3, 5, 7]
-- [2, 4, 6, 8]

이 map 함수는 우리가 이전에 배웠던 list comprehension 으로 똑같이 작성할 수 있습니다.

map f xs = [f x | x <- xs]

아니면 recursive function 으로 작성할 수도 있습니다.

map f [] = []
map f (x:xs) = f x : map f xs

filter

filter 도 고차함수입니다. filter 는 predicate 즉, (a -> Bool) 을 받아 True 인 원소만 모아 돌려줍니다.

filter :: (a -> Bool) -> [a] -> [a]

filter even [1..10]
-- [2, 4, 6, 8, 10]

filter 도 마찬가지로 list comprehension 과 recursive function 두 가지 버전으로 작성될 수 있습니다.

filter p xs = [x | x <- xs, p x]

filter p [] = []
filter p (x:xs)
  | p x = x : filter p xs
  | otherwise = filter p xs

단순히 list comprehension 으로 작성하는 것 보다, recursive function 으로 작성하면 위에서 볼 수 있듯이 공통점을 파악할 수 있습니다. 그러면 한단계 더 추상화 할 수 있지요. filter 와 map 의 공통점이 보이시나요?

foldr

위의 두 가지 예에서 filter, map 모두 빈 리스트와 그렇지 않은 리스트를 구분했습니다. 그리고 각각의 원소에 대해서 연산을 수행했지요.

f [] = v
f (x:xs) = x pred f xs

빈 원소라면 특정 값 v 를 돌려주고 아니라면 원소 x 에 pred를 적용하고, 나머지 tail xs 에 f 를 적용합니다. 비슷한 예제를 살펴볼까요?

-- v = 0, pred = +
sum [] = 0
sum (x:xs) = x + sum xs

-- v = 1, pred = *
product [] = 1
product (x:xs) = x * product xs

-- v = True, pred = &&
and [] = True
and (x:xs) = x && and xs

따라서 다음과 같이 foldr (fold right) 을 이용해 정의할 수 있습니다.

sum = foldr (+) 0

product = foldr (*) 1

or = foldr (||) False

and = foldr (&&) True

위에서 대략적인 정의를 봤지만, 더 엄밀하게 foldr 은 이렇게 정의할 수 있습니다.

foldr :: (a -> b-> b) -> b -> [a] -> b
foldr f v [] = []
foldr f v (x:xs) = f x (foldr f v xs)

보면 알겠지만, 리스트의 the right-most (가장 우측) 부터 연산합니다. 그래서 fold right 라는 이름이 붙었지요. 그림으로 보자면

(http://www.pling.org.uk/cs/fun.html)

sum [1, 2, 3]
foldr (+) 0 [1, 2, 3]
foldr (+) 0 (1:(2:(3:[])))
1 + (2 + (3 + 0))

콘싱 : 하고 비슷합니다. 이 부분에 연산자를 집어넣고, [] 에 초기값 v 를 넣는다고 생각하면 이해하기 쉽습니다.

length 도 비슷한 패턴을 가지고 있기 때문에 foldr 로 바꿀 수 있습니다.

length :: [a] -> Int
length [] = 0
length (x:xs) = 1 + length xs

length = foldr (\_ n -> 1 + n) 0

이렇게 바꿀 수 있는 이유는

length [1, 2, 3]
length (1: (2: (3:[])))
1 + (1 + (1 + 0)))

여기서 각 : 을 \_ n -> 1 + n 으로 바꾸면 되기 때문입니다.

reverse [] = []
reverse (x:xs) reverse xs ++ [x]

이제 위 reverse 함수도 foldr 을 이용할 수 있습니다.

reverse = foldr (\x xs -> xs ++ [x]) []

처음의 filter, map 도 이렇게 정의할 수 있습니다.

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f v [] = v
foldr f v (x:xs) = f x (foldr f v xs)

filter :: (a -> Bool) -> [a] -> [a]
filter p xs = foldr (\x acc -> if p x then x : acc else acc) [] xs

map :: (a -> b) -> [a] -> [b]
map p xs = foldr (\x acc -> p x : acc) [] xs

foldr 을 이용하면 몇 가지 장점이 있습니다.

  1. Some recursive functions on lists, such as sum, are simpler to define using foldr.

  2. Properties of functions defined using foldr can ben proved using algebraic properties of foldr, such as fusion and the banana split rule.

  3. Advanced program optimizations can be simpler if foldr is used in place of explicit recursion.

여기서 fusion 은, 하나의 foldr 은 리스트를 순회하면서 새로운 리스트를 리턴하고, 다른 foldr 을 그 결과에 사용할 때 intermediate list 를 생성하는 것 없이 계산을 해 낸다는 뜻입니다.

In particular fusion means that I have two functions. One that uses foldr to traverse one list and return another list. And if I do another foldr on the result of that I can fuse these two together, such that the intermediate list is never constructed. So program can be optimized.

다른 고차함수들을 좀 살펴봅시다.

composition

(.) 은 함수를 composition (합성) 해 줍니다.

(.) :: (b -> c) -> (a -> b) -> (a -> c)
f . g = \x -> f(g x)

예를 들어

odd :: Int -> Bool
odd = not . even

compoisition 을 사용할때는 괄호와 나머지 인자를 제거하여 함수의 정의를 간단히 할 수 있습니다.

twice f x = f (f x)

-- same as
twice f = f f

all, any

모든 원소에 대해 p 를 적용한 결과가 참인지를 돌려주는 all 은 다음처럼 정의할 수 있습니다.

all :: (a -> Bool) -> [a] -> Bool
all p xs = and [p x | x <- xs]

이번엔 list comprehension 을 사용했습니다. foldr 과의 차이는, foldr 은 모든 순회 가능한 데이터 타입에 적용 가능한 반면 list comprehension 은 리스트에만 사용할 수 있습니다. 위 예제를 foldr 로 바꾸면

all :: (a -> Bool) -> [a] -> Bool
all p xs = foldr (\x acc -> p x && acc) True xs

any 도 만들 수 있습니다.

import Data.Char

any :: (a -> Bool) -> [a] -> Bool
any p xs = or [p x | x <- xs]

-- same as
any p xs = or (map p xs)

takeWhile, dropWhile

takeWhile 은 predicate 가 참인 원소까지만 돌려줍니다. 예를 들어

takeWhile :: (a -> Bool) -> [a] -> [a]
takeWhile p [] = []
takeWhile p (x:xs) | p x = x : takeWhile p xs
                    | otherwise = [] 

takeWhile isAlpha "abc def"
-- "abc"

반면 dropWhile 은 predicate 를 적용한 결과가 참인 원소를 모두 버리고 나머지만 돌려줍니다. 예를 들어

dropWhile :: (a -> Bool) -> [a] -> [a]
dropWhile p [] = []
dropWhile p (x:xs) | p x = dropWhile p xs
                    | otherwise = x:xs
                    
dropWhile isAlpha "fp 101"
-- " 101"

Church Numerals

Church Numerals give us a way to abstract over the concrete representation of a number by means of functions and unction application.

숫자 n 은 zero 에 n 번의 s function application 을 통해 정의합니다.

zero = \s z -> z
one = \s z -> s z
two = \s z -> s (s z)

-- same as
two = \s z -> (s . s) z

-- we can remove z
two = \s -> s . s

여기서 데이터 z 자체는 아무것도 정해진 것이 없습니다. 다시 말해 어떤 타입이든 가져다 쓸 수 있다는 뜻이지요.

우리가 숫자 3을 표현하기 위해 1을 세번 더해 3 을 표시하든, 아니면 * 를 세번 컨싱하든 상관 없다는 뜻 입니다.

zero = \s z -> z
one = \s z -> s z
two = \s -> s . s

-- church to int
c2i x = x (+1) 0

c2i zero
-- 0

c2i one
-- 1

c2i two
-- 2

* (에스터리스크) 의 개수로 숫자를 정의해 봅시다.

-- church to int
c2s x = x ('*' :) ""

c2s zero
-- ""

c2s one
-- "*"

c2s two
-- "**"

이제 연산자를 만들어 봅시다. 덧셈부터 시작해 보죠! c2i 에 x 를 넣어 만들어낸 수 (Number) 를 x' 라 하고 y 를 넣어 만든 수를 y' 라 합시다.

x' = c2i x
y' = c2i y

그러면 덧셈은 이렇게 정의할 수 있습니다.

x' + y' = c2i (add x y)

증명해 봅시다.

x' + y' 
= c2i x + c2i y
= x (+1) 0 + c2i y -- 0 is substituted
= x (+1) (c2i y)
= x (+1) (y (+1) 0)
= (\s z -> x s (y s z)) (+1) 0 -- by beta expension

보면 알겠지만 c2i y 나 0 + c2i y 나 같습니다. 따라서 0을 지우고 x c2i 의 베이스 값으로 (c2i y) 를 사용할 수 있죠.

그리고 마지막 치환은 s 와 z 를 (+1) 과 0 으로 취하는 lambda 를 구할 수 있습니다. \s z -> x s (y s z) 를 add 라 부르면

x' + y' = (add x y) (+1) 0
= c2i (add x y)

결국 addtion 은

add x y = \s z -> x s (y s z)

c2i (add one two)
-- 3

*multiplication (곱셈)*은 어떻게 만들까요? 간단한 예제부터 시작해 intuition 을 얻어보도록 합시다.

two = \s -> s . s
three = \s -> s . s . s

결국 n 번째 수란건 s successor function 을 n 번 만큼 수행한거지요. 그럼 a * b 의 곱셈은 b 번 적용한 successor 를 a 번 적용하면 되므로

mul = \s z -> x (y s) z

c2i (mul two five)
-- 10

Examples

id :: a -> a
id = \x -> x

compose :: [a -> a] -> (a -> a)
compose = foldr (.) id

id 함수는 받은걸 그대로 돌려주기 때문에 id . f, f . id 는 f 입니다. 따라서 함수 리스트를 위한 foldr 의 초기값으로 id 를 사용할 수 있습니다.

String Transmitter

간단한 문자열 전송을 모델링한 코드를 작성해 봅시다.

import Data.Char

type Bit = Int

bin2int :: [Bit] -> Int
bin2int bits = sum [w * b | (w, b) <- zip weights bits]
  where weights = iterate (*2) 1

-- or
-- bin2int bitis = foldr (\x acc -> x + acc * 2) 0

int2bin :: Int -> [Bit]
int2bin 0 = []
int2bin n = n `mod` 2 : int2bin(n `div` 2)

make8 :: [Bit] -> [Bit]
make8 bits = take 8 (bits ++ repeat 0)

encode :: String -> [Bit]
encode = concat . map (make8 . int2bin . ord)

chop8 :: [Bit] -> [[Bit]]
chop8 [] = []
chop8 bits = take 8 bits : chop8 (drop 8 bits)

decode :: [Bit] -> String
decode = map (chr . bin2int) . chop8

channel :: [Bit] -> [Bit]
channel = id

transmit :: String -> String
transmit = decode . channel . encode

재밌는 부분은 마지막 channel 부분인데요, id 함수를 써서 인코딩된 문자열이 바로 디코딩을 위해 전송된다는 것을 표현했습니다.

위 코드 중에서 int2bin 과 chop8 은 헤드에 특정 연산을 수행하고, tail 에 나머지 연산을 수행 한 결과를 다시 재귀적으로 호출하는 패턴을 가지고 있는데요, unfold 함수로 추상화 할 수 있습니다.

쉽게 말해서 fold 가 리스트를 접어 (folding) 원소 하나로 만든다면, unfold 는 리스트를 더 한단계 펼친다고 볼 수 있습니다.

unfold p h t x 
  | p x = []
  | otherwise = h x : unfold p h t (t x)

그리하면 구현을

type Bit = Int
int2bin :: Int -> [Bit]
int2bin = unfold (== 0) (`mod` 2) (`div` 2)

chop8 :: [Bit] -> [[Bit]]
chop8 = unfold null (take 8) (drop 8)

map 과 iterate 도 구현할 수 있습니다.

map2 f = unfold null (f . head) tail

iterate' f = unfold (const False) id f -- const False is pred. always return False

여기서 const False 는 항상 False 만 돌려주는 predicate 라 보시면 됩니다.

References

(1) DelftX FP 101x in edx
(2) https://sadakurapati.wordpress.com
(3) Programming in Haskell, Chapter 6, 7
(4) http://www.pling.org.uk/cs/fun.html



comments powered by Disqus