Functional Programming - Declaring Types and Classes
우리는 이전 Parser를 배울때 type을 정의했었습니다. 이와 마찬가지로 함수를 정의하듯 type을 정의할 수 있습니다. 앞으로 우리는 어떻게 새로운 type을 만들고 type class를 정의하는지 보는 동시에 기존 OOP(Object Oriented Programming)과의 비교해보겠습니다. 문법적으로는 다를 수 있지만, 공통된 사항들을 논의할 수 있을 것입니다.
Type Declarations
Haskell에서는 기존에 있는 type에 대한 새로운 이름을 정의할 수 있습니다.
type String = [Char]
지금까지 자주 사용해왔던 String은 [Char] 로 Char List 입니다. 따라서 위와같이 표현한 것을 볼 수 있습니다.
또한, 편리하게 표현하기 위해 사용하기도 하는데 다음 예가 그러합니다.
type Pos = (Int,Int)
편리하게 위치(position)을 표현하기 위해 위와 같은 묶어서 정의하였습니다.
origin :: Pos
origin = (0,0)
left :: Pos -> Pos
left (x,y) = (x-1,y)
또한, 마치 함수처럼 인자(parameter)를 받도록 정의할 수 있습니다.
type Pair a = (a,a)
a 를 받아 쌍(pair)를 만들도록 하는 것입니다.
mult :: Pair Int -> Int
mult (m,n) = m*n
copy :: a -> Pair a
copy x = (x,x)
mult 의 경우 Pair Int 를 받아 곱셈을 만들어주고, copy 의 경우 Pair 과 비슷하지만 타입을 정하지 않고 쌍으로 만드는 것을 볼 수 있습니다.
Type declaration 은 다중(nested)으로 적용할 수 있습니다.
type Pos = (Int, Int)
type Trans = Pos -> Pos
하지만, 재귀(recursive)를 적용할 수 없습니다.
type Tree = (Int, [Tree]) -- Error
그러나 나중에 보겠지만, 재귀를 적용할 수 있는 방법이 있습니다. nominal type을 이용해야 가능합니다.
Data Declarations
우리가 recursive type을 만들고 싶을 때, nominal type을 이용해야한다고 하였습니다. 앞으로 우리가 data declaration을 이용하여 nominal type을 만드는 방법을 알아보겠습니다. 먼저 data declaration에 대한 설명입니다.
data Bool = False | True
위의 type 과는 달리 새로운 type을 정의합니다. (type 은 기존에 있는 type을 이용하여 표현하는 방법이었습니다.)
이런 방법은 Scala에서 case class를 이용하여 표현하는 방식과 유사한데, Java나 C#에서도 비슷하게 사용됩니다. Bool이 abstract base class로 위 예에 오른편이 subtype이 되어 False extends Bool과 True extends Bool로 구현이 가능합니다. 또한 Bool은 abstract로 instance 생성이 불가하여 False, True로 표현해야하지만, 둘다 Bool type이라는 것을 지금과 동일합니다. 다시 돌아가서..
- False와 True는 type Bool의 constructors라고 불립니다.
- type과 constructor는 반드시 대문자로 시작해야합니다.
- Data declaration은 context free grammar와 유사합니다. 전자는 type의 value를 정의하지만, 후자는 언어의 sentence를 정의합니다.
새로운 type의 값들은 동일한 방법으로 다양하게 이용될 수 있습니다.
data Answer = Yes | No | Unknown
answers :: [Answer]
answers = [Yes,No,Unknown]
flip :: Answer -> Answer
flip Yes = No
flip No = Yes
flip Unknown = Unknown
data declaration의 constructor는 인자를 가질 수 있습니다. 예를 들어,
data Shape = Circle Float
| Rect Float Float
위와 같이 정의하여 다음과 같이 사용할 수 있습니다.
square :: Float -> Shape
square n = Rect n n
area :: Shape -> Float
area (Circle r) = pi * r^2
area (Rect x y) = x * y
- 위
Shape는r은 float인Circle r과x,y모두 float은Rect x y를 가집니다. Circle과Rect는 마치 함수처럼 동작합니다.
Circle :: Float -> Shape
Rect :: Float -> Float -> Shape
놀랍지도 않게 data declaration 또한 인자를 가질 수 있습니다.
data Maybe a = Nothing | Just a
위 Maybe 는 비어있거나 단지(Just) a 라는 표현으로 아래와 같이 list에 대해 안전한(safe) 함수를 구현하게 해줍니다.
safediv :: Int -> Int -> Maybe Int
safediv _ 0 = Nothing
safediv m n = Just (m \`div\` n)
safehead :: [a] -> Maybe a
safehead [] = Nothing
safehead xs = Just (head xs)
하지만, Maybe 가 항상 붙어 우리는 이것을 처리해줘야할 필요가 생깁니다.
Recursive Types
앞서 Recursive Type을 생성하지 못한다고 하였지만, nominal type의 경우 가능하다고 했습니다. 앞으로 몇가지 recursive type에 대해 알아보겠습니다.
처음으로 볼 것은 natural number입니다.
data Nat = Zero | Succ Nat
위 Nat 는 Zero 이거나 Succ :: Nat -> Nat 에 의해 다른 자신(숫자)를 가질 수 있습니다. 이것을 함수로 본다면 Zero 는 인자를 받지 않으며, Succ 은 인자를 받아 natural number를 돌려준다고 볼 수 있습니다.
Natvalue는Zero이거나Succ과 같은 형태 이기때문에 무한 sequence를 가질 수 있습니다.
Zero
Succ Zero
Succ (Succ Zero)
...
여기서는 undefined나 bottom에 대해 다루지 않지만 위의 경우는 통상 안전합니다.
- 우리는
Nat이 natural number를 표현한다고 생각하면Zero는 0,Succ은 (+1)로 생각할 수 있습니다. - 따라서 다음과 같은 경우,
Succ (Succ (Succ Zero))
다음과 같은 natural number와 같은 표현이라고 생각할 수 있습니다.
1 + (1 + (1 + 0)) = 3
또한, 우리는 recursion을 이용하여 Nat와 Int간 전환(convert)을 쉽게 할 수 있습니다.
nat2int :: Nat -> Int
nat2int Zero = 0
nat2int (Succ n) = 1 + nat2int n
int2nat :: Int -> Nat
int2nat 0 = Zero
int2nat n = Succ (int2nat (n-1))
첫 예제와 함께 Nat 은 Int 와 동일체인 것을 쉽게 확인 할 수 있습니다. 물론 몇가지 고려해야할 사항들이 있지만요.
두 개의 natural number를 integer로 변환하여 더한(add) 후 다시 변환하여 계산할 수도 있습니다.
add :: Nat -> Nat -> Nat
add m n = int2nat (nat2int m + nat2int n)
하지만, resursion을 이용하면 번거로운 변환작업을 하지 않아도 됩니다.
add Zero n = n
add (Succ m) n = Succ (add m n)
예를 보겠습니다.
add (Succ (Succ Zero))(Succ Zero)
= Succ (add (Succ Zero)(Succ Zero))
= Succ (Succ (add Zero (Succ Zero))
= Succ (Succ (Succ Zero))
정리하자면 add 에 대한 재귀는 다음 법칙을 따릅니다.
0 + n = n (1 + m) + n = 1 + (m + n)
Arithmetic Expressions
우리가 Parser를 배울 때 string에 대해 abstract syntax tree를 만드려 했지만 새로운 type에 대해 만드는 것을 알지 못했습니다. 대신에 우리는 주어진 expression의 값을 parsing을 통해 계산하는 방법을 보았습니다. 하지만 recursive type를 이용하면 수학적(algebraic) data type expression을 정의할 수 있습니다.
data Expr = Val Int
| Add Expr Expr
| Mul Expr Expr
일단 abstract base class인 Expr 을 정의하고 3가지 subtype을 정의합니다. 이를 이용하여 위의 그림을 표현하면 다음과 같습니다.
Add (Val 1) (Mul (Val 2) (Val 3))
앞으로 이런 recursion을 이용하여 expression을 처리하는 함수 또한 표현하기 쉽습니다.
size :: Expr -> Int
size (Val n) = 1
size (Add x y) = size x + size y
size (Mul x y) = size x + size y
eval :: Expr -> Int
eval (Val n) = n
eval (Add x y) = eval x + eval y
eval (Mul x y) = eval x * eval y
위 3가지 constructor들은 다음과 같은 타입을 가집니다.
Val :: Int -> Expr
Add :: Expr -> Expr -> Expr
Mul :: Expr -> Expr -> Expr
위 사항을 이용하면 무엇을 할 수 있을까요? expression에 대해 foldr을 정의할 때 2번 recursive function을 작성하지 않고 한번에 해결할 수 있습니다. 아래 예에서 id를 Val 로, (+)를 Add, (*)를 Mul 로 변경할 수 있습니다.
eval = fold id (+) (*)
Binary Trees
이제부터 binary Tree에 대해 처리하는 방법을 알아보겠습니다.
Recursion을 이용하여 binary tree는 다음과 같이 새로운 type으로 표현할 수 있습니다.
data Tree = Leaf Int | Node Tree Int Tree
위의 그림을 표현하면 다음과 같습니다.
Node (Node (Leaf 1) 3 (Leaf 4)) -- left
5 -- root
(Node (Leaf 6) 7 (Leaf 9)) -- right
또한, 주어진 integer에 대한 탐색을 하는 함수를 만들 수도 있습니다.
occurs :: Int -> Tree -> Bool
occurs m (Leaf n) = m==n
occurs m (Node l n r) = m==n
|| occurs m l
|| occurs m r
하지만 만일 같은 숫자가 binary tree 내 존재하지 않을 경우 모든 leaf를 다 탐색해야합니다.
그럼 다른 알고리즘을 이용해봅시다. 여기 새로운 함수를 정의하였습니다.
flatten :: Tree -> [Int]
flatten (Leaf n) = [n]
flatten (Node l n r) = flatten l
++ [n]
++ flatten r
flatten 은 주어진 tree를 integer list로 변환해 돌려줍니다. 여기서 만일 돌려받은 list가 정렬되어있다면(ordered) 이 tree는 search tree라고 말합니다.
이런 search tree에 대해서는 occurs 함수를 다음과 같이 변경할 수 있습니다.
occurs m (Leaf n) = m==n
occurs m (Node l n r) | m==n = True
| m<n = occurs m l
| m>n = occurs m r
이를 통해 훨씬 더 효율적인 것을 볼 수 있습니다.