Ich fange gerade an, mich mit Haskell zu befassen. Ich habe eine naive Fibonacci-Implementierung geschrieben, und ich habe auch eine fortgeschrittenere geschrieben Eine, die aus Effizienzgründen die Tail-Call-Rekursion verwendet.
module Fibonacci where import System.Environment fibonacci :: Integer -> Integer fibonacci 0 = 0 fibonacci 1 = 1 fibonacci n | n < 0 = error "Cannot find a negative fibonacci number" | otherwise = fibonacci (n - 1) + fibonacci (n - 2) fibonacci" :: Integer -> Integer fibonacci" n | n < 0 = error "Cannot find a negative fibonacci number" | otherwise = fibHelper n 0 1 where fibHelper :: Integer -> Integer -> Integer -> Integer fibHelper n a b | n == 0 = a | otherwise = fibHelper (n - 1) b (a + b) firstNumberFrom :: [String] -> Integer firstNumberFrom [] = 10 firstNumberFrom args = read $ args !! 0 main = do args <- getArgs let num = firstNumberFrom args in putStrLn $ show (fibonacci" num)
Ich würde mich über Bewertungen zur Korrektheit und zur idiomatischen Verwendung freuen.
Kommentare
- Was ist Ihr Zweck bei der Implementierung einer naiven Fibonacci-Funktion? Kennen Sie die Einschränkungen? Kennen Sie effizientere Fibonacci-Algorithmen?
- Das Haskell-Wiki enthält einen Artikel mit vielen verschiedenen Fibonacci-Implementierungen: wiki.haskell.org/The_Fibonacci_sequence
Antwort
Die vielen Ansätze in main
und firstNumberFrom
kann vereinheitlicht werden:
main = print . fibonacci" . maybe 10 read . listToMaybe =<< getArgs
Die explizite Rekursion in fibbonacci"
wird von iterate
erfasst:
fibbonacci" n = fst $ iterate (\(a,b) -> (b, a+b)) (0,1) !! n