make it functional 함수형 프로그래밍의 모든 것

제2회 대안언어축제의 공통문제에 대한 풀이와 해설입니다. 문제에 대한 설명은 공통문제집합을 참고하세요.

합계

기본 함수인 sum을 쓰면 됩니다.

sum [1,2,3]

그럼 sum은 어떻게 정의되어 있을까요?

sum = foldl (+) 0

fold계열의 함수들은 리스트에 있는 원소들 사이에 함수를 적용합니다. foldl은 왼쪽부터 계산하고, foldr은 오른쪽부터 계산합니다. 위의 식의 의미는 0부터 시작해서 리스트에 있는 원소들을 모두 더하라는 뜻입니다. 덧셈은 어느 쪽 먼저 계산하든 상관없으니까 다음과 같이 정의해도 됩니다.

sum = foldr (+) 0

평균

이 부분은 Haskell 초보자에게 가장 어려운 부분입니다. 길이가 기니까 별도의 페이지에서 자세히 얘기하겠습니다.

구구단

간단히 다음과 같이 하면 됩니다.

timesTable = [x*y| x <- [1..9], y <- [1..9] ]

단 하나가 리스트 하나가 되게 하는 방법도 있습니다.

timesTable = [ [x*y| x <- [1..9] ] | y <- [1..9] ]

아래처럼 쓰는 게 이해하기는 제일 쉬울 겁니다.

dan n = map (*n) [1..9]
timesTable = map dan [1..9]

예쁘게 출력하는 부분은 숙제로 맡겨 둡니다.

우애수

우애수란 자기 자신을 제외한 약수의 합이 서로가 되는 두 정수를 말합니다. 그러니까 일단 약수를 구하는 함수가 필요합니다. 약수의 정의를 그대로 써주면 됩니다.

divisor n = [x| x <- [1.. n-1], mod n x == 0]

나머지는 간단합니다. 아래는 gimmesilver님의 코드를 조금 손 본 것입니다.

sumDiv = sum . divisor -- 약수의 합
amicable n = [(x,sumDiv x) | x <- [1..n], x < sumDiv x, x == (sumDiv $ sumDiv x)]

그러나 이 우애수 프로그램은 속도가 무척 느립니다. gimmesilver님과 같이 고민을 해봤는 데 속도가 좀처럼 개선이 안되더군요. 가장 간단한 방법은 divisor 함수에서 n-1 대신 div n 2를 써주면 됩니다. 약수들은 항상 자기 짝을 가지고 있는 데 1은 n과, 2는 div n 2와 짝이니까 div n 2보다 큰 약수는 없습니다. 그러면 속도가 2배 빨라지겠죠.

cooking_curry님의 답글을 보고 추가합니다. 모든 약수는 자기 짝이 있습니다. 그러니까 작은 쪽 짝을 찾으면 큰 쪽 짝도 저절로 찾아집니다. 18에서 2를 찾으면 바로 9를 찾을 수 있지요. 이렇게 검색을 하면서 왼쪽과 오른쪽에서 짝을 찾아가다보면 가장 마지막에 만나는 것은 짝이 자기 자신인 n의 제곱근입니다. n이 36이라면 2,18,3,12,4,9까지 찾은 다음에는 6을 찾게 되죠. 루트 36이 6입니다. 그래서 이 소스에는 리스트의 끝을 div n 2가 아니라 루트 n으로 정해주면 그만큼 시간을 더 절약하게 됩니다.

휘동그레님의 아이디어를 바탕으로 코드를 좀 더 간결하게 고쳤습니다.

divisor n = nub $ ds ++ map (div n) (tail ds) where
	ds = [x| x <- [1..intSqrt n], mod n x == 0]

듀얼코어 3GHz, 512MB램에서 테스트를 해봤습니다. div n 2까지 찾는 경우는 58초, 위의 코드는 9초 걸립니다. 인터프리터 상에서 돌리는 대신 컴파일해서 실행파일로 만들어 돌려보니 각각 11초, 1.7초 걸리는군요. 결국 컴파일러가 5~6배, 알고리듬이 6배 정도 속도를 향상 시켜줍니다. 그러니까 Haskell 코드가 느리다면 일단 컴파일부터 해보세요. :)

뒤집어 더하기

주어진 숫자가 있을 때, 그 숫자의 개별숫자의 순서를 뒤집어서 나온 숫자를 원래 숫자에 더합니다. 만약 합이 팰린드롬(앞으로 읽으나 거꾸로 읽으나 동일한 것)이 아니라면 이 과정을 반복해서 팰린드롬이 되기 위해 반복해야 하는 횟수와 해당 팰린드롬을 돌려줍니다.

숫자를 뒤집는 가장 쉬운 방법은 문자열로 바꾼 다음, 뒤집어서 숫자로 읽어들이는 것입니다.

revNum = read . reverse . show

팰린드롬인지 판단하는 함수는 간단하죠. 뒤집었는 데도 똑같으면 팰린드롬입니다.

palindrome n = n == revNum n

그 다음엔 숫자를 뒤집고 더하고 이것을 계속 반복하지요. 아래 iterate 는 함수를 무한히 반복적용해주는 표준함수입니다. x를 뒤집어 더하고 그렇게 나온 수를 또 뒤집어 더하고.. break 함수는 리스트를 조건에 따라 둘로 쪼개줍니다. 여기서는 팰린드롬 앞쪽에서 쪼갭니다.

reverseAndAdd = (\(x,y) -> (length x, head y) ) . break palindrome . iterate (\n -> n + revNum n) 

Haskell 코드를 짤 때는 가능하면 람다 함수나 조건제시법을 적게 쓰는 것이 더 좋습니다. 일단 코드가 예쁘지 않거든요. 다음과 같이하면 깔끔합니다.

tuple f g (x,y) = (f x, g y)
reverseAndAdd = tuple length head . break palindrome . iterate (\n -> n + revNum n) 

할인가격

기름값을 계산하는 문제입니다. 많이 사면 할인을 해줍니다.

1. 처음 20 리터 : 리터 당 90원
2. 다음 40 리터 : 리터 당 80원
3. 나머지 : 리터 당 75원

예를 들어 35갤론을 구입한다면, 가격은 30달러가 됩니다. 이 문제는 사실 아주 간단한으로 풀 수 있습니다. 꼭 복잡한 계산을 해야한다는 편견을 버리고 1리터짜리 석유통이 줄줄이 있다고 생각해봅시다.

oilPrice n = sum $ take n $ replicate 20 90 ++ replicate 40 80 ++ repeat 75

Haskell처럼 지연 계산하는 언어만 짤 수 있는 코드입니다. 75원짜리 석유통이 무한히 있어야 할테니까요. 위의 코드는 3.5리터 같은 건 살 수 없고, 가격을 바꿀 수도 없고 결정적으로 느리다는 단점이 있습니다. 그럼 어떻게 할까요.

quantity x [] = [x]
quantity x (y:ys) = (min x y) : quantity (max 0 (x-y)) ys 

oilPrice q p x = sum $ zipWith (*) p (quantity x q)

examplePrice = oilPrice [20,40] [90,80,75]

시어핀스키 삼각형

시어핀스키 삼각형은 간단합니다. 원래 도형을 아래쪽에 하나, 아래 오른쪽에 하나 덧붙이는 것을 반복합니다. 어떤 모양이 되는 지는 대안언어축제2006/SierpinskiTriangle을 참고하세요.

fillSpace list = map ( take n . (++ repeat ' ')) list where n = length $ last list
nextTriangle x = fillSpace $ x ++ zipWith (++) x x
sierpinsky n = putStr $ unlines $ (!! n) $ iterate nextTriangle ["*"]

nextTriangle은 원래 도형 x를 zipWith (++)로 두 개 이어붙인 다음에 원래 도형 뒤에 붙여줍니다. 그리고 fillSpace로 삼각형 오른쪽 위를 스페이스로 채워줍니다. sierpinsky는 ["*"]에서 시작해 이것을 무한히 반복하는 리스트를 만듭니다. 여기서 n번째 원소를 가져다가(!! n) 모든 문자열에 엔터를 넣어주고(unlines) 출력합니다.