30000! 빨리 계산하기 with Haskell

* 꼬리 재귀호출과 패턴 매칭을 이용하여 구현한 팩토리얼과 피보나치 수열 계산

{-
    Filename: fact.hs
         Rapid factorial and fibonacci seq implementations
         by pattern matching and tail recursive call

    Compile: ghc fact.hs
    Execute: main

    Date: 2010/07/20
    Author: phkim  pkim (AT) scripts.pe.kr
-}

module Main where

  factorial :: Integer -> Integer
  factorial n =  recfact 1 n

  recfact :: Integer -> Integer -> Integer
  recfact acc k = case k of
        0 -> acc
        k-> recfact (acc*k) (k - 1)

  fib :: Integer -> Integer
  fib n = fibGen 0 1 n

  fibGen :: Integer -> Integer -> Integer -> Integer
  fibGen a b n = case n of
        0 -> a
        n -> fibGen b (a + b) (n - 1)

  main :: IO ()
  main = do
        print ("Factorial(30000) has " ++ show (length (show (factorial 30000))) ++ " digits")
        print ("Fibonacci(200000) has " ++ show (length (show (fib 200000))) ++ " digits")

{-
    Expected result:
    "Factorial(30000) has 121288 digits"
    "Fibonacci(200000) has 41798 digits"
-}

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-동일조건변경허락 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.