LangDev

2^k - 1 을 매우 비효율적으로 계산하는 하스켈 예제 (실용적으로 아무 쓸모 없음)

안기영

맨 첫줄에 꼭 뭘 써줘야 코드 블럭이 되는군요 음 ...

data Nat = Z
         | S Nat
  deriving (Show,Read,Eq,Ord)

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

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

-- binexp n = 2^n

binexp n = S (f n [])

-- f n xs = (2^k - 1) + sum [2^k | k<-xs]

f Z     []     = Z           -- 2^0 - 1 = 0
f Z     (x:xs) = S (f x xs)  -- sum [2^k | k<-x:xs] = 1 + (2^x-1) + sum [2^k | k<-xs]
f (S n) xs     = f n (n:xs)  -- (2^(n+1)-1) + sum [2^k | k<-xs] = (2^n-1) + sum [2^k | k<-x:xs]

{-
example run on ghci:

Main> nat2int $ binexp (int2nat 10)
1024

Main> nat2int $ f (int2nat 10) []
1023
-}

자연수의 정의를 이용한 소름끼치는 구현이군요. 기왕이면 f의 구현도 Nat만을 이용해서 이루어졌다면 더 멋졌겠군요.

Kroisse

이 예제는 실용적으로 그다지 쓸모가 없지만 이런 식의 코드가 함수형 프로그래밍 코드에 자주 등장합니다. 랑데브 IRC 채널에서 꼬리 되돌기(tail recursion)는 반복문(loop)으로 대치가 가능한데 명령형 언어에서 굳이 꼬리 되돌기로 프로그래밍을 하고 컴파일러가 tail call optimization까지 해 주는 건 불필요하지 않냐는 의견에 대한 답변으로서, 꼬리 되돌기는 반복문으로 표현하면 복잡해지거나 귀찮아지는 이런 것들도 간단히 표현할 수 있다는 것을 보여주는 귀여운 예제라고 생각해서 올렸습니다. 저런 걸 명령형 언어식의 일차원적 반복문으로로 구현하려면 최소한 이중 루프 들어가야 합니다.

안기영