하스켈 첫걸음

Haskell을 람다식 계산기로 사용해보자

우선 정수(integer)나 진리값(boolean) 상수 등이 전혀 없는 순수한 람다식으로 조건문과 진리값을 만들어 쓰던 예제를 하스켈 프로그램으로 실행해보자. 함수 적용은 람다계산법의 문법 그대로이고 $(\lambda x.x)$와 같은 함수 정의는 하스켈 코드로는 (\x -> x)로 나타낸다. 즉 람다계산법에서 $\lambda$와 $.$이 하스켈에서는 \와 ->에 해당한다.

In [1]:
if_then_else c e1 e2 = ((c e1) e2)
true = (\x -> (\y -> x))
false = (\x -> (\ y -> y))




















In [2]:



    


if_then_else true 1 2























1



















In [3]:



    


if_then_else false 1 2























2

























Haskell의 문법을 조금 더 알아보자
괄호를 쓰지 않더라도 함수 적용은 왼쪽에서부터 묶이며 람다계산법에서의 $\lambda$에 해당하는
\로 정의하는 이름없는 함수는 오른쪽에서부터 묶인다.
그래서 아래와 같이 정의하더라도 위에서 정의한 것과 똑같다.
한줄 주석은 --로 시작하며 여러 줄 주석은 {-로 시작해서 -}로 끝마친다.


if_then_else의 경우처럼 함수 이름과 인자들을 = 왼쪽에 쓰고 오른쪽에 계산식을 쓰면 그것이 정의이다. true나 false의 경우처럼 함수 인자 없이 바로 이름만 써서 정의할 수도 있다.


IHaskell 환경에서는 = 없이 계산식만 나오면 계산식을 실행시켜 준다.













In [4]:



    


if_then_else c e1 e2 = c e1 e2  -- ((c e1) e2) 와 같다
true  = \x -> \y -> x  -- (\x -> (\y -> x)) 와 같다
false = \x -> \y -> y  -- (\x -> (\y -> y)) 와 같다

















In [5]:



    


{- 한번에 여러 개의 계산식을 실행해 보려면
   아래와 같이 여러 줄에 써주면 한줄씩 처리한다.
   자 이것이 여러 줄을 주석처리하는 방법이다! -}
if_then_else true 1 2
if_then_else false 1 2























1














2

























인자가 여러 개인 이름없는 함수를 정의할 때 여러 번 \를 쓰는 것이 번거로우므로 더욱 줄여 다음과 같이 써도 된다.













In [6]:



    


true  = \x y -> x  -- \x -> \y -> x 와 같다
false = \x y -> y  -- \x -> \y -> y 와 같다

-- 이렇게 정의와 계산식을 하나의 셀에 같이 포함해도 된다 
if_then_else true 1 2
if_then_else false 1 2























1














2

























위의 if_then_else도 함수 이름 다음에 인자를 써주는 대신에 람다식의 형태로도 정의할 수도 있으며 반대로 람다식으로 정의된 true와 false도 =왼쪽으로 인자를 넘겨서 정의할 수 있다.













In [7]:



    


if_then_else = \c e1 e2 -> c e1 e2
true  x y = x
false x y = y

if_then_else true 1 2
if_then_else false 1 2























1














2

























위의 예제는 하스켈을 람다식 계산기로 활용할 수 있다는 것을 보여주기 위한 것이고
실제로 프로그램을 작성할 때 자주 쓰는 조건문과 진리값은
하스켈에서 이미 기본적으로 제공하고 있다.













In [8]:



    


if True then 1 else 2
if False then 1 else 2























1














2

























하스켈 컴파일러에 어떤 정보를 문의해 알아본다거나 설정값을 바꾸거나 하는 등의
특별한 명령들은 :로 시작한다.
예를 들면 다음과 같이 :type이라는 명령으로 어떤 계산식의 타입이 무엇인지
하스켈 컴파일러에게 물어볼 수 있다.













In [9]:



    


:type True
:type False





















True :: Bool











False :: Bool
























진리값 상수인 True와 False의 타입은 Bool이라는 것을 알 수 있다. :: 기호는 오른쪽의 계산식이 왼쪽에 있는 타입을 갖는다는 의미이다. 여태까지 타입을 하나도 적어주지 않아서 하스켈이 마치 Python이나 JavaScript 등의 동적 스크립트 언어와 같이 타입에 별로 신경쓰지 않는 언어로 오해했을 수도 있는데, 하스켈은 처음 설계할 때부터 정적으로 (즉, 프로그램 실행 전에) 엄격하게 타입을 검사하는 언어이다. 다만 타입을 프로그래머가 직접 적어주지 않더라도 알아서 유추하는 타입 유추 기능이 강력하기 때문에 여태까지의 프로그램에서는 타입을 전혀 표시하지 않아도 되었던 것 뿐이다. 방금 소개한 if ... then ... else문도 타입을 엄격하게 검사하기 때문에 then과 else다음에 오는 식의 타입이 일치하지 않으면 다음과 같이 타입 오류가 발생한다.













In [10]:



    


if True then "hello" else (\x y -> y)





















Couldn't match expected type `t0 -> t1 -> t1' with actual type `String'
The lambda expression `\ x y -> y' has two arguments,
but its type `String' has none
In the expression: (\ x y -> y)
In the expression: if True then "hello" else (\ x y -> y)
























위 오류 메시지는 대략 then 다음에 오는 "hello"가 문자열 타입(String)이므로 else 다음에 오는 식도 문자열이어야 하는데 (\x y -> y)는 인자를 두 개 받는 함수 타입(t0 -> t1 -> t1)이라서 문자열 타입(String)과 맞아떨어지지 않는다는 뜻이다.



















수의 사칙연산 등도 물론 지원한다.













In [11]:



    


2 + 3      -- 덧셈
2 - 3      -- 뺄셈
2 * 3      -- 곱셈
2 / 3      -- 소수 나눗셈
2 `div` 3  -- 정수 나눗셈
2 `rem` 3  -- 정수 나머지























5














-1














6














0.6666666666666666














0














2

























하스켈에서 수와 관련된 타입은 약간 복잡한 나름 이유가 있는 사정이 있다. 일단 이 과목에서 Haskell을 활용하기 시작할 때는 굳이 그것까지 알아야 할 필요는 없지만 그래도 궁금한 사람들은 아래를 실행해 보고 이게 무엇을 뜻하는지 하스켈 관련 책이나 자료를 스스로 찾아보거나 찾아봐도 잘 이해가 안되면 개인적으로 문의하시길. 나중에 관련된 사항에 대해서 한번 정리해서 설명할 예정이다.













In [12]:



    


:type (+)
:type (-)
:type (*)
:type (/)
:type div
:type rem





















(+) :: forall a. Num a => a -> a -> a











(-) :: forall a. Num a => a -> a -> a











(*) :: forall a. Num a => a -> a -> a











(/) :: forall a. Fractional a => a -> a -> a











div :: forall a. Integral a => a -> a -> a











rem :: forall a. Integral a => a -> a -> a


















In [13]:



    


:type 1
:type 1.0





















1 :: forall a. Num a => a











1.0 :: forall a. Fractional a => a
























위와 같이 복잡한 사정에 대한 이해는 일단 접어두고, 앞에서 설명한 :: 기호를 코드상에서 써서 수의 타입을 간단하게 하나로 고정시킬 수 있다는 것은 알아두면 좋다.













In [14]:



    


:type (1 :: Int)       -- 컴퓨터에서 제공되는 고정 크기 정수
:type (1.0 :: Double)  -- 컴퓨터에서 제공되는 부동 소수점 수





















(1 :: Int) :: Int











(1.0 :: Double) :: Double
























그리고 (함수 포함) 어떤 이름을 정의할 때에도 :: 기호를 써서 직접 타입을 지정해 줄 수 있다.













In [15]:



    


x1, x2 :: Int
x1 = 3
x2 = 4

f1 :: Int -> Int -> Int
f1 x y = x^2 + y^2

















In [16]:



    


:t x1
:t x2
:t f1





















x1 :: Int











x2 :: Int











f1 :: Int -> Int -> Int


















In [17]:



    


f1 x1 x2























25



















In [18]:



    


f1 3.0 4.0   -- 타입 오류가 난다





















No instance for (Fractional Int) arising from the literal `3.0'
In the first argument of `f1', namely `3.0'
In the expression: f1 3.0 4.0
In an equation for `it': it = f1 3.0 4.0
























일진수 자연수에 대한 수학적 귀납법스러운 함수 정의












In [19]:



    


data Nat = Z | S Nat   deriving Show























위와 같이 새로운 데이타 타입으로 일진수 자연수를 정의할 수 있다. Nat은 데이타 타입의 이름이다. Z는 0을 나타내는 상수이며 S는 오른쪽에 오는 자연수보다 하나 더 큰 수를 나타낸다. 예를 들면 (S (S (S Z))은 3을 나타내는 일진수이다. 위의 데이타 타입 정의 끝부분에 나오는 deriving Show는 컴파일러가 알아서 Nat 타입의 값을 출력하는 방법을 자동으로 만들어 달라는 뜻인데 아직까지는 자세한 것은 몰라도 된다. 궁금한 사람은 알아서 찾아보고 그래도 잘 모르겠으면 개인적으로 질문하시길.













In [20]:



    


:type Z
:type S
:type (S Z)





















Z :: Nat











S :: Nat -> Nat











(S Z) :: Nat
























모든 일진수 자연수를 Haskell에서 제공하는 정수로 대응시킬 수 있다는 것을 수학적귀납법에 따라 증명하려면 다음과 같이 할 것이다. 일진수 자연수를 같은 값의 Haskell에서 제공하는 정수로 대응시키는 함수를 nat2int라고 부르자. 이 때 nat2int가 잘 정의될 수 있음을 보이는 수학적귀납법은 다음과 같다.


    

  1. 귀납기초(induction base): nat2int Z의 값은 0으로 정의 된다.
    2. 

  2. 귀납단계(induction step): n에 대한 귀납가정 즉 nat2int n의 값을 구할 수 있다고 가정하면 n 다음에 오는 n보다 1만큼 큰 일진수 자연수에 대한 경우인 nat2int (S n)을 귀납가정을 이용해 정의될 수 있음을 보이면 된다. 이것은 어렵지 않다 nat2int n의 결과에 1을 더해주기만 하면 된다.
    3. 



위의 수학적귀납법스러운 구조를 Haskell 프로그램으로 아래와 같이 작성할 수 있다.













In [21]:



    


nat2int Z     = 0
nat2int (S n) = 1 + nat2int n

















In [22]:



    


nat2int Z
nat2int (S (S (S Z)))























0














3

























위의 실행 예 중에서 nat2int (S (S (S Z)))의 계산과정을 수식을 전개하듯 다음과 같이 손으로 풀어볼 수 있다.



  nat2int (S (S (S Z)))
= 1 + nat2int (S (S Z))
= 1 + (1 + nat2int (S Z))
= 1 + (1 + (1 + nat2int Z))
= 1 + (1 + (1 + 0))
= 1 + (1 + 1)
= 1 + 2
= 3


우리들이 초등학교나 중학교 산수/수학 시간에 배운 등식을 바탕으로 수식 전개하는 익숙한 방법대로 프로그램의 실행에 대해 생각해 볼 수 있는 것이 함수형 프로그래밍의 특징이다. (어느 변수의 메모리의 내용을 변경시키는지 이런 기계중심의 사고방식이 아니라)



















리스트 (일진트리, 한갈래나무, unary tree로 볼 수도 있음)












In [23]:



    


data List = Nil | Cons Int List  deriving Show























리스트는 위와 같이 정의할 수 있다. 리스트는 빈 리스트를 나타내는 Nil이거나 아니면 Cons를 이용해 어떤 리스트의 맨 앞에 숫자 하나를 덧붙이면 그것이 또한 리스트가 된다. 4, 5, 6 이 차례로 들어 있는 리스트는 (Cons 4 (Cons 5 (Cons 6 Nil)))로 나타낸다.


흥미로운 사실은 리스트의 구조가 일진수의 구조와 유사하다는 점이다. 구체적으로는 N이 Nil에, S가 Cons가 대응된다. 일진수와 리스트의 차이점은 크기 혹은 길이가 하나 더 큰 구조를 만들 때 일진수는 S이외의 아무런 정보도 추가되지 않고 리스트는 Cons뒤에 정수값이 하나 더 추가 정보로 따라붙는다는 점이다.













In [24]:



    


:type Nil
:type Cons
:type Cons 6 Nil
:type Cons 6





















Nil :: List











Cons :: Int -> List -> List











Cons 6 Nil :: List











Cons 6 :: List -> List
























리스트의 길이를 구하는 함수 len을 작성해 보자. 일진수와 비슷한 구조를 가졌으므로 수학적귀납법스럽게 정의할 수 있다.
귀납기초에 해당하는 Nil의 경우 길이는 0이다. 귀납단계를 처리하기 위해서는 우선 어떤 리스트 xs의 길이를 구할 수 있다는 귀납가정을 하고 그 가정을 바탕으로 계산하여 거기에 어떤 수 x를 하나 덧붙인 리스트인 (Cons x xs)의 길이를 구하는 방법을 계산식으로 나타낼 수 있으면 된다.













In [25]:



    


len Nil         = 0
len (Cons x xs) = 1 + len xs

















In [26]:



    


len Nil
len (Cons 4 (Cons 5 (Cons 6 Nil)))























0














3

























리스트에 들어 있는 수들의 총합을 구하는  sumList 함수도 거의 같은 구조를 갖는다. 귀납가정에 해당하는 값에 1을 더하는 대신에 실제로 리스트에 들어 있는 수 x를 더하면 된다.













In [27]:



    


sumList Nil         = 0
sumList (Cons x xs) = x + sumList xs

















In [28]:



    


sumList Nil
sumList (Cons 4 (Cons 5 (Cons 6 Nil)))























0














15

























이진트리 (두갈래나무, binary tree)












In [29]:



    


data Tree = Null | Node Int Tree Tree  deriving Show























한 갈래로만 같은 구조가 반복될 수 있는 일진수나 리스트와 달리 이진트리는 두 갈래로 같은 구조가 반복될 수 있다.
따라서 한 갈래로만 생각하는 수학적 귀납법을 조금 더 일반화한 "구조적 귀납법"(structural induction)을 적용한다.
구조적 귀납법은 말로 설명하는 것보다 이진트리에 들어 있는 수들의 총합을 구하는 함수인
sumTree의 정의를 살펴보면 직관적으로 이해할 수 있을 것이다. sumTree와 앞서 정의한 sumList의 차이점을 대조해 보라.
sumTree에서는 귀납가정을 t1과 t2 각각의 갈래에 들어 있는 부분 나무들에 대해 두번 적용된 것을 볼 수 있다.
이와 같이 한 갈래로만 적용하는 수학적 귀납법을 여러 갈래의 부분구조에 대한 경우까지 포함하여 일반화한 것이 구조적 귀납법이다.













In [30]:



    


sumTree Null           = 0
sumTree (Node n t1 t2) = n + sumTree t1 + sumTree t2

















In [31]:



    


sumTree Null
sumTree (Node 5 (Node 4 Null Null) (Node 6 Null Null))























0














15

























이진트리의 높이를 구하는 height 함수를 작성해 보자.
귀납기초(induction base) 측 Null의 높이는 0이다. 귀납단계(inductive step)인 Node n t1 t2를 처리하기 위해서는 두 개의 귀납가정인 height t1과 height t2 중에 더 큰 값, 즉 t1과 t2 두 부분나무 중에 더 높은 높이값에 1을 더하면 전체 이진트리의 높이를 구할 수 있게 된다.

두 부분트리의 높이 중 더 큰 것을 선택하기 위해 max라는 표준라이브러리 함수를 사용하였다.













In [32]:



    


height Null = 0
height (Node n t1 t2) = 1 + max (height t1) (height t2)

















In [33]:



    


height Null
height (Node 5 (Node 4 Null Null) (Node 6 Null Null))























0














2



















In [38]:



    


:type max

max 2 1
max 1 2





















max :: forall a. Ord a => a -> a -> a













2














2

























max와 같은 함수를 정의하는 것도 어렵지 않다. max와 똑같은 일을 하는 mymax 함수는 다음과 같이 비교 연산자와 조건문을 써서 작성 가능하다.













In [37]:



    


mymax x y = if x > y then x else y

:type mymax
:type (>)

mymax 1 2
mymax 2 1





















mymax :: forall a. Ord a => a -> a -> a











(>) :: forall a. Ord a => a -> a -> Bool













2














2

























(>) 이외에도 당연히 있어야 할 것 같은 다음 비교연산자들도 정수 등의 수 타입에 대해 정의되어 있다.













In [39]:



    


:type (>)  -- 크다
:type (>=) -- 크거나 같다
:type (<)  -- 작다
:type (<=) -- 작거나 같다
:type (==) -- 같다
:type (/=) -- 같지 않다





















(>) :: forall a. Ord a => a -> a -> Bool











(>=) :: forall a. Ord a => a -> a -> Bool











(<) :: forall a. Ord a => a -> a -> Bool











(<=) :: forall a. Ord a => a -> a -> Bool











(==) :: forall a. Eq a => a -> a -> Bool











(/=) :: forall a. Eq a => a -> a -> Bool