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 qualified Data.Semigroup as Semigroup
  26
  27 -------------------------------------------------------------
  28 fib' :: Integer -> Integer
  29 fib' 0 = 0
  30 fib' 1 = 1
  31 fib' n = fib (n-1) + fib (n-2)
  32 -------------------------------------------------------------
  33
  34
  35 data Matrix2x2 = Matrix
  36     { x00 :: Integer, x01 :: Integer
  37     , x10 :: Integer, x11 :: Integer
  38     }
  39
  40 instance Monoid Matrix2x2 where
  41     mempty =
  42         Matrix
  43             { x00 = 1, x01 = 0
  44             , x10 = 0, x11 = 1
  45             }
  46
  47 instance Semigroup Matrix2x2 where
  48     Matrix l00 l01 l10 l11 <> Matrix r00 r01 r10 r11 =
  49         Matrix
  50             { x00 = l00 * r00 + l01 * r10, x01 = l00 * r01 + l01 * r11
  51             , x10 = l10 * r00 + l11 * r10, x11 = l10 * r01 + l11 * r11
  52             }
  53
  54 fib :: Integer -> Integer
  55 fib n = x01 (Semigroup.mtimesDefault n matrix)
  56   where
  57     matrix =
  58         Matrix
  59             { x00 = 0, x01 = 1
  60             , x10 = 1, x11 = 1
  61             }