Functional Programming - The Countdown Problem
이번 포스팅은 Haskell의 새로운 컨셉을 설명하는 것이 아닌 Haskell을 이용하여 어떻게 개발하는지 알아보겠습니다. 보통 개발 초기에는 동작하지만 다소 복잡하고 비효율적으로 코드를 작성하게 됩니다. 이후 refactoring을 하며 효율적인 방향으로 수정합니다. 하지만 초기 목표는 효율성과 관계없이 가장 간단한 프로그램을 만드는 것입니다. 하지만, 지금 지금까지 배운 코드는 Haskell Compiler에서 동작하는 코드로 실제 상황에 적용하기 어려울 수 있습니다. 그러나 이 강의에서 목표는 다음처럼 functional programming 개념을 익히고 적용하는 것입니다.
Think like a fundamentalist but code like a Hacker
What Is CountDown?
그럼 Countdown 문제는 뭘까요?
예를 들어, 아래와 같은 숫자와 연산자(operator)를 받을 경우 조합을 통해 원하는 숫자를 만들면 됩니다.
numbers: 1 3 7 10 25 50
operators: + - * /
result: 765
위에 대해 사람이 하기에는 다소 어려움을 가지고 있습니다. 따라서 프로그램을 통해 해결해야하는데 제약사항이 들어갈 수록 속도는 빨라집니다.
Rules * 모든 숫자는 양의 자연수(positive naturals) 이여야 합니다. * 주어진 number는 최대 한번씩만 사용될 수 있습니다.
위의 조건 및 제약사항으로 답을 구하면 다음과 같습니다.
(25-10)*(50+1) = 765
- 780에 대해서도 구할 수 있습니다.
- 831에 대해서는 결과를 얻을 수 없습니다.
Evaluating Expressions
이제는 우리가 사용할 사항들을 만들어봅시다. 먼저 operation을 정의한 data type 입니다.
data Op = Add | Sub | Mul | Div
위에서 생성한 type을 이용한 evaluation function 은 아래와 같이 정의할 수 있습니다.
apply || Op -> Int -> Int -> Int
apply Add x y = x + y
apply Sub x y = x - y
apply Mul x y = x * y
apply Div x y = x / y
또한, Rule에 따라 모든 number 및 계산 중 발생하는 number는 모두 양수여야 합니다. 이를 검증하기 위한 함수는 다음처럼 구현할 수 있습니다.
valid :: Op -> Int -> Int -> Bool
valid Add _ _ = True
valid Sub x y = x > y
valid Mul _ _ = True
valid Div x y = x \`mod\` y == 0
마지막으로 전체 expression에 대한 data type은 아래와 같으며,
data Expr = Val Int | App Op Expr Expr
이를 이용한 evaluation 함수는 다음과 같습니다.
eval :: Expr -> [Int]
eval (Val n) = [n | n > 0]
eval (App o l r) = [apply o x y | x <- eval l
, y <- eval r
, valid o x y]
따라서 실패할 경우 비어있는 list를 돌려주고 성공할 경우 singleton list를 돌려줍니다.
예를 들어, 아래와 같은 숫자와 연산자(operator)를 받을 경우 조합을 통해 원하는 숫자를 만들면 됩니다.
numbers: 1 3 7 10 25 50
operators: + - * /
result: 765
위에 대해 사람이 하기에는 다소 어려움을 가지고 있습니다. 따라서 프로그램을 통해 해결해야하는데 제약사항이 들어갈 수록 속도는 빨라집니다.
Rules * 모든 숫자는 양의 자연수(positive naturals) 이여야 합니다. * 주어진 number는 최대 한번씩만 사용될 수 있습니다.
위의 조건 및 제약사항으로 답을 구하면 다음과 같습니다.
(25-10)*(50+1) = 765
- 780에 대해서도 구할 수 있습니다.
- 831에 대해서는 결과를 얻을 수 없습니다.
Evaluating Expressions
이제는 우리가 사용할 사항들을 만들어봅시다. 먼저 operation을 정의한 data type 입니다.
data Op = Add | Sub | Mul | Div
위에서 생성한 type을 이용한 evaluation function 은 아래와 같이 정의할 수 있습니다.
apply || Op -> Int -> Int -> Int
apply Add x y = x + y
apply Sub x y = x - y
apply Mul x y = x * y
apply Div x y = x / y
또한, Rule에 따라 모든 number 및 계산 중 발생하는 number는 모두 양수여야 합니다. 이를 검증하기 위한 함수는 다음처럼 구현할 수 있습니다.
valid :: Op -> Int -> Int -> Bool
valid Add _ _ = True
valid Sub x y = x > y
valid Mul _ _ = True
valid Div x y = x \`mod\` y == 0
마지막으로 전체 expression에 대한 data type은 아래와 같으며,
data Expr = Val Int | App Op Expr Expr
이를 이용한 evaluation 함수는 다음과 같습니다.
eval :: Expr -> [Int]
eval (Val n) = [n | n > 0]
eval (App o l r) = [apply o x y | x <- eval l
, y <- eval r
, valid o x y]
따라서 실패할 경우 비어있는 list를 돌려주고 성공할 경우 singleton list를 돌려줍니다. 여기서는 이전과 다르게 Maybe type을 사용하지 않은 것을 확인 할 수 있습니다. (여기서는 이편이 더 좋다고 합니다.)
Formalising the Problem
이미 있는 함수일지 모르지만 우리는 연습을 위해 정의해보겠습니다. 지금 구현할 함수는 0개 또는 그 이상의 element들의 가능한 조합을 모두 구하는 list입니다.
choices :: [a] -> [[a]]
> choices [1,2]
[[],[1],[2],[1,2],[2,1]]
다음은 expression안에 있는 모든 values를 포함한 list를 구하는 함수를 구현한 것입니다.
values :: Expr -> [Int]
values (Val n) = [n]
values (App _ l r) = values 1 ++ values r
위에 구현한 사항들 모두를 이용하여 주어진 expression으로 결과를 구할 수 있는지 확인하는 함수입니다.
solution :: Expr -> [Int] -> Int -> Bool
solution e ns n = elem (values e) (choices ns)
&& eval e == [n]
Brute Force Solution
다음으로 Brute-force 방법을 보겠습니다. 먼저 list를 두개의 non-empty list로 나누는 모든 경우를 돌려주는 함수를 보겠습니다.
split :: [a] -> [([a],[a])]
> split [1,2,3,4]
[([1],[2,3,4],([1,2],[3,4]),([1,2,3],[4])]
다음 함수는 주어진 number list로 표현 가능한 expression list를 돌려줍니다.
exprs :: [Int] -> [Expr]
exprs [] = []
exprs [n] = [Val n]
exprs ns = [e | (ls, rs) <- split ns
, l <- exprs ls
, r <- exprs rs
, e <- combine l r]
또한, 위에서 사용된 combine 함수는 다음과 같이 작성할 수 있습니다.
combine :: Expr -> Expr -> [Expr]
combine l r =
[App o l r | o <- [Add,Sub,Mul,Div]]
마지막으로 위 사항들을 모두 이용하여 countdown problem을 해결할 수 있는 모든 expression을 돌려주는 함수를 만들 수 있습니다.
solutions :: [Int] -> Int -> [Expr]
solutions ns n = [e | ns' <- choices ns
, e <- exprs ns'
, eval e == [n]]
위 방법은 매우 brute-force 한 방법이지만, 괜찮은 속도를 보여줍니다. 모든 경우의 세는 것임에도 말이죠. 아래와 같은 것을 고려하면 더 빠른 성능을 볼 수 있습니다.
- 많은 expression들이 invalid 합니다.
- 앞선 예의 경우 3300만의 가능한 expression에 대해 오직 500만개의 expression만 valid합니다.
- 따라서 invalid expression에 대한 판단을 하도록 evalution을 적용한 combine을 만들었다면 더 빠른 성능이 가능했을 겁니다.
그럼 위와 같은 사항들을 고려하여 invalid expression을 생성하는 경우를 피하도록 해보겠습니다.
Fusing Two Functions
일단, valid expression과 그 expression의 결과를 모은 type과 계산하는 함수를 만듭니다.
type Result = (Expr,Int)
results :: [Int] -> [Result]
results ns = [(e,n) | e <- expr ns
, n <- eval e]
위의 동작들을 아래와 같이 구현이 가능합니다.
results [] = []
results [n] = [(Val n,n) | n > 0]
results ns =
[res | (ls,rs) <- split ns
, lx <- results ls
, ry <- results rs
, res <- combine' lx ry]
combine' :: Result -> Result -> [Result]
combine' 함수는 위의 combine과 동일하지만, valid check가 들어간 점이 다릅니다.
combine' (l,x) (r,y) =
[(App o l r, apply o x y)
| o <- [Add,Sub,Mul,Div]
, valid o x y]
이 모두를 적용하여 solutions 함수를 변경해주면 됩니다.
solutions'
solutions' ns n =
[e | ns' <- choices ns
, (e,m) <- results ns'
, m == n]
이렇게 구현할 경우 처음경우보다 훨씬 빠른 결과를 볼 수 있습니다. 그렇다면 더 향상 시킬 수는 없는 걸까요? 이전에는 invalid expression을 제거하는 것이 목적이였다면, 이제는 아래와 같은 사항들을 고려해보겠습니다.
- 많은 expression들이 수학적으로 볼때 기본적으로 같습니다. 예를 들어,
x * y는y * x와 동일하고,x * 1은x와 같습니다. - 위 사항을 고려하면 충분히 탐색과 solution 공간을 줄일 수 있습니다.
Exploiting Properties
그럼 위에서 이야기한 교환가능과 동일성을 고려하여 valid 함수를 작성해보겠습니다.
valid :: Op -> Int -> Int -> Bool
valid Add x y = x <= y -- True
valid Sub x y = x > y
valid Mul x y = x <= y && x != 1 -- True
valid Div x y = x \`mod\`y == 0
위와 같이 Add 와 Mul 에 대해 제약을 가해 일정한 패턴만 적용받게 하여 동일한 결과를 돌려주는 expression 중복을 제거하였습니다.