하스켈/맛보기

하스켈은 비엄격한 의미론을 가진 표준 함수형 프로그래밍 언어이다. 하스켈은 다음과 같은 기능을 지원한다.

• 재귀 함수
• 데이터 타입
• 패턴 매칭
• 리스트 컴프리헨션

이러한 기능을 결합하면 절차적 프로그래밍 언어에서 작성하기 어려운 함수도 하스켈에서는 거의 간단하게 구현할 수 있다. 하스켈은 2011년 기준으로 가장 많은 연구가 진행되고 있는 함수형 언어이다.

아래 예제는 다른 프로그래밍 언어에 익숙한 사람을 위한 하스켈 맛보기이다.

예제

팩토리얼

팩토리얼 함수의 고전적 정의는 다음과 같다.

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

다음 정의는 하스켈 리스트 표기법과 표준 함수 product를 이용했다.

fac n = product [1..n]

위 두 정의는 등식 추론을 사용하는 컴파일러를 통해 동일하게 효율적인 코드로 컴파일 된다.

피보나치 수열

피보나치 수열에서 n번째 숫자를 반환하는 단순한 함수는 다음과 같이 구현한다.

fib 0 = 0
fib 1 = 1 
fib n = fib (n - 2) + fib (n - 1)

선형 시간에 피보나치 숫자 목록을 반환하는 함수는 다음과 같다.

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

위 함수는 무한 리스트를 정의한다. 하스켈의 느긋한 계산 기능 덕분에 무한 리스트 정의가 가능하다.

fib 함수를 다음과 같이 구현할 수 있다.

fib n = fibs !! n

(!!는 리스트의 n번째 요소를 가져오는 연산자이다.)

퀵 정렬

퀵정렬 알고리즘은 하스켈로 다음과 같이 간결하게 표현할 수 있다.

qsort []     = [] 
qsort (x:xs) = qsort [y | y<-xs, y < x ] ++ [x] ++
               qsort [y | y<-xs, y >= x]

(일반적으로 퀵 정렬은 제자리에서 값을 교환하지만 하스켈 리스트는 불변이므로 값을 복사해야 한다.)

합병 정렬

합병 정렬은 다음과 같이 구현한다.

mgsort less [] = []
mgsort less xs = head $ until (null.tail) pairs [[x] | x <- xs]
    where 
      pairs (x:y:xs)    = merge x y : pairs xs
      pairs xs          = xs
      merge (x:xs) (y:ys)
            | less y x  = y : merge (x:xs) ys 
            | True      = x : merge  xs (y:ys)
      merge  xs     ys  = xs ++ ys

(.)는 함수 합성 연산자이다. 함수 합성 연산자는 다음처럼 정의한다.

(h . g) x = h (g x)

(\x -> ...)는 람다 표현식(이름 없는 함수)이다. 미리 정의된 함수 until cond fun은 조건 cond가 만족될 때까지 함수 fun을 반복해서 적용한다. where 키워드를 사용하여 로컬 정의를 도입하면서 패턴 사용을 보여준다. (x:xs)는 비어 있지 않은 리스트를 머리 x와 꼬리 xs로 매칭하며 가드도 사용했다.

해밍 수열

해밍 수열은 다음과 같이 구현한다.

hamm = 1 : map (2*) hamm `union` 
              (map (3*) hamm `union` map (5*) hamm)
-- a union of two ordered lists:
union (x:xs) (y:ys) = case (compare x y) of
          LT -> x : union  xs  (y:ys)
          EQ -> x : union  xs     ys 
          GT -> y : union (x:xs)  ys

위 코드에서 (2*)와 같이 섹션(일부만 적용한 함수)을 사용했다. 내장 함수 map은 느긋한 계산법(또는 요구에 의한 호출) 덕분에 무한 리스트에도 적용할 수 있다. `union`과 같이 함수 이름을 억음 부호로 감싸면 중위 연산자처럼 쓸 수 있다. 이렇게 하면 union에 인자로 넣을 두 표현식에 자동으로 괄호가 쳐진 효과를 볼 수 있다. 줄표 두 개 다음에 적는 것은 주석이 된다.

무한 소수

나누기를 이용해서 무한 소수를 만드는 방법은 다음과 같다.

primes = 2 : sieve [3..] primes   -- 2 : _Y ((3:) . sieve [5,7..])
             where
             sieve xs (p:ps) | (h,t) <- span (< p*p) xs =
                                h ++ sieve [n | n <- t, rem n p > 0] ps

다음과 같이 정렬 리스트를 이용해 무한 소수를 만들 수 있다.

import Data.List.Ordered

primes = 2 : _Y ((3:) . minus [5,7..]   -- ps = [2..] \\ [[p*p, p*p+p..] | p <- ps]
                      . unionAll 
                      . map (\p -> [p*p, p*p+2*p..]))
  
_Y g = g (_Y g)       -- = g (g (g (g (g ... ))))

상호 재귀를 이용해 무한 소수를 만들 수 있다.

import Data.Array
import Data.List (tails, inits)

ps = 2 : [n | (r:q:_, px) <- (zip . tails . (2:) . map (^2)) ps (inits ps),
              (n,True)    <- assocs (
                                accumArray (\_ _ -> False) True (r+1,q-1)
                     [(m,()) | p <- px, 
                               let s = div (r+p) p * p,  m <- [s,s+p..q-1]] )]

하스켈은 퀵 정렬만을 위한 것이 아니다

하스켈은 GUI나 웹 같은 실생활 프로그램을 만드는 데에도 쓰인다. 하스켈로 만든 실생활 프로그램을 맛보고 싶다면 아래 자료를 참고하라.

• 하스켈 웹 프레임워크
• 하스켈 쓰는 회사
• 하스켈로 만든 버전 관리 시스템 Darcs