haskell 로 프로젝트 오일러의 25번 문제를 풀어봤다

http://www.haskell.org/haskellwiki/Memoization 읽어보자.
오일러 포럼에는 수학적으로 푼 넘들도 많은데 헐.. 
어릴때 공부 안한게 후회스러울 따름.
http://www.haskell.org/haskellwiki/Euler_problems/21_to_30#Problem_25
도 참고해보자.. 그런데 읽기 어렵네. 어쨌건 돌려보니 내거하곤 성능차이가..
한글위키피디아에 이런 페이지도 있다.


import Data.List(findIndex)

-- 간단한 구현. 이건 속도때문에 꽝. 코드가 트리형태로 전개되기 때문에
-- 매우 느리다.
fibBad 1 = 1
fibBad 2 = 1
fibBad n = fib (n-1) + fib (n-2)
                               

-- 헐 쫌더 나은 버전일랑가.
-- 함수형 언어라면 간지나게 memoize 등을 써서 푸는게 맞을거 같은데
-- 간단히 Data.Map 하나 두고 캐시처럼 써먹는 모듈을 짜보려고 했으나
-- 실패. 이거뭐.. 어떻게 시작해야 할지도 모르겠더라. 일단 문제는 풀어야
-- 겠으니 익숙한 식대로 루프돌렸다.
fib 1 = 1
fib 2 = 1
fib n = f 3 1 1 2
    where f step older old cur
              | step == n = cur
              | otherwise = let newstep  = step+1
                                newolder = old
                                newold   = cur
                                newcur   = newolder+newold
                            in f newstep newolder newold newcur

-- fib 함수로 리스트 생성
fibs = map fib [1..]

-- 자릿수
digits :: (Num a) => a -> Int
digits = length . show

-- 풀이. 리스트는 0 base 이고 위 fib 는 1 base 이므로 1 만큼 보정을 했다.
solve = (+1) `fmap` findIndex ((==1000) . digits) fibs

-- 우왕국
-- 현재 내 PC 에서는 대략 2 초정도에 끝난다.
main = print solve