HASKELL FIBONACCI SEQUENCE

REVISED: Wednesday, January 24, 2024

Haskell Fibonacci sequence.

I. HASKELL FIBONACCI SEQUENCE

The "Fibonacci Sequence" was named after Leonardo "Pisano" Fibonacci an Italian mathematician who was born around 1175 and died around 1250.

The Fibonacci [pronounced fib-on-arch-ee] Sequence is a recursive sequence which obeys the rule that to calculate the next term, one sums the preceding two. For example, the positive index Fibonacci Sequence is the sequence of numbers: 0,1,1,2,3,5,8,13,21,... Each number in the Fibonacci Sequence equals the sum of the two numbers before it. However, there is an exception in regards to the first two numbers in the positive index Fibonacci Sequence. By definition f₀ the first number in the positive index Fibonacci Sequence, is 0. Also by definition f₁ the second number in the positive index Fibonacci Sequence, is 1. The first two numbers are needed to start the sequence. f₂ is computed as 0+1=1. f₃ is 1+1=2. f₄ is 1+2=3. f₅ is 2+3=5, and so on.

f₀ = 0 by definition.
f₁ = 1 by definition.
f₂ = f₀ + f₁ = 0 + 1 = 1
f₃ = f₁ + f₂ = 1 + 1 = 2
f₄ = f₂ + f₃ = 1 + 2 = 3
f₅ = f₃ + f₄ = 2 + 3 = 5

The positive index Fibonacci Sequence can also be extended to a negative index; i.e.,

f_-n.

EXAMPLE 1

Save the following as fib.hs

fib :: (Eq a, Num a) => a -> a
fib 0 = 0
fib 1 = 1
fib f = fib (f-1) + fib (f-2)

Then open GHCi; :load fib.hs; and run fib as shown below:

Prelude>  :load fib
[1 of 1] Compiling Main             ( fib.hs, interpreted )
Ok, modules loaded: Main.
Prelude>

Prelude>  fib 0    -- fib 0 = 0
0
it :: (Num a, Eq a) => a
Prelude>

Prelude>  fib 1    -- fib 1 = 1
1
it :: (Num a, Eq a) => a
Prelude>

Prelude>  fib 2    -- 0 + 1= 1
1
it :: (Num a, Eq a) => a
Prelude>

Prelude>  fib 3    -- 1 + 1 = 2
2
it :: (Num a, Eq a) => a
Prelude>

Prelude>  fib 4    -- 1 + 2 = 3
3
it :: (Num a, Eq a) => a
Prelude>

Prelude>  fib 5    -- 2 + 3 = 5
5
it :: (Num a, Eq a) => a
Prelude>

Prelude>  fib 6
8
it :: (Num a, Eq a) => a
Prelude>

Prelude>  fib 7
13
it :: (Num a, Eq a) => a
Prelude>

Prelude>  fib 8
21
it :: (Num a, Eq a) => a
Prelude>

Prelude>  fib 9
34
it :: (Num a, Eq a) => a
Prelude>  

EXAMPLE 2

Save the following as fibGen.hs

fib :: (Eq a, Num a, Num a1) => a -> a1
fib f = fibGen 0 1 f

fibGen :: (Eq a, Num a, Num a1) => a1 -> a1 -> a -> a1
fibGen a b f = case f of
0 -> a
f -> fibGen b (a + b) (f - 1)

Then open GHCi; :load fibsGen.hs; and run fib as shown below:

Prelude>  :load fibGen
[1 of 1] Compiling Main             ( fibGen.hs, interpreted )
Ok, modules loaded: Main.
Prelude>

Prelude>  fib 0
0
it :: Num a1 => a1
Prelude>

Prelude>  fib 1
1
it :: Num a1 => a1
Prelude>

Prelude>  fib 2
1
it :: Num a1 => a1
Prelude>

Prelude>  fib 3
2
it :: Num a1 => a1
Prelude>

Prelude>  fib 4
3
it :: Num a1 => a1
Prelude>

Prelude>  fib 5
5
it :: Num a1 => a1
Prelude>

Prelude>  fib 6
8
it :: Num a1 => a1
Prelude>

Prelude>  fib 7
13
it :: Num a1 => a1
Prelude>

Prelude>  fib 8
21
it :: Num a1 => a1
Prelude>

Prelude>  fib 9
34
it :: Num a1 => a1
Prelude> 

EXAMPLE 3

Save the following as fibs.hs

fibs :: [Integer]
fibs = 0 : 1 : [ a + b | (a, b) <- zip fibs (tail fibs)]

Then open GHCi; :load fibs.hs; and run fibs as shown below:

Prelude>  fibs !! 0
0
it :: Integer
Prelude>

Prelude>  fibs !! 1
1
it :: Integer
Prelude>

Prelude>  fibs !! 2
1
it :: Integer
Prelude>

Prelude>  fibs !! 3
2
it :: Integer
Prelude>

Prelude>  fibs !! 4
3
it :: Integer
Prelude>

Prelude>  fibs !! 5
5
it :: Integer
Prelude>

Prelude>  fibs !! 6
8
it :: Integer
Prelude>

Prelude>  fibs !! 7
13
it :: Integer
Prelude>

Prelude>  fibs !! 8
21
it :: Integer
Prelude>

Prelude>  fibs !! 9
34
it :: Integer
Prelude>

!! is the index operator for lists in Haskell. Haskell lists are 0-indexed.

Prelude>  [0,1,1,2,3,5,8,13,21,34]!!0
0
it :: Num a => a
Prelude>

Prelude>  [0,1,1,2,3,5,8,13,21,34]!!1
1
it :: Num a => a
Prelude>

Prelude>  [0,1,1,2,3,5,8,13,21,34]!!2
1
it :: Num a => a
Prelude>

Prelude>  [0,1,1,2,3,5,8,13,21,34]!!3
2
it :: Num a => a
Prelude>

Prelude>  [0,1,1,2,3,5,8,13,21,34]!!4
3
it :: Num a => a
Prelude>

Prelude>  [0,1,1,2,3,5,8,13,21,34]!!5
5
it :: Num a => a
Prelude>

Prelude>  [0,1,1,2,3,5,8,13,21,34]!!6
8
it :: Num a => a
Prelude>

Prelude>  [0,1,1,2,3,5,8,13,21,34]!!7
13
it :: Num a => a
Prelude>

Prelude>  [0,1,1,2,3,5,8,13,21,34]!!8
21
it :: Num a => a
Prelude>

Prelude>  [0,1,1,2,3,5,8,13,21,34]!!9
34
it :: Num a => a
Prelude>  

Using tail recursion, while slightly more complex, will prevent the exponential growth of function calls.

The value of tail recursion is that in a tail recursive call, the "caller" does nothing except pass up the value that is returned by the "callee"; and that, in turn, means that you do not need to return to the "caller". If you think of it in terms of primitive machine-level code, in a tail recursive call, you can use a direct branch instruction instead of a branch to subroutine; the tail recursive call does not need to create a new stack frame. It can just reuse the "callers" frame.

Prelude>  tail [0,1,1,2,3,5,8,13,21,34]
[1,1,2,3,5,8,13,21,34]
it :: Num a => [a]
Prelude>

Prelude>  zip [0,1,1,2,3,5,8,13,21,34] $ tail [0,1,1,2,3,5,8,13,21,34]
[(0,1),(1,1),(1,2),(2,3),(3,5),(5,8),(8,13),(13,21),(21,34)]  -- (a, b) <-
it :: (Num b, Num a) => [(a, b)]
Prelude>  

Prelude>  let y = 0 : 1 : [ a + b | (a,b) <- zip [0,1,1,2,3,5,8,13,21,34] $ tail [0,1,1,2,3,5,8,13,21,34]]
y :: Num a => [a]
Prelude>

Prelude>  y
[0,1,1,2,3,5,8,13,21,34,55]    -- The Fibonacci Sequence...
it :: Num a => [a]
Prelude>  

EXAMPLE 4

Prelude> import Data.List

Prelude Data.List> fibs = 0 : scanl (+) 1 fibs

Prelude Data.List> take 10 fibs
[0,1,1,2,3,5,8,13,21,34]   -- The Fibonacci Sequence...

Prelude Data.List>

EXAMPLE 5

Save the following as fibs5.hs

import System.Environment (getArgs)

main = do

     args <- getArgs

     let n = (read (args !! 0) :: Int)

     putStrLn (show (fibs !! (n-1)))

fibs = 0 : 1 : [ a + b | (a, b) <- zip fibs (tail fibs) ]

Then open GHCi; :load fibs5.hs; and run fibs as shown below:

*Main>  take 10 fibs
[0,1,1,2,3,5,8,13,21,34]
*Main>

II. REFERENCES

Bird, R. (2015). Thinking Functionally with Haskell. Cambridge, England: Cambridge University Press.

Davie, A. (1992). Introduction to Functional Programming Systems Using Haskell. Cambridge, England: Cambridge University Press.

Goerzen, J. & O'Sullivan, B. &  Stewart, D. (2008). Real World Haskell. Sebastopol, CA: O'Reilly Media, Inc.

Hutton, G. (2007). Programming in Haskell. New York: Cambridge University Press.

Lipovača, M. (2011). Learn You a Haskell for Great Good!: A Beginner's Guide. San Francisco, CA: No Starch Press, Inc.

Thompson, S. (2011). The Craft of Functional Programming. Edinburgh Gate, Harlow, England: Pearson Education Limited.

In this tutorial, you have been introduced to the Haskell Fibonacci sequence.