peano 0.1.0.1 → 0.1.0.2

raw patch · 7 files changed

+163/−30 lines, 7 filesdep +peanodep +tasty-benchdep ~basesetup-changednew-uploaderPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

Dependencies added: peano, tasty-bench

Dependency ranges changed: base

API changes (from Hackage documentation)

Files

• CHANGELOG.md +18/−0
• Data/Peano.hs +27/−18
• LICENSE +26/−3
• README.md +28/−0
• Setup.hs +0/−2
• bench/Main.hs +18/−0
• peano.cabal +46/−7

@@ -0,0 +1,18 @@+0.1.0.2+-------++_Andreas Abel, 2023-10-23_++* Added benchmark for "`genericLength _ >=`".+* Changed license to BSD 3-clause.+* Tested with GHC 8.0 - 9.8.1.++0.1.0.1+-------++_Matthew Farkas Dyck, 2015-03-27_++0.1.0.0+-------++_Matthew Farkas Dyck, 2015-03-27_

@@ -1,17 +1,21 @@-module Data.Peano (Peano (..), infinity) where+-- | See 'Peano'. -import Data.Data-import Data.Function (on)-import Data.Ix (Ix (..))-import Data.Typeable+module Data.Peano ( Peano (Zero, Succ), infinity ) where -data Peano = Zero | Succ Peano deriving (Eq, Ord, Read, Show, Typeable, Data)+import Data.Data       ( Data, Typeable )+import Data.Ix         ( Ix( index, inRange, range, rangeSize ) ) +-- | The natural numbers in (lazy) unary notation.+data Peano+  = Zero+  | Succ Peano+  deriving (Eq, Ord, Typeable, Data, Read, Show)+ instance Enum Peano where     succ = Succ      pred (Succ n) = n-    pred Zero = error "pred Zero"+    pred Zero     = error "Data.Peano.pred Zero"      toEnum   = fromInteger . toEnum @@ -22,8 +26,8 @@     maxBound = infinity  instance Ix Peano where-    range = uncurry enumFromTo-    index (l, u) n = fromEnum (n - l)+    range            = uncurry enumFromTo+    index (l, _) n   = fromEnum (n - l)     inRange (l, u) n = l <= n && u >= n     rangeSize (l, u) = fromEnum (Succ u - l) @@ -33,8 +37,9 @@      m      - Zero   = m     Succ m - Succ n = m - n+    Zero   - _      = error "Data.Peano.(-): underflow (negative)" -    Zero   * n = Zero+    Zero   * _ = Zero     Succ m * n = n + m * n      abs = id@@ -42,23 +47,27 @@     signum Zero = Zero     signum _    = Succ Zero -    fromInteger n | n <  0 = error "fromInteger n | n < 0"-                  | n == 0 = Zero-                  | n >  0 = Succ (fromInteger (n - 1))+    fromInteger n =+      case compare n 0 of+        LT -> error "fromInteger n | n < 0"+        EQ -> Zero+        GT -> Succ (fromInteger (n - 1))  instance Real Peano where     toRational = toRational . toInteger  instance Integral Peano where-    toInteger Zero = 0+    toInteger Zero     = 0     toInteger (Succ n) = toInteger n + 1 -    Zero `quotRem` Zero   = error "0/0"-    m    `quotRem` n      = case compare m n-                            of LT -> (Zero, m)-                               _  -> let (q, r) = quotRem (m - n) n in (Succ q, r)+    Zero `quotRem` Zero   = error "Data.Peano.quotRem: zero divided by zero"+    m    `quotRem` n      =+      case compare m n of+        LT -> (Zero, m)+        _  -> let (q, r) = quotRem (m - n) n in (Succ q, r)      divMod = quotRem +-- | The infinite number (ω). infinity :: Peano infinity = Succ infinity

@@ -1,5 +1,28 @@-© Unix year 45 (Strake = M Farkas-Dyck)+Copyright (c) 2017, M Farkas-Dyck -Leave to use, copy, modify, and distribute this work for any purpose is hereby granted if the above copyright notice and this license are included.+Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are met: -THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.+    * Redistributions of source code must retain the above copyright+      notice, this list of conditions and the following disclaimer.++    * Redistributions in binary form must reproduce the above+      copyright notice, this list of conditions and the following+      disclaimer in the documentation and/or other materials provided+      with the distribution.++    * Neither the name of M Farkas-Dyck nor the names of other+      contributors may be used to endorse or promote products derived+      from this software without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

@@ -0,0 +1,28 @@+peano - Lazy unary natural numbers+==================================++This package provides natural numbers in unary notation+```haskell+data Peano+  = Zero+  | Succ Peano+```+implementing `Num`, `Ord` etc.++Purpose+-------++One application is to check whether the length of a (potentially long) list is greater than a (small) number.++E.g., without optimization (`-O 0`),+```haskell+genericLength (replicate (10 ^ 6) True) >= (5 :: Peano)+```+outperforms the same test for `5 :: Int` by a factor of 10⁵, see [benchmark](bench/Main.hs):+```+  length+    Peano: OK+      450  ns ±  45 ns+    Int:   OK+      136  ms ± 4.1 ms+```

@@ -1,2 +0,0 @@-import Distribution.Simple-main = defaultMain

@@ -0,0 +1,18 @@+import Data.Peano ( Peano )+import Data.List  ( genericLength )++import Test.Tasty.Bench ( bench, bgroup, defaultMain, nf )++main :: IO ()+main = defaultMain+  [ bgroup "length"+    [ bench "Peano" $ nf (bench_length $ 10 ^ 6) (5 :: Peano)+    , bench "Int"   $ nf (bench_length $ 10 ^ 6) (5 :: Int)+    ]+  ]++bench_length :: (Enum a, Num a, Ord a) => Int -> a -> Bool+bench_length n m =+  (genericLength (replicate n True) >= m)+  ==+  (n >= fromEnum m)

@@ -1,15 +1,54 @@+cabal-version:       1.18 name:                peano-version:             0.1.0.1+version:             0.1.0.2 synopsis:            Peano numbers-license:             OtherLicense+description:         Lazy unary natural numbers.+license:             BSD3 license-file:        LICENSE-author:              M Farkas-Dyck-maintainer:          strake888@gmail.com+author:              M Farkas-Dyck, Andreas Abel+maintainer:          Andreas Abel category:            Data, Math build-type:          Simple-cabal-version:       >=1.9.2 +tested-with:+  GHC == 9.8.1+  GHC == 9.6.3+  GHC == 9.4.7+  GHC == 9.2.8+  GHC == 9.0.2+  GHC == 8.10.7+  GHC == 8.8.4+  GHC == 8.6.5+  GHC == 8.4.4+  GHC == 8.2.2+  GHC == 8.0.2++extra-doc-files:+  CHANGELOG.md+  README.md+ library   exposed-modules:     Data.Peano-  extensions:          DeriveDataTypeable-  build-depends:       base >=4.7 && <4.9+  default-language:    Haskell2010+  default-extensions:  DeriveDataTypeable+  build-depends:       base >= 4.9 && < 5+  ghc-options:+    -Wall+    -Wcompat++benchmark bench+  type:                exitcode-stdio-1.0+  hs-source-dirs:      bench+  main-is:             Main.hs+  default-language:    Haskell2010+  build-depends:+     base+   , peano+   , tasty-bench+  -- Turn optimization off for the benchmark so that @length . replicate@ is not fused.+  ghc-options:+    -O0++source-repository head+  type:     git+  location: https://github.com/andreasabel/peano.hs