Mercurial > repos > other > SevenLanguagesInSevenWeeks

comparison 7-Haskell/fibonacci.hs @ 87:2b5341fc4555

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add Haskell Day 1 code and notes
author IBBoard <dev@ibboard.co.uk>
date Sat, 15 Jun 2019 17:31:22 +0100
parents
children
comparison
equal deleted inserted replaced
86:ab08b4bcd4a9 87:2b5341fc4555
1 module Fibonacci where
2 -- Classic imperative Fibonacci
3 -- XXX: This seems to give odd answers! "fib_simple 0" gives 1 when it should be 0 (0-based indexing) or an error (1-based indexing)!
4 fib_simple :: Integer -> Integer
5 fib_simple 0 = 1
6 fib_simple 1 = 1
7 fib_simple x = fib_simple (x - 1) + fib_simple (x - 2)
8
9 -- Fibonacci with tuples and effective caching
10 -- This works by using the parameter as the number of steps and iterating those in the tuple
11 -- Note: We're zero-indexing, so "fib 0" is the first Fibonacci number
12 fib :: Integer -> Integer
13 fib x = fibResult (fibTuple (0, 1, x))
14
15 fibResult :: (Integer, Integer, Integer) -> Integer
16 fibResult (x, y, z) = x
17
18 fibTuple :: (Integer, Integer, Integer) -> (Integer, Integer, Integer)
19 fibTuple (x, y, 0) = (x, y, 0)
20 fibTuple (x, y, index) = fibTuple (y, x + y, index -1)