CODEWITHSUNDEEP
haskell
Madalina
Madalina

Reputation: 85

Sum of first n fibonacci numbers haskell

I have tu calculate the sum of first n fibonacci numbers. fib function returns the nth fibonnaci number. But i dont know how to sum only the first n numbers ( n given number )

fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib x = fib (x-1) + fib (x-2)

sumFib :: Int -> Int 
sumFib x = if x == fib x then x+fib x else fib x

Upvotes: 0

Views: 1350

Answers (4)

GÖKAY GÖK
GÖKAY GÖK

Reputation: 81

fibo 0=0
fibo 1=1
fibo n=fibo(n-2)+fibo(n-1)
fibosum n=sum [fibo i | i<-[0..n-1]]

This code calculate the sum of first n fibonacci numbers. fibo function is calculate fibonacci numbers.

Upvotes: 0

Madalina
Madalina

Reputation: 85

fib finds the n'th fibonacci number 

fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib x = fib (x-1) + fib (x-2)

map' is the implemantation of standard map function ( I wasn't allowed to use it) 

map' :: (a -> b) -> [a] -> [b]
map' _ [] = []
map' f (x:xs) = f x : map' f xs

sumFib calculates the sum of first n fibonnaci numbers.

sumFib :: Int -> Int 
sumFib x = sum (map' fib [1..x])

Upvotes: 1

Redu
Redu

Reputation: 26161

Another good option would be to generate a lazy function to provide us a list of Fibonacci numbers indefinitely as many as we need. While we can achieve this with a lot of recursive trick, i believe the series generating function of Haskell, namely unfoldr is the ideal one. The following code will beautifully generate us a list of as many of Fibonacci numbers as wee need lazily.

fibs :: [Integer]
fibs = unfoldr (\(f,s) -> Just (f,(s,f+s))) (0,1)

Now all we have to do is to get the sum of the Fibonacci numbers up to a given count. At this point the take function comes handy. take will take the first n items of a list. Then all we need to do is to apply the sum function to the resulting list.

fibs :: [Integer]
fibs = unfoldr (\(f,s) -> Just (f,(s,f+s))) (0,1)

sumNFibs :: Int -> Integer
sumNFibs = sum . (flip take) fibs

*Main> sumNFibs 10
88

Upvotes: 2

Cirdec
Cirdec

Reputation: 24156

The first n numbers are [1 .. n]. For example, in ghci

Prelude> [1..7]
[1,2,3,4,5,6,7]

You can map a function onto a list, applying that function to each element in the list, and returning the resulting list. For example

Prelude> double x = x+x
Prelude> map double [1..7]
[2,4,6,8,10,12,14]

You can do the same thing with fib, maping it onto the first n numbers. If you want to do this for large n you'll need a more efficient implementation of fib.

You can sum the elements in a list. For example

Prelude> sum [1,3,7]
11

If you put these three ideas together you can sum the result of fib for the first n numbers.

Upvotes: 2

Related Questions