opentheory-fibonacci (empty) → 1.69

raw patch · 5 files changed

+147/−0 lines, 5 filesdep +QuickCheckdep +basedep +opentheorysetup-changed

Dependencies added: QuickCheck, base, opentheory, opentheory-primitive, opentheory-stream

Files

LICENSE +17/−0
Setup.hs +6/−0
opentheory-fibonacci.cabal +37/−0
src/OpenTheory/Natural/Fibonacci.hs +50/−0
src/Test.hs +37/−0

+ LICENSE view

@@ -0,0 +1,17 @@+Permission is hereby granted, free of charge, to any person obtaining a copy+of this software and associated documentation files (the "Software"), to deal+in the Software without restriction, including without limitation the rights+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell+copies of the Software, and to permit persons to whom the Software is+furnished to do so, subject to the following conditions:++The above copyright notice and this permission notice shall be included in+all copies or substantial portions of the Software.++THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN+THE SOFTWARE.

+ Setup.hs view

@@ -0,0 +1,6 @@+module Main ( main ) where++import Distribution.Simple++main :: IO ()+main = defaultMain

+ opentheory-fibonacci.cabal view

@@ -0,0 +1,37 @@+name: opentheory-fibonacci+version: 1.69+category: Number Theory+synopsis: Fibonacci numbers+license: MIT+license-file: LICENSE+cabal-version: >= 1.8.0.2+build-type: Simple+author: Joe Leslie-Hurd <joe@gilith.com>+maintainer: Joe Leslie-Hurd <joe@gilith.com>+description:+  Fibonacci numbers - this package was automatically generated from the+  OpenTheory package natural-fibonacci-1.69++library+  build-depends:+    base >= 4.0 && < 5.0,+    QuickCheck >= 2.4.0.1 && < 3.0,+    opentheory-primitive >= 1.6 && < 2.0,+    opentheory >= 1.195 && < 1.201,+    opentheory-stream >= 1.46 && < 1.47+  hs-source-dirs: src+  ghc-options: -Wall+  exposed-modules:+    OpenTheory.Natural.Fibonacci++test-suite opentheory-fibonacci-test+  type: exitcode-stdio-1.0+  build-depends:+    base >= 4.0 && < 5.0,+    QuickCheck >= 2.4.0.1 && < 3.0,+    opentheory-primitive >= 1.6 && < 2.0,+    opentheory >= 1.195 && < 1.201,+    opentheory-stream >= 1.46 && < 1.47+  hs-source-dirs: src+  ghc-options: -Wall+  main-is: Test.hs

+ src/OpenTheory/Natural/Fibonacci.hs view

@@ -0,0 +1,50 @@+{- |+module: $Header$+description: Fibonacci numbers+license: MIT++maintainer: Joe Leslie-Hurd <joe@gilith.com>+stability: provisional+portability: portable+-}++module OpenTheory.Natural.Fibonacci+where++import qualified Data.List as List+import qualified OpenTheory.Primitive.Natural as Natural+import qualified OpenTheory.Stream as Stream++fibonaccis :: [Natural.Natural]+fibonaccis = Stream.unfold (\(p, f) -> (p, (f, p + f))) (0, 1)++decode :: [Bool] -> Natural.Natural+decode =+  dest 1 0+  where+  {-dest ::+        Natural.Natural -> Natural.Natural -> [Bool] -> Natural.Natural-}+    dest _ _ [] = 0+    dest f p (h : t) =+      let s = f + p in let n = dest s f t in if h then s + n else n++encode :: Natural.Natural -> [Bool]+encode =+  \n -> find n 1 0+  where+  {-find ::+        Natural.Natural -> Natural.Natural -> Natural.Natural -> [Bool]-}+    find n f p = let s = f + p in if n < s then mk [] n f p else find n s f++  {-mk ::+        [Bool] -> Natural.Natural -> Natural.Natural -> Natural.Natural ->+          [Bool]-}+    mk l n f p =+      if p == 0 then l+      else if f <= n then mk (True : l) (n - f) p (f - p)+      else mk (False : l) n p (f - p)++zeckendorf :: [Bool] -> Bool+zeckendorf [] = True+zeckendorf (h : t) =+  if List.null t then h else not (h && head t) && zeckendorf t

+ src/Test.hs view

@@ -0,0 +1,37 @@+{- |+module: Main+description: Fibonacci numbers - testing+license: MIT++maintainer: Joe Leslie-Hurd <joe@gilith.com>+stability: provisional+portability: portable+-}+module Main+  ( main )+where++import qualified OpenTheory.Natural.Fibonacci as Fibonacci+import qualified OpenTheory.Primitive.Natural as Natural+import qualified OpenTheory.Stream as Stream+import OpenTheory.Primitive.Test++proposition0 :: Natural.Natural -> Bool+proposition0 n = Fibonacci.zeckendorf (Fibonacci.encode n)++proposition1 :: Natural.Natural -> Bool+proposition1 n = Fibonacci.decode (Fibonacci.encode n) == n++proposition2 :: Natural.Natural -> Natural.Natural -> Bool+proposition2 j k =+  Stream.nth Fibonacci.fibonaccis (j + (k + 1)) ==+  Stream.nth Fibonacci.fibonaccis j * Stream.nth Fibonacci.fibonaccis k ++  Stream.nth Fibonacci.fibonaccis (j + 1) *+  Stream.nth Fibonacci.fibonaccis (k + 1)++main :: IO ()+main =+    do check "Proposition 0:\n  !n. zeckendorf (encode n)\n  " proposition0+       check "Proposition 1:\n  !n. decode (encode n) = n\n  " proposition1+       check "Proposition 2:\n  !j k.\n    nth all (j + (k + 1)) =\n    nth all j * nth all k + nth all (j + 1) * nth all (k + 1)\n  " proposition2+       return ()