src/Gargantext/Prelude/Fibonacci.hs

   1 {-|
   2 Module      : Gargantext.Prelude.Utils
   3 Description : Useful Tools near Prelude of the project
   4 Copyright   : (c) CNRS, 2017-Present
   5 License     : AGPL + CECILL v3
   6 Maintainer  : team@gargantext.org
   7 Stability   : experimental
   8 Portability : POSIX
   9
  10 Nice optimization of the Fibonacci function.
  11
  12 Source:
  13 Gabriel Gonzales, Blazing fast Fibonacci numbers using Monoids, 2020-04,
  14 http://www.haskellforall.com/2020/04/blazing-fast-fibonacci-numbers-using.html
  15 (This post illustrates a nifty application of Haskell’s standard library to solve a numeric problem.)
  16
  17 TODO: quikcheck
  18
  19 -}
  20
  21
  22
  23 module Gargantext.Prelude.Fibonacci where
  24
  25 import Protolude
  26
  27 import qualified Data.Monoid as Monoid
  28 import qualified Data.Semigroup as Semigroup
  29
  30 -------------------------------------------------------------
  31 fib' :: Integer -> Integer
  32 fib' 0 = 0
  33 fib' 1 = 1
  34 fib' n = fib (n-1) + fib (n-2)
  35 -------------------------------------------------------------
  36
  37
  38 data Matrix2x2 = Matrix
  39     { x00 :: Integer, x01 :: Integer
  40     , x10 :: Integer, x11 :: Integer
  41     }
  42
  43 instance Monoid.Monoid Matrix2x2 where
  44     mempty =
  45         Matrix
  46             { x00 = 1, x01 = 0
  47             , x10 = 0, x11 = 1
  48             }
  49
  50 instance Semigroup.Semigroup Matrix2x2 where
  51     Matrix l00 l01 l10 l11 <> Matrix r00 r01 r10 r11 =
  52         Matrix
  53             { x00 = l00 * r00 + l01 * r10, x01 = l00 * r01 + l01 * r11
  54             , x10 = l10 * r00 + l11 * r10, x11 = l10 * r01 + l11 * r11
  55             }
  56
  57 fib :: Integer -> Integer
  58 fib n = x01 (Semigroup.mtimesDefault n matrix)
  59   where
  60     matrix =
  61         Matrix
  62             { x00 = 0, x01 = 1
  63             , x10 = 1, x11 = 1
  64             }