-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | An implementation of quadratic irrationals
--   
--   A library for exact computation with <a>quadratic irrationals</a> with
--   support for exact conversion from and to <a>(potentially periodic)
--   simple continued fractions</a>.
--   
--   A quadratic irrational is a number that can be expressed in the form
--   
--   <pre>
--   (a + b √c) / d
--   </pre>
--   
--   where <tt>a</tt>, <tt>b</tt> and <tt>d</tt> are integers and
--   <tt>c</tt> is a square-free natural number.
--   
--   Some examples of such numbers are
--   
--   <ul>
--   <li><tt>7/2</tt>,</li>
--   <li><tt>√2</tt>,</li>
--   <li><tt>(1 + √5)/2</tt> (<a>the golden ratio</a>),</li>
--   <li>solutions to quadratic equations with rational constants – the
--   <a>quadratic formula</a> has a familiar shape.</li>
--   </ul>
--   
--   A simple continued fraction is a number expressed in the form
--   
--   <pre>
--   a + 1/(b + 1/(c + 1/(d + 1/(e + …))))
--   </pre>
--   
--   or alternatively written as
--   
--   <pre>
--   [a; b, c, d, e, …]
--   </pre>
--   
--   where <tt>a</tt> is an integer and <tt>b</tt>, <tt>c</tt>, <tt>d</tt>,
--   <tt>e</tt>, … are positive integers.
--   
--   Every finite SCF represents a rational number and every infinite,
--   periodic SCF represents a quadratic irrational.
--   
--   <pre>
--   3.5      = [3; 2]
--   (1+√5)/2 = [1; 1, 1, 1, …]
--   √2       = [1; 2, 2, 2, …]
--   </pre>
@package quadratic-irrational
@version 0.0.6


module Numeric.QuadraticIrrational.CyclicList
data CycList a
CycList :: [a] -> [a] -> CycList a
instance GHC.Base.Functor Numeric.QuadraticIrrational.CyclicList.CycList
instance GHC.Show.Show a => GHC.Show.Show (Numeric.QuadraticIrrational.CyclicList.CycList a)
instance GHC.Read.Read a => GHC.Read.Read (Numeric.QuadraticIrrational.CyclicList.CycList a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Numeric.QuadraticIrrational.CyclicList.CycList a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Numeric.QuadraticIrrational.CyclicList.CycList a)
instance Data.Foldable.Foldable Numeric.QuadraticIrrational.CyclicList.CycList


-- | A tiny implementation of some lens primitives. Please see
--   <a>http://hackage.haskell.org/package/lens</a> for proper
--   documentation.
module Numeric.QuadraticIrrational.Internal.Lens
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 = 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
view :: Getting a s a -> s -> a
over :: Setting s t a b -> (a -> b) -> s -> t
set :: Setting s t a b -> b -> s -> t


-- | A library for exact computation with <a>quadratic irrationals</a> with
--   support for exact conversion from and to <a>(potentially periodic)
--   simple continued fractions</a>.
--   
--   A quadratic irrational is a number that can be expressed in the form
--   
--   <pre>
--   (a + b √c) / d
--   </pre>
--   
--   where <tt>a</tt>, <tt>b</tt> and <tt>d</tt> are integers and
--   <tt>c</tt> is a square-free natural number.
--   
--   Some examples of such numbers are
--   
--   <ul>
--   <li><tt>7/2</tt>,</li>
--   <li><tt>√2</tt>,</li>
--   <li><tt>(1 + √5)/2</tt> (<a>the golden ratio</a>),</li>
--   <li>solutions to quadratic equations with rational constants – the
--   <a>quadratic formula</a> has a familiar shape.</li>
--   </ul>
--   
--   A simple continued fraction is a number expressed in the form
--   
--   <pre>
--   a + 1/(b + 1/(c + 1/(d + 1/(e + …))))
--   </pre>
--   
--   or alternatively written as
--   
--   <pre>
--   [a; b, c, d, e, …]
--   </pre>
--   
--   where <tt>a</tt> is an integer and <tt>b</tt>, <tt>c</tt>, <tt>d</tt>,
--   <tt>e</tt>, … are positive integers.
--   
--   Every finite SCF represents a rational number and every infinite,
--   periodic SCF represents a quadratic irrational.
--   
--   <pre>
--   3.5      = [3; 2]
--   (1+√5)/2 = [1; 1, 1, 1, …]
--   √2       = [1; 2, 2, 2, …]
--   </pre>
module Numeric.QuadraticIrrational

-- | <pre>
--   (a + b √c) / d
--   </pre>
data QI

-- | Given <tt>a</tt>, <tt>b</tt>, <tt>c</tt> and <tt>d</tt> such that
--   <tt>n = (a + b √c)/d</tt>, constuct a <a>QI</a> corresponding to
--   <tt>n</tt>.
--   
--   <pre>
--   &gt;&gt;&gt; qi 3 4 5 6
--   qi 3 4 5 6
--   </pre>
--   
--   The fractions are reduced:
--   
--   <pre>
--   &gt;&gt;&gt; qi 30 40 5 60
--   qi 3 4 5 6
--   </pre>
--   
--   If <tt>b = 0</tt> then <tt>c</tt> is zeroed and vice versa:
--   
--   <pre>
--   &gt;&gt;&gt; qi 3 0 42 1
--   qi 3 0 0 1
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; qi 3 42 0 1
--   qi 3 0 0 1
--   </pre>
--   
--   The <tt>b √c</tt> term is simplified:
--   
--   <pre>
--   &gt;&gt;&gt; qi 0 1 (5*5*6) 1
--   qi 0 5 6 1
--   </pre>
--   
--   If <tt>c = 1</tt> (after simplification) then <tt>b</tt> is moved to
--   <tt>a</tt>:
--   
--   <pre>
--   &gt;&gt;&gt; qi 1 5 (2*2) 1
--   qi 11 0 0 1
--   </pre>
qi :: Integer -> Integer -> Integer -> Integer -> QI

-- | Given <tt>a</tt>, <tt>b</tt> and <tt>c</tt> such that <tt>n = a + b
--   √c</tt>, constuct a <a>QI</a> corresponding to <tt>n</tt>.
--   
--   <pre>
--   &gt;&gt;&gt; qi' 0.5 0.7 2
--   qi 5 7 2 10
--   </pre>
qi' :: Rational -> Rational -> Integer -> QI

-- | Given <tt>n</tt> and <tt>f</tt> such that <tt>n = (a + b √c)/d</tt>,
--   run <tt>f a b c d</tt>.
--   
--   <pre>
--   &gt;&gt;&gt; runQI (qi 3 4 5 6) (\a b c d -&gt; (a,b,c,d))
--   (3,4,5,6)
--   </pre>
runQI :: QI -> (Integer -> Integer -> Integer -> Integer -> a) -> a

-- | Given <tt>n</tt> and <tt>f</tt> such that <tt>n = a + b √c</tt>, run
--   <tt>f a b c</tt>.
--   
--   <pre>
--   &gt;&gt;&gt; runQI' (qi' 0.5 0.7 2) (\a b c -&gt; (a, b, c))
--   (1 % 2,7 % 10,2)
--   </pre>
runQI' :: QI -> (Rational -> Rational -> Integer -> a) -> a

-- | Given <tt>n</tt> such that <tt>n = (a + b √c)/d</tt>, return <tt>(a,
--   b, c, d)</tt>.
--   
--   <pre>
--   &gt;&gt;&gt; unQI (qi 3 4 5 6)
--   (3,4,5,6)
--   </pre>
unQI :: QI -> (Integer, Integer, Integer, Integer)

-- | Given <tt>n</tt> such that <tt>n = a + b √c</tt>, return <tt>(a, b,
--   c)</tt>.
--   
--   <pre>
--   &gt;&gt;&gt; unQI' (qi' 0.5 0.7 2)
--   (1 % 2,7 % 10,2)
--   </pre>
unQI' :: QI -> (Rational, Rational, Integer)

-- | Given a <a>QI</a> corresponding to <tt>n = (a + b √c)/d</tt>, access
--   <tt>(a, b, c, d)</tt>.
--   
--   <pre>
--   &gt;&gt;&gt; view _qi (qi 3 4 5 6)
--   (3,4,5,6)
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; over _qi (\(a,b,c,d) -&gt; (a+10, b+10, c+10, d+10)) (qi 3 4 5 6)
--   qi 13 14 15 16
--   </pre>
_qi :: Lens' QI (Integer, Integer, Integer, Integer)

-- | Given a <a>QI</a> corresponding to <tt>n = a + b √c</tt>, access
--   <tt>(a, b, c)</tt>.
--   
--   <pre>
--   &gt;&gt;&gt; view _qi' (qi' 0.5 0.7 2)
--   (1 % 2,7 % 10,2)
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; over _qi' (\(a,b,c) -&gt; (a/5, b/6, c*3)) (qi 3 4 5 6)
--   qi 9 10 15 90
--   </pre>
_qi' :: Lens' QI (Rational, Rational, Integer)

-- | Given a <a>QI</a> corresponding to <tt>n = (a + b √c)/d</tt>, access
--   <tt>(a, b, d)</tt>. Avoids having to simplify <tt>b √c</tt> upon
--   reconstruction.
--   
--   <pre>
--   &gt;&gt;&gt; view _qiABD (qi 3 4 5 6)
--   (3,4,6)
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; over _qiABD (\(a,b,d) -&gt; (a+10, b+10, d+10)) (qi 3 4 5 6)
--   qi 13 14 5 16
--   </pre>
_qiABD :: Lens' QI (Integer, Integer, Integer)

-- | Given a <a>QI</a> corresponding to <tt>n = (a + b √c)/d</tt>, access
--   <tt>a</tt>. It is more efficient to use <a>_qi</a> or <a>_qiABD</a>
--   when modifying multiple terms at once.
--   
--   <pre>
--   &gt;&gt;&gt; view _qiA (qi 3 4 5 6)
--   3
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; over _qiA (+ 10) (qi 3 4 5 6)
--   qi 13 4 5 6
--   </pre>
_qiA :: Lens' QI Integer

-- | Given a <a>QI</a> corresponding to <tt>n = (a + b √c)/d</tt>, access
--   <tt>b</tt>. It is more efficient to use <a>_qi</a> or <a>_qiABD</a>
--   when modifying multiple terms at once.
--   
--   <pre>
--   &gt;&gt;&gt; view _qiB (qi 3 4 5 6)
--   4
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; over _qiB (+ 10) (qi 3 4 5 6)
--   qi 3 14 5 6
--   </pre>
_qiB :: Lens' QI Integer

-- | Given a <a>QI</a> corresponding to <tt>n = (a + b √c)/d</tt>, access
--   <tt>c</tt>. It is more efficient to use <a>_qi</a> or <a>_qiABD</a>
--   when modifying multiple terms at once.
--   
--   <pre>
--   &gt;&gt;&gt; view _qiC (qi 3 4 5 6)
--   5
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; over _qiC (+ 10) (qi 3 4 5 6)
--   qi 3 4 15 6
--   </pre>
_qiC :: Lens' QI Integer

-- | Given a <a>QI</a> corresponding to <tt>n = (a + b √c)/d</tt>, access
--   <tt>d</tt>. It is more efficient to use <a>_qi</a> or <a>_qiABD</a>
--   when modifying multiple terms at once.
--   
--   <pre>
--   &gt;&gt;&gt; view _qiD (qi 3 4 5 6)
--   6
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; over _qiD (+ 10) (qi 3 4 5 6)
--   qi 3 4 5 16
--   </pre>
_qiD :: Lens' QI Integer

-- | The constant zero.
--   
--   <pre>
--   &gt;&gt;&gt; qiZero
--   qi 0 0 0 1
--   </pre>
qiZero :: QI

-- | The constant one.
--   
--   <pre>
--   &gt;&gt;&gt; qiOne
--   qi 1 0 0 1
--   </pre>
qiOne :: QI

-- | Check if the value is zero.
--   
--   <pre>
--   &gt;&gt;&gt; map qiIsZero [qiZero, qiOne, qiSubR (qi 7 0 0 2) 3.5]
--   [True,False,True]
--   </pre>
qiIsZero :: QI -> Bool

-- | Convert a <a>QI</a> number into a <a>Floating</a> one.
--   
--   <pre>
--   &gt;&gt;&gt; qiToFloat (qi 3 4 5 6) == ((3 + 4 * sqrt 5)/6 :: Double)
--   True
--   </pre>
qiToFloat :: Floating a => QI -> a

-- | Add an <a>Integer</a> to a <a>QI</a>.
--   
--   <pre>
--   &gt;&gt;&gt; qi 3 4 5 6 `qiAddI` 1
--   qi 9 4 5 6
--   </pre>
qiAddI :: QI -> Integer -> QI

-- | Subtract an <a>Integer</a> from a <a>QI</a>.
--   
--   <pre>
--   &gt;&gt;&gt; qi 3 4 5 6 `qiSubI` 1
--   qi (-3) 4 5 6
--   </pre>
qiSubI :: QI -> Integer -> QI

-- | Multiply a <a>QI</a> by an <a>Integer</a>.
--   
--   <pre>
--   &gt;&gt;&gt; qi 3 4 5 6 `qiMulI` 2
--   qi 3 4 5 3
--   </pre>
qiMulI :: QI -> Integer -> QI

-- | Divice a <a>QI</a> by an <a>Integer</a>.
--   
--   <pre>
--   &gt;&gt;&gt; qi 3 4 5 6 `qiDivI` 2
--   qi 3 4 5 12
--   </pre>
qiDivI :: QI -> Integer -> QI

-- | Add a <a>Rational</a> to a <a>QI</a>.
--   
--   <pre>
--   &gt;&gt;&gt; qi 3 4 5 6 `qiAddR` 1.2
--   qi 51 20 5 30
--   </pre>
qiAddR :: QI -> Rational -> QI

-- | Subtract a <a>Rational</a> from a <a>QI</a>.
--   
--   <pre>
--   &gt;&gt;&gt; qi 3 4 5 6 `qiSubR` 1.2
--   qi (-21) 20 5 30
--   </pre>
qiSubR :: QI -> Rational -> QI

-- | Multiply a <a>QI</a> by a <a>Rational</a>.
--   
--   <pre>
--   &gt;&gt;&gt; qi 3 4 5 6 `qiMulR` 0.5
--   qi 3 4 5 12
--   </pre>
qiMulR :: QI -> Rational -> QI

-- | Divice a <a>QI</a> by a <a>Rational</a>.
--   
--   <pre>
--   &gt;&gt;&gt; qi 3 4 5 6 `qiDivR` 0.5
--   qi 3 4 5 3
--   </pre>
qiDivR :: QI -> Rational -> QI

-- | Negate a <a>QI</a>.
--   
--   <pre>
--   &gt;&gt;&gt; qiNegate (qi 3 4 5 6)
--   qi (-3) (-4) 5 6
--   </pre>
qiNegate :: QI -> QI

-- | Compute the reciprocal of a <a>QI</a>.
--   
--   <pre>
--   &gt;&gt;&gt; qiRecip (qi 5 0 0 2)
--   Just (qi 2 0 0 5)
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; qiRecip (qi 0 1 5 2)
--   Just (qi 0 2 5 5)
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; qiRecip qiZero
--   Nothing
--   </pre>
qiRecip :: QI -> Maybe QI

-- | Add two <a>QI</a>s if the square root terms are the same or zeros.
--   
--   <pre>
--   &gt;&gt;&gt; qi 3 4 5 6 `qiAdd` qiOne
--   Just (qi 9 4 5 6)
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; qi 3 4 5 6 `qiAdd` qi 3 4 5 6
--   Just (qi 3 4 5 3)
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; qi 0 1 5 1 `qiAdd` qi 0 1 6 1
--   Nothing
--   </pre>
qiAdd :: QI -> QI -> Maybe QI

-- | Subtract two <a>QI</a>s if the square root terms are the same or
--   zeros.
--   
--   <pre>
--   &gt;&gt;&gt; qi 3 4 5 6 `qiSub` qiOne
--   Just (qi (-3) 4 5 6)
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; qi 3 4 5 6 `qiSub` qi 3 4 5 6
--   Just (qi 0 0 0 1)
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; qi 0 1 5 1 `qiSub` qi 0 1 6 1
--   Nothing
--   </pre>
qiSub :: QI -> QI -> Maybe QI

-- | Multiply two <a>QI</a>s if the square root terms are the same or
--   zeros.
--   
--   <pre>
--   &gt;&gt;&gt; qi 3 4 5 6 `qiMul` qiZero
--   Just (qi 0 0 0 1)
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; qi 3 4 5 6 `qiMul` qiOne
--   Just (qi 3 4 5 6)
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; qi 3 4 5 6 `qiMul` qi 3 4 5 6
--   Just (qi 89 24 5 36)
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; qi 0 1 5 1 `qiMul` qi 0 1 6 1
--   Nothing
--   </pre>
qiMul :: QI -> QI -> Maybe QI

-- | Divide two <a>QI</a>s if the square root terms are the same or zeros.
--   
--   <pre>
--   &gt;&gt;&gt; qi 3 4 5 6 `qiDiv` qiZero
--   Nothing
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; qi 3 4 5 6 `qiDiv` qiOne
--   Just (qi 3 4 5 6)
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; qi 3 4 5 6 `qiDiv` qi 3 4 5 6
--   Just (qi 1 0 0 1)
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; qi 3 4 5 6 `qiDiv` qi 0 1 5 1
--   Just (qi 20 3 5 30)
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; qi 0 1 5 1 `qiDiv` qi 0 1 6 1
--   Nothing
--   </pre>
qiDiv :: QI -> QI -> Maybe QI

-- | Exponentiate a <a>QI</a> to an <a>Integer</a> power.
--   
--   <pre>
--   &gt;&gt;&gt; qi 3 4 5 6 `qiPow` 0
--   qi 1 0 0 1
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; qi 3 4 5 6 `qiPow` 1
--   qi 3 4 5 6
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; qi 3 4 5 6 `qiPow` 2
--   qi 89 24 5 36
--   </pre>
qiPow :: QI -> Integer -> QI

-- | Compute the floor of a <a>QI</a>.
--   
--   <pre>
--   &gt;&gt;&gt; qiFloor (qi 10 0 0 2)
--   5
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; qiFloor (qi 10 2 2 2)
--   6
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; qiFloor (qi 10 2 5 2)
--   7
--   </pre>
qiFloor :: QI -> Integer

-- | Convert a (possibly periodic) simple continued fraction to a
--   <a>QI</a>.
--   
--   <tt>[2; 2] = 2 + 1/2 = 5/2</tt>.
--   
--   <pre>
--   &gt;&gt;&gt; continuedFractionToQI (2,CycList [2] [])
--   qi 5 0 0 2
--   </pre>
--   
--   The golden ratio is <tt>[1; 1, 1, …]</tt>.
--   
--   <pre>
--   &gt;&gt;&gt; showCReal 1000 (qiToFloat (continuedFractionToQI (1,CycList [] [1])))
--   "1.6180339887498948482045868343656381177203091798057628621354486227052604628189024497072072041893911374847540880753868917521266338622235369317931800607667263544333890865959395829056383226613199282902678806752087668925017116962070322210432162695486262963136144381497587012203408058879544547492461856953648644492410443207713449470495658467885098743394422125448770664780915884607499887124007652170575179788341662562494075890697040002812104276217711177780531531714101170466659914669798731761356006708748071013179523689427521948435305678300228785699782977834784587822891109762500302696156170025046433824377648610283831268330372429267526311653392473167111211588186385133162038400522216579128667529465490681131715993432359734949850904094762132229810172610705961164562990981629055520852479035240602017279974717534277759277862561943208275051312181562855122248093947123414517022373580577278616008688382952304592647878017889921990270776903895321968198615143780314997411069260886742962267575605231727775203536139362"
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; continuedFractionToQI (0,CycList [83,78,65,75,69] [32,66,65,68,71,69,82])
--   qi 987601513930253257378987883 1 14116473325908285531353005 81983584717737887813195873886
--   </pre>
continuedFractionToQI :: (Integer, CycList Integer) -> QI

-- | Convert a <a>QI</a> into a (possibly periodic) simple continued
--   fraction.
--   
--   <tt>5/2 = 2 + 1/2 = [2; 2]</tt>.
--   
--   <pre>
--   &gt;&gt;&gt; qiToContinuedFraction (qi 5 0 0 2)
--   (2,CycList [2] [])
--   </pre>
--   
--   The golden ratio is <tt>(1 + √5)/2</tt>. We can compute the
--   corresponding PCF.
--   
--   <pre>
--   &gt;&gt;&gt; qiToContinuedFraction (qi 1 1 5 2)
--   (1,CycList [] [1])
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; qiToContinuedFraction (qi 987601513930253257378987883 1 14116473325908285531353005 81983584717737887813195873886)
--   (0,CycList [83,78,65,75,69] [32,66,65,68,71,69,82])
--   </pre>
qiToContinuedFraction :: QI -> (Integer, CycList Integer)

-- | Compute a rational partial evaluation of a simple continued fraction.
--   
--   Rational approximations that converge toward φ:
--   
--   <pre>
--   &gt;&gt;&gt; [ continuedFractionApproximate n (1, repeat 1) | n &lt;- [0,3..18] ]
--   [1 % 1,5 % 3,21 % 13,89 % 55,377 % 233,1597 % 987,6765 % 4181]
--   </pre>
continuedFractionApproximate :: Foldable f => Int -> (Integer, f Integer) -> Rational
instance GHC.Classes.Eq Numeric.QuadraticIrrational.QI
instance GHC.Show.Show Numeric.QuadraticIrrational.QI
instance GHC.Read.Read Numeric.QuadraticIrrational.QI
instance GHC.Classes.Ord Numeric.QuadraticIrrational.QI
