quadratic-irrational 0.0.5 → 0.0.6
raw patch · 12 files changed
+206/−107 lines, 12 filesdep ~arithmoidep ~basedep ~containersnew-uploader
Dependency ranges changed: arithmoi, base, containers, mtl, numbers, tasty, tasty-quickcheck, transformers
Files
- .gitignore +3/−0
- .travis.yml +114/−1
- ChangeLog.md +4/−0
- README.md +1/−1
- quadratic-irrational.cabal +11/−11
- src/Numeric/QuadraticIrrational.hs +24/−24
- src/Numeric/QuadraticIrrational/CyclicList.hs +14/−16
- src/Numeric/QuadraticIrrational/Internal/Lens.hs +8/−9
- tests/CyclicList.hs +10/−26
- tests/QuadraticIrrational.hs +8/−11
- tests/doctests.hs +8/−7
- tests/tasty.hs +1/−1
.gitignore view
@@ -1,3 +1,6 @@ .cabal-sandbox cabal.sandbox.config dist++# Haskell Tool Stack-related+.stack-work
.travis.yml view
@@ -1,1 +1,114 @@-language: haskell+language: c+sudo: false++cache:+ directories:+ - $HOME/.cabal/packages+ - $HOME/.cabal/store++before_cache:+ - rm -fv $HOME/.cabal/packages/hackage.haskell.org/build-reports.log+ # remove files that are regenerated by 'cabal update'+ - rm -fv $HOME/.cabal/packages/hackage.haskell.org/00-index.*+ - rm -fv $HOME/.cabal/packages/hackage.haskell.org/*.json+ - rm -fv $HOME/.cabal/packages/hackage.haskell.org/01-index.cache+ - rm -fv $HOME/.cabal/packages/hackage.haskell.org/01-index.tar+ - rm -fv $HOME/.cabal/packages/hackage.haskell.org/01-index.tar.idx++ - rm -rfv $HOME/.cabal/packages/head.hackage++matrix:+ include:+ - compiler: "ghc-7.10.3"+ env: TEST=--disable-tests+ addons: {apt: {packages: [ghc-ppa-tools,cabal-install-head,ghc-7.10.3], sources: [hvr-ghc]}}+ - compiler: "ghc-8.0.2"+ addons: {apt: {packages: [ghc-ppa-tools,cabal-install-head,ghc-8.0.2], sources: [hvr-ghc]}}+ - compiler: "ghc-8.2.2"+ addons: {apt: {packages: [ghc-ppa-tools,cabal-install-head,ghc-8.2.2], sources: [hvr-ghc]}}+ - compiler: "ghc-8.4.3"+ addons: {apt: {packages: [ghc-ppa-tools,cabal-install-head,ghc-8.4.3], sources: [hvr-ghc]}}+ - compiler: "ghc-8.6.1"+ env: GHCHEAD=true+ addons: {apt: {packages: [ghc-ppa-tools,cabal-install-head,ghc-8.6.1], sources: [hvr-ghc]}}+ - compiler: "ghc-head"+ env: GHCHEAD=true+ addons: {apt: {packages: [ghc-ppa-tools,cabal-install-head,ghc-head], sources: [hvr-ghc]}}++ allow_failures:+ - compiler: "ghc-head"++before_install:+ - HC=${CC}+ - HCPKG=${HC/ghc/ghc-pkg}+ - unset CC+ - ROOTDIR=$(pwd)+ - mkdir -p $HOME/.local/bin+ - "PATH=/opt/ghc/bin:/opt/ghc-ppa-tools/bin:$HOME/local/bin:$PATH"+ - HCNUMVER=$(( $(${HC} --numeric-version|sed -E 's/([0-9]+)\.([0-9]+)\.([0-9]+).*/\1 * 10000 + \2 * 100 + \3/') ))+ - echo $HCNUMVER++install:+ - cabal --version+ - echo "$(${HC} --version) [$(${HC} --print-project-git-commit-id 2> /dev/null || echo '?')]"+ - BENCH=${BENCH---enable-benchmarks}+ - TEST=${TEST---enable-tests}+ - HADDOCK=${HADDOCK-true}+ - INSTALLED=${INSTALLED-true}+ - GHCHEAD=${GHCHEAD-false}+ - travis_retry cabal update -v+ - "sed -i.bak 's/^jobs:/-- jobs:/' ${HOME}/.cabal/config"+ - rm -fv cabal.project cabal.project.local+ # Overlay Hackage Package Index for GHC HEAD: https://github.com/hvr/head.hackage+ - |+ if $GHCHEAD; then+ sed -i.bak 's/-- allow-newer:.*/allow-newer: *:base, *:template-haskell, *:ghc, *:Cabal, *:stm/' ${HOME}/.cabal/config++ echo 'repository head.hackage' >> ${HOME}/.cabal/config+ echo ' url: http://head.hackage.haskell.org/' >> ${HOME}/.cabal/config+ echo ' secure: True' >> ${HOME}/.cabal/config+ echo ' root-keys: 07c59cb65787dedfaef5bd5f987ceb5f7e5ebf88b904bbd4c5cbdeb2ff71b740' >> ${HOME}/.cabal/config+ echo ' 2e8555dde16ebd8df076f1a8ef13b8f14c66bad8eafefd7d9e37d0ed711821fb' >> ${HOME}/.cabal/config+ echo ' 8f79fd2389ab2967354407ec852cbe73f2e8635793ac446d09461ffb99527f6e' >> ${HOME}/.cabal/config+ echo ' key-threshold: 3' >> ${HOME}/.cabal.config++ cabal new-update head.hackage -v+ fi+ - grep -Ev -- '^\s*--' ${HOME}/.cabal/config | grep -Ev '^\s*$'+ - "printf 'packages: \".\"\\n' > cabal.project"+ - cat cabal.project+ - if [ -f "./configure.ac" ]; then+ (cd "." && autoreconf -i);+ fi+ - rm -f cabal.project.freeze+ - cabal new-build -w ${HC} ${TEST} ${BENCH} --project-file="cabal.project" --dep -j2 all+ - cabal new-build -w ${HC} --disable-tests --disable-benchmarks --project-file="cabal.project" --dep -j2 all+ - rm -rf "."/.ghc.environment.* "."/dist+ - DISTDIR=$(mktemp -d /tmp/dist-test.XXXX)++# Here starts the actual work to be performed for the package under test;+# any command which exits with a non-zero exit code causes the build to fail.+script:+ # test that source-distributions can be generated+ - (cd "." && cabal sdist)+ - mv "."/dist/quadratic-irrational-*.tar.gz ${DISTDIR}/+ - cd ${DISTDIR} || false+ - find . -maxdepth 1 -name '*.tar.gz' -exec tar -xvf '{}' \;+ - "printf 'packages: quadratic-irrational-*/*.cabal\\n' > cabal.project"+ - cat cabal.project+ # this builds all libraries and executables (without tests/benchmarks)+ - cabal new-build -w ${HC} --disable-tests --disable-benchmarks -f check-bounds all++ # Build with installed constraints for packages in global-db+ - if $INSTALLED; then echo cabal new-build -w ${HC} --disable-tests --disable-benchmarks $(${HCPKG} list --global --simple-output --names-only | sed 's/\([a-zA-Z0-9-]\{1,\}\) */--constraint="\1 installed" /g') all | sh; else echo "Not building with installed constraints"; fi++ # build & run tests, build benchmarks+ - cabal new-build -w ${HC} ${TEST} ${BENCH} all+ - if [ "x$TEST" = "x--enable-tests" ]; then cabal new-test -w ${HC} ${TEST} ${BENCH} -f check-bounds all; fi++ # haddock+ - rm -rf ./dist-newstyle+ - if $HADDOCK; then cabal new-haddock -w ${HC} ${TEST} ${BENCH} all; else echo "Skipping haddock generation";fi++# REGENDATA ["quadratic-irrational.cabal"]+# EOF
ChangeLog.md view
@@ -1,3 +1,7 @@+# 0.0.6 (2018-08-29)++* Support GHC up to 8.6.1.+ # 0.0.5 (2014-03-28) * Add an `Ord` instance.
README.md view
@@ -1,6 +1,6 @@ # `quadratic-irrational` -[](https://travis-ci.org/ion1/quadratic-irrational)+[](https://travis-ci.org/ion1/quadratic-irrational) [](https://hackage.haskell.org/package/quadratic-irrational) A library for exact computation with [quadratic irrationals][qi] with support for exact conversion from and to [(potentially periodic) simple continued
quadratic-irrational.cabal view
@@ -1,10 +1,10 @@ name: quadratic-irrational category: Math, Algorithms, Data-version: 0.0.5+version: 0.0.6 license: MIT license-file: LICENSE author: Johan Kiviniemi <devel@johan.kiviniemi.name>-maintainer: Johan Kiviniemi <devel@johan.kiviniemi.name>+maintainer: Andrew Lelechenko andrew dot lelechenko at gmail dot com stability: provisional homepage: https://github.com/ion1/quadratic-irrational bug-reports: https://github.com/ion1/quadratic-irrational/issues@@ -51,7 +51,7 @@ > 3.5 = [3; 2] > (1+√5)/2 = [1; 1, 1, 1, …] > √2 = [1; 2, 2, 2, …]-tested-with: GHC == 7.6.3+tested-with: GHC==7.10.3, GHC==8.0.2, GHC==8.2.2, GHC==8.4.3, GHC==8.6.1 build-type: Simple cabal-version: >= 1.10@@ -70,11 +70,11 @@ , Numeric.QuadraticIrrational.CyclicList , Numeric.QuadraticIrrational.Internal.Lens hs-source-dirs: src- build-depends: base >= 4.6 && < 4.8- , arithmoi == 0.4.*- , containers == 0.5.*- , mtl == 2.1.*- , transformers == 0.3.*+ build-depends: base >= 4.8 && < 5+ , arithmoi >= 0.4+ , containers >= 0.5 && < 0.7+ , mtl >= 2.1 && < 2.3+ , transformers >= 0.3 && < 0.6 default-language: Haskell2010 ghc-options: -Wall -O2 -funbox-strict-fields @@ -86,10 +86,10 @@ hs-source-dirs: tests build-depends: base , quadratic-irrational- , numbers == 3000.*+ , numbers >= 3000.0 && < 3000.3 , QuickCheck >= 2.7 && < 3- , tasty == 0.8.*- , tasty-quickcheck == 0.8.*+ , tasty >= 0.8 && < 1.2+ , tasty-quickcheck >= 0.8 && < 0.11 default-language: Haskell2010 ghc-options: -Wall -O2 -funbox-strict-fields
src/Numeric/QuadraticIrrational.hs view
@@ -1,4 +1,5 @@-{-# LANGUAGE ViewPatterns #-}+{-# LANGUAGE FlexibleContexts #-}+{-# LANGUAGE ViewPatterns #-} -- | -- Module : Numeric.QuadraticIrrational@@ -7,7 +8,7 @@ -- License : MIT -- Maintainer : Johan Kiviniemi <devel@johan.kiviniemi.name> -- Stability : provisional--- Portability : ViewPatterns+-- Portability : FlexibleContexts, ViewPatterns -- -- A library for exact computation with -- <http://en.wikipedia.org/wiki/Quadratic_irrational quadratic irrationals>@@ -68,16 +69,16 @@ , module Numeric.QuadraticIrrational.CyclicList ) where -import Control.Applicative-import Control.Monad.State-import qualified Data.Foldable as F-import Data.List-import Data.Maybe-import Data.Ratio-import qualified Data.Set as Set-import Math.NumberTheory.Powers.Squares-import Math.NumberTheory.Primes.Factorisation-import Text.Read+import Control.Monad.State (evalState, gets, modify)+import Data.Foldable (toList)+import Data.List (foldl')+import Data.Maybe (fromMaybe)+import Data.Ratio ((%), denominator, numerator)+import qualified Data.Set as Set (empty, insert, member)+import Math.NumberTheory.Powers.Squares (integerSquareRoot)+import Math.NumberTheory.Primes.Factorisation (factorise)+import Text.Read (Lexeme (Ident), Read (readListPrec, readPrec),+ lexP, parens, prec, readListPrecDefault, step) import Numeric.QuadraticIrrational.CyclicList import Numeric.QuadraticIrrational.Internal.Lens@@ -652,21 +653,20 @@ -- -- @[2; 2] = 2 + 1\/2 = 5\/2@. ----- >>> continuedFractionToQI (2,NonCyc [2])+-- >>> continuedFractionToQI (2,CycList [2] []) -- qi 5 0 0 2 -- -- The golden ratio is @[1; 1, 1, …]@. ----- >>> showCReal 1000 (qiToFloat (continuedFractionToQI (1,Cyc [] 1 [])))+-- >>> showCReal 1000 (qiToFloat (continuedFractionToQI (1,CycList [] [1]))) -- "1.6180339887498948482045868343656381177203091798057628621354486227052604628189024497072072041893911374847540880753868917521266338622235369317931800607667263544333890865959395829056383226613199282902678806752087668925017116962070322210432162695486262963136144381497587012203408058879544547492461856953648644492410443207713449470495658467885098743394422125448770664780915884607499887124007652170575179788341662562494075890697040002812104276217711177780531531714101170466659914669798731761356006708748071013179523689427521948435305678300228785699782977834784587822891109762500302696156170025046433824377648610283831268330372429267526311653392473167111211588186385133162038400522216579128667529465490681131715993432359734949850904094762132229810172610705961164562990981629055520852479035240602017279974717534277759277862561943208275051312181562855122248093947123414517022373580577278616008688382952304592647878017889921990270776903895321968198615143780314997411069260886742962267575605231727775203536139362" ----- >>> continuedFractionToQI (0,Cyc [83,78,65,75,69] 32 [66,65,68,71,69,82])+-- >>> continuedFractionToQI (0,CycList [83,78,65,75,69] [32,66,65,68,71,69,82]) -- qi 987601513930253257378987883 1 14116473325908285531353005 81983584717737887813195873886 continuedFractionToQI :: (Integer, CycList Integer) -> QI continuedFractionToQI (i0_, is_) = qiAddI (go is_) i0_ where- go (NonCyc as) = goNonCyc as qiZero- go (Cyc as b bs) = goNonCyc as (goCyc (b:bs))+ go (CycList as bs) = goNonCyc as (if null bs then qiZero else goCyc bs) goNonCyc ((pos -> i):is) final = sudoQIRecip (qiAddI (goNonCyc is final) i) goNonCyc [] final = final@@ -709,15 +709,15 @@ -- @5\/2 = 2 + 1\/2 = [2; 2]@. -- -- >>> qiToContinuedFraction (qi 5 0 0 2)--- (2,NonCyc [2])+-- (2,CycList [2] []) -- -- The golden ratio is @(1 + √5)\/2@. We can compute the corresponding PCF. -- -- >>> qiToContinuedFraction (qi 1 1 5 2)--- (1,Cyc [] 1 [])+-- (1,CycList [] [1]) -- -- >>> qiToContinuedFraction (qi 987601513930253257378987883 1 14116473325908285531353005 81983584717737887813195873886)--- (0,Cyc [83,78,65,75,69] 32 [66,65,68,71,69,82])+-- (0,CycList [83,78,65,75,69] [32,66,65,68,71,69,82]) qiToContinuedFraction :: QI -> (Integer, CycList Integer) qiToContinuedFraction num@@ -725,9 +725,9 @@ case break isLoopQI cfs of (preLoop, ~(i:postLoop)) -> let is = takeWhile (not . isLoopQI) postLoop- in (i0, Cyc (map snd preLoop) (snd i) (map snd is))+ in (i0, CycList (map snd preLoop) (map snd $ i : is)) | otherwise =- (i0, NonCyc (map snd cfs))+ (i0, CycList (map snd cfs) []) where (i0, cfs) = qiToContinuedFractionList num @@ -758,9 +758,9 @@ -- -- >>> [ continuedFractionApproximate n (1, repeat 1) | n <- [0,3..18] ] -- [1 % 1,5 % 3,21 % 13,89 % 55,377 % 233,1597 % 987,6765 % 4181]-continuedFractionApproximate :: F.Foldable f+continuedFractionApproximate :: Foldable f => Int -> (Integer, f Integer) -> Rational-continuedFractionApproximate n (i0, F.toList -> is) =+continuedFractionApproximate n (i0, toList -> is) = fromInteger i0 + foldr (\(pos -> i) r -> recip (fromInteger i + r)) 0 (take n is) where
src/Numeric/QuadraticIrrational/CyclicList.hs view
@@ -7,30 +7,28 @@ -- Stability : provisional -- Portability : portable +{-# LANGUAGE DeriveFunctor #-}+ module Numeric.QuadraticIrrational.CyclicList- ( CycList (..)+ ( CycList(..) ) where -import Data.Foldable-import Data.Monoid+import Data.Monoid ((<>)) -- | A container for a possibly cyclic list. ----- >>> toList (NonCyc "hello")+-- $setup+-- >>> import Data.Foldable (toList)+--+-- >>> toList (CycList "hello" "") -- "hello" ----- >>> take 70 (toList (Cyc "prefix " 'c' "ycle"))+-- >>> take 70 (toList (CycList "prefix " "cycle")) -- "prefix cyclecyclecyclecyclecyclecyclecyclecyclecyclecyclecyclecyclecyc"-data CycList a = NonCyc [a] -- ^ A non-cyclic list.- | Cyc [a] a [a]- -- ^ A non-cyclic list followed by the head of a cyclic list- -- followed by the tail of the cyclic list.- deriving (Eq, Ord, Read, Show)--instance Functor CycList where- fmap f (NonCyc as) = NonCyc (fmap f as)- fmap f (Cyc as b bs) = Cyc (fmap f as) (f b) (fmap f bs)+data CycList a = CycList [a] [a]+ deriving (Eq, Ord, Read, Show, Functor) instance Foldable CycList where- foldMap f (NonCyc as) = foldMap f as- foldMap f (Cyc as b bs) = foldMap f as <> foldMap f (cycle (b:bs))+ foldMap f (CycList as bs) = foldMap f as <> if null bs then mempty else cycleAppend (foldMap f bs)+ where+ cycleAppend x = x <> cycleAppend x
src/Numeric/QuadraticIrrational/Internal/Lens.hs view
@@ -1,4 +1,4 @@-{-# LANGUAGE Rank2Types #-}+{-# LANGUAGE RankNTypes #-} -- | -- Module : Numeric.QuadraticIrrational.Internal.Lens@@ -7,7 +7,7 @@ -- License : MIT -- Maintainer : Johan Kiviniemi <devel@johan.kiviniemi.name> -- Stability : provisional--- Portability : Rank2Types+-- Portability : RankNTypes -- -- A tiny implementation of some lens primitives. Please see -- <http://hackage.haskell.org/package/lens> for proper documentation.@@ -16,15 +16,14 @@ ( Lens, Traversal, Lens', Traversal', Getting, Setting , view, over, set ) where--import Control.Applicative-import Data.Functor.Identity+import Control.Applicative (Const (Const), getConst)+import Data.Functor.Identity (Identity (Identity), runIdentity) -type Lens s t a b = Functor f => (a -> f b) -> s -> f t-type Traversal s t a b = Applicative f => (a -> f b) -> s -> f t+type Lens s t a b = forall f. Functor f => (a -> f b) -> s -> f t+type Traversal s t a b = forall f. Applicative f => (a -> f b) -> s -> f t -type Lens' s a = Functor f => (a -> f a) -> s -> f s-type Traversal' s a = Applicative f => (a -> f a) -> s -> f s+type Lens' s a = forall f. Functor f => (a -> f a) -> s -> f s+type Traversal' s a = forall f. Applicative f => (a -> f a) -> s -> f s type Getting r s a = (a -> Const r a) -> s -> Const r s type Setting s t a b = (a -> Identity b) -> s -> Identity t
tests/CyclicList.hs view
@@ -2,40 +2,24 @@ module CyclicList (tests) where -import Control.Applicative-import qualified Data.Foldable as F-import Test.Tasty-import Test.Tasty.QuickCheck+import Data.Foldable (toList)+import Test.Tasty (TestTree, testGroup)+import Test.Tasty.QuickCheck (Arbitrary (arbitrary, shrink), (===),+ testProperty) import Numeric.QuadraticIrrational.CyclicList instance Arbitrary a => Arbitrary (CycList a) where- arbitrary = oneof [ NonCyc <$> arbitrary- , Cyc <$> arbitrary <*> arbitrary <*> arbitrary- ]-- shrink (NonCyc as) = [ NonCyc as' | as' <- shrink as ]- shrink (Cyc as b bs) = [ Cyc as' b bs | as' <- shrink as ]- ++ [ Cyc as b' bs | b' <- shrink b ]- ++ [ Cyc as b bs' | bs' <- shrink bs ]+ arbitrary = CycList <$> arbitrary <*> arbitrary+ shrink (CycList as bs) = (CycList <$> pure as <*> shrink bs)+ ++ (CycList <$> shrink as <*> pure bs) tests :: TestTree tests = testGroup "CyclicList"- [ testProperty "fmap" . withListEquiv $ \asC asL ->- initEq' (fmap (*10) asC) (fmap (*10) asL)- , testProperty "toList" . withListEquiv $ \asC asL ->- take 1000 (F.toList asC) === take 1000 asL+ [ testProperty "toList" . withListEquiv $ \asC asL ->+ take 1000 (toList asC) === take 1000 asL ] withListEquiv :: (CycList Integer -> [Integer] -> b) -> CycList Integer -> b-withListEquiv f cl@(NonCyc as) = f cl as-withListEquiv f cl@(Cyc as b bs) = f cl (as ++ cycle (b:bs))--initEq :: Eq a => CycList a -> [a] -> Bool-initEq (NonCyc as) cs = take 1000 cs == take 1000 as-initEq (Cyc as b bs) cs = take 1000 cs == take 1000 (as ++ cycle (b:bs))--initEq' :: (Eq a, Show a) => CycList a -> [a] -> Property-initEq' (NonCyc as) cs = take 1000 cs === take 1000 as-initEq' (Cyc as b bs) cs = take 1000 cs === take 1000 (as ++ cycle (b:bs))+withListEquiv f cl@(CycList as bs) = f cl (as ++ if null bs then [] else cycle bs)
tests/QuadraticIrrational.hs view
@@ -1,13 +1,13 @@-{-# LANGUAGE ViewPatterns #-}- {-# OPTIONS_GHC -fno-warn-orphans #-}+{-# LANGUAGE ViewPatterns #-} module QuadraticIrrational (tests) where -import Control.Applicative-import Data.Number.CReal-import Test.Tasty-import Test.Tasty.QuickCheck+import Data.Number.CReal (CReal)+import Test.Tasty (TestTree, testGroup)+import Test.Tasty.QuickCheck (Arbitrary (arbitrary, shrink),+ NonNegative (NonNegative), NonZero (NonZero), Property, Testable, (===),+ (==>), conjoin, counterexample, testProperty) import Numeric.QuadraticIrrational import Numeric.QuadraticIrrational.Internal.Lens@@ -160,12 +160,9 @@ ] , testGroup "Continued fractions" [ testProperty "qiToContinuedFraction/continuedFractionToQI" $ \n ->- let cf = qiToContinuedFraction n- len = case cf of- (_, NonCyc _) -> 0- (_, Cyc _ _ xs) -> length xs+ let cf@(_, CycList _ xs) = qiToContinuedFraction n -- Limit the length of the periodic part for speed.- in (len <= 100) ==>+ in (length xs <= 100) ==> n === continuedFractionToQI cf , testProperty "continuedFractionApproximate" $ \n ->
tests/doctests.hs view
@@ -2,13 +2,14 @@ module Main (main) where -import Control.Applicative-import Control.Monad-import Control.Monad.List-import Data.List-import System.Directory-import System.FilePath-import Test.DocTest+import Control.Applicative (empty)+import Control.Monad (guard)+import Control.Monad.List (ListT (ListT), liftIO, runListT)+import Data.List (isSuffixOf)+import System.Directory (doesDirectoryExist, doesFileExist,+ getDirectoryContents)+import System.FilePath ((</>))+import Test.DocTest (doctest) main :: IO () main = do
tests/tasty.hs view
@@ -1,6 +1,6 @@ module Main (main) where -import Test.Tasty+import Test.Tasty (TestTree, defaultMain, testGroup) import qualified CyclicList import qualified QuadraticIrrational