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


-- | A redefinition of the Prelude's Enum class in order to render it safe.
--   
--   A redefinition of the Prelude's Enum class in order to render it safe.
--   That is, the Haskell Language Report defines pred, succ, fromEnum, and
--   toEnum to be partial functions when the type is Bounded, but this is
--   unacceptable. We define a new type-class hierarchy for enumeration
--   which is safe and also generalizes to cover types which can only be
--   enumerated in one direction.
@package prelude-safeenum
@version 0.1.1.2


-- | A redefinition of the <a>Prelude</a>'s <a>Enum</a> class in order to
--   render it safe. That is, the Haskell Language Report defines
--   <a>pred</a>, <a>succ</a>, <a>fromEnum</a> and <a>toEnum</a> to be
--   partial functions when the type is <a>Bounded</a>[1], but this is
--   unacceptable. So these classes are offered as a replacement,
--   correcting the types of those functions. We intentionally clash with
--   the names of the Prelude's class; if you wish to use both in the same
--   file, then import this module (or the Prelude) qualified.
--   
--   While we're at it, we also generalize the notion of enumeration.
--   Rather than requiring that the type is linearly enumerable, we
--   distinguish between forward enumeration (which allows for multiple
--   predecessors) and backward enumeration (which allows for multiple
--   successors). Moreover, we do not require that the enumeration order
--   coincides with the <a>Ord</a> ordering (if one exists), though it's
--   advisable that they do (for your sanity). However, we also ensure that
--   the notion of enumeration (in either direction) is well-defined, which
--   rules out instances for <a>Float</a> and <a>Double</a>, and renders
--   instances for <tt>Ratio</tt> problematic. <tt>Ratio</tt> instances
--   <i>can</i> be provided so long as the base type is integral and
--   enumerable; but they must be done in an obscure order[2] that does not
--   coincide with <a>Ord</a>. Since this is not what people may expect, we
--   only provide an instance for the newtype <tt>CalkinWilf</tt>, not for
--   <tt>Ratio</tt> itself.
--   
--   The <tt>MagicHash</tt> extension is only actually required if on GHC.
--   This extension is used only so that the implementation of the
--   instances for <a>Char</a> match those of the Prelude's <a>Enum</a>. I
--   have not benchmarked to determine whether this low-level hackery is
--   actually still necessary.
--   
--   <ul>
--   <li><i>1</i>
--   <a>http://www.haskell.org/onlinereport/haskell2010/haskellch6.html#x13-1310006.3.4</a></li>
--   <li><i>2</i> Jeremy Gibbons, David Lester, and Richard Bird (2006).
--   <i>Enumerating the Rationals</i>. JFP 16(3):281--291.
--   DOI:10.1017/S0956796806005880
--   <a>http://www.cs.ox.ac.uk/jeremy.gibbons/publications/rationals.pdf</a></li>
--   </ul>
module Prelude.SafeEnum

-- | A class for upward enumerable types. That is, we can enumerate larger
--   and larger values, eventually getting every one of them; i.e., given
--   any <tt>x</tt>, for all <tt>y</tt> such that <tt>y `succeeds` x</tt>,
--   it must be the case that <tt>y</tt> occurs within some finite prefix
--   of <tt>enumFrom x</tt>.
--   
--   We require that <a>succeeds</a> forms a strict partial order. That is,
--   it must obey the following laws (N.B., if the first two laws hold,
--   then the third one follows for free):
--   
--   <pre>
--   if x `succeeds` y &amp;&amp; y `succeeds` z then x `succeeds` z
--   if x `succeeds` y then not (y `succeeds` x)
--   not (x `succeeds` x)
--   </pre>
--   
--   Moreover, we require that <a>succeeds</a> agrees with <a>succ</a>, and
--   that <a>succ</a> is exhaustive for <a>succeeds</a> (assuming <tt>Eq
--   a</tt>, by magic if need be):
--   
--   <pre>
--   if succ x == Just y then y `succeeds` x
--   if x `succeeds` y   then x `elem` enumFrom y
--   </pre>
--   
--   Minimal complete definition: <a>succ</a>, <a>succeeds</a>.
class UpwardEnum a

-- | The successor of a value, or <tt>Nothing</tt> is there isn't one. For
--   the numeric types in the Prelude, <a>succ</a> adds 1.
succ :: UpwardEnum a => a -> Maybe a

-- | A variant of <tt>(<a>&gt;</a>)</tt> with regards to the enumeration
--   order.
succeeds :: UpwardEnum a => a -> a -> Bool

-- | Return <tt>x</tt> followed by all it's successors, in order. The
--   resulting list is always non-empty, since it includes <tt>x</tt>. If
--   the resulting list is always finite, then the <a>succeeds</a> ordering
--   is converse well-founded. In GHC, the default implementation is a
--   "good producer" for list fusion.
enumFrom :: UpwardEnum a => a -> [a]

-- | Return the elements of <tt><a>enumFrom</a> x</tt>, filtering out
--   everything that succeeds <tt>z</tt>. If <tt>x</tt> succeeds
--   <tt>z</tt>, then the resulting list is empty; otherwise, it is
--   non-empty, since it includes <tt>x</tt>. In GHC, the default
--   implementation is a "good producer" for list fusion.
enumFromTo :: UpwardEnum a => a -> a -> [a]

-- | A class for downward enumerable types. That is, we can enumerate
--   smaller and smaller values, eventually getting every one of them;
--   i.e., given any <tt>x</tt>, for all <tt>y</tt> such that <tt>y
--   `precedes` x</tt>, it must be the case that <tt>y</tt> occurs within
--   some finite prefix of <tt>enumDownFrom x</tt>.
--   
--   We require that <a>precedes</a> forms a strict partial order. That is,
--   it must obey the following laws (N.B., if the first two laws hold,
--   then the third one follows for free):
--   
--   <pre>
--   if x `precedes` y &amp;&amp; y `precedes` z then x `precedes` z
--   if x `precedes` y then not (y `precedes` x)
--   not (x `precedes` x)
--   </pre>
--   
--   Moreover, we require that <a>precedes</a> agrees with <a>pred</a>, and
--   that <a>pred</a> is exhaustive for <a>precedes</a> (assuming <tt>Eq
--   a</tt>, by magic if need be):
--   
--   <pre>
--   if pred x == Just y then y `precedes` x
--   if x `precedes` y   then x `elem` enumDownFrom y
--   </pre>
--   
--   Minimal complete definition: <a>pred</a>, <a>precedes</a>.
class DownwardEnum a

-- | The predecessor of a value, or <tt>Nothing</tt> is there isn't one.
--   For the numeric types in the Prelude, <a>pred</a> subtracts 1.
pred :: DownwardEnum a => a -> Maybe a

-- | A variant of <tt>(<a>&lt;</a>)</tt> with regards to the enumeration
--   order.
precedes :: DownwardEnum a => a -> a -> Bool

-- | Return <tt>x</tt> followed by all it's predecessors, in (reverse)
--   order. The resulting list is always non-empty, since it includes
--   <tt>x</tt>. If the resulting list is always finite, then the
--   <a>precedes</a> ordering is well-founded. In GHC, the default
--   implementation is a "good producer" for list fusion.
enumDownFrom :: DownwardEnum a => a -> [a]

-- | Return the elements of <tt><a>enumDownFrom</a> x</tt>, filtering out
--   everything that precedes <tt>z</tt>. If <tt>x</tt> precedes
--   <tt>z</tt>, then the resulting list is empty; otherwise, it is
--   non-empty, since it includes <tt>x</tt>. In GHC, the default
--   implementation is a "good producer" for list fusion.
enumDownFromTo :: DownwardEnum a => a -> a -> [a]

-- | A class for types with a linear enumeration order. We require that the
--   partial orders of the superclasses agree:
--   
--   <pre>
--   x `succeeds` y  ==  y `precedes` x
--   </pre>
--   
--   That the enumeration order is preserved/reflected:
--   
--   <pre>
--   i `succeeds` j  ==  toEnum   i `succeeds` toEnum   j
--   x `succeeds` y  ==  fromEnum x `succeeds` fromEnum y
--   </pre>
--   
--   And that <a>toEnum</a> and <a>fromEnum</a> form a weak isomorphism;
--   i.e., for some <tt>p</tt> and <tt>q</tt>, the following must hold:
--   
--   <pre>
--   fromEnum &lt;=&lt; toEnum    ==  (\i -&gt; if p i then Just i else Nothing)
--   toEnum   &lt;=&lt; fromEnum  ==  (\x -&gt; if q x then Just x else Nothing)
--   </pre>
--   
--   In other words, the following type-restricted functions form an
--   isomorphism of linear orderings.
--   
--   <pre>
--   toEnum'   :: {i :: Int | toEnum   i == Just _} -&gt; a
--   fromEnum' :: {x :: a   | fromEnum x == Just _} -&gt; Int
--   </pre>
--   
--   Minimal complete definition: <a>toEnum</a>, <a>fromEnum</a>. N.B., the
--   default definitions for <a>enumFromThen</a> and <a>enumFromThenTo</a>
--   only make sense when the type <tt>a</tt> is "smaller" than <a>Int</a>
--   (i.e., <a>fromEnum</a> always succeeds); if <a>fromEnum</a> ever
--   fails, then you must override the defaults in order to correctly infer
--   the stride for values which cannot be converted to <a>Int</a>.
class (UpwardEnum a, DownwardEnum a) => Enum a

-- | Convert from an <a>Int</a>.
toEnum :: Enum a => Int -> Maybe a

-- | Convert to an <a>Int</a>.
fromEnum :: Enum a => a -> Maybe Int

-- | Enumerate values with an inferred stride. The resulting list is always
--   non-empty, since it includes <tt>x</tt>. Naturally, this should agree
--   with <a>enumFrom</a> and <a>enumDownFrom</a> (assuming <tt>Eq a</tt>,
--   by magic if need be):
--   
--   <pre>
--   if succ x == Just y then enumFromThen x y == enumFrom x
--   if pred x == Just y then enumFromThen x y == enumDownFrom x
--   </pre>
--   
--   In the default implementation: if <a>fromEnum</a> fails on either
--   argument, then the result is exactly <tt>[x]</tt>; and if
--   <a>toEnum</a> fails on any of the enumerated integers, then the first
--   failure terminates the enumeration. If either of these properties is
--   inappropriate, then you should override the default. In GHC, the
--   default implementation is a "good producer" for list fusion.
enumFromThen :: Enum a => a -> a -> [a]

-- | Enumerate values with an inferred stride and a given limit. If
--   <tt>x</tt> precedes <tt>y</tt> (and therefore we're enumerating
--   forward) but <tt>x</tt> succeeds <tt>z</tt> (and therefore is past the
--   limit), then the result is empty. Similarly, if <tt>x</tt> succeeds
--   <tt>y</tt> (and therefore we're enumerating backward) but <tt>x</tt>
--   precedes <tt>z</tt> (and therefore is past the limit), then the result
--   is empty. Otherwise the result is non-empty since it contains
--   <tt>x</tt>. Naturally, this should agree with <a>enumFromTo</a> and
--   <a>enumDownFromTo</a> (assuming <tt>Eq a</tt>, by magic if need be):
--   
--   <pre>
--   if succ x == Just y then enumFromThenTo x y z == enumFromTo x z
--   if pred x == Just y then enumFromThenTo x y z == enumDownFromTo x z
--   </pre>
--   
--   In the default implementation: if <a>fromEnum</a> fails on any
--   argument, then the result is either <tt>[]</tt> or <tt>[x]</tt> (as
--   appropriate); and if <a>toEnum</a> fails on any of the enumerated
--   integers, then the first failure terminates the enumeration. If either
--   of these properties is inappropriate, then you should override the
--   default. In GHC, the default implementation is a "good producer" for
--   list fusion.
enumFromThenTo :: Enum a => a -> a -> a -> [a]
instance Prelude.SafeEnum.Enum ()
instance Prelude.SafeEnum.Enum GHC.Types.Bool
instance Prelude.SafeEnum.Enum GHC.Types.Ordering
instance Prelude.SafeEnum.Enum GHC.Types.Char
instance Prelude.SafeEnum.Enum GHC.Types.Int
instance Prelude.SafeEnum.Enum GHC.Integer.Type.Integer
instance Prelude.SafeEnum.DownwardEnum ()
instance Prelude.SafeEnum.DownwardEnum GHC.Types.Bool
instance Prelude.SafeEnum.DownwardEnum GHC.Types.Ordering
instance Prelude.SafeEnum.DownwardEnum GHC.Types.Char
instance Prelude.SafeEnum.DownwardEnum GHC.Types.Int
instance Prelude.SafeEnum.DownwardEnum GHC.Integer.Type.Integer
instance Prelude.SafeEnum.UpwardEnum ()
instance Prelude.SafeEnum.UpwardEnum GHC.Types.Bool
instance Prelude.SafeEnum.UpwardEnum GHC.Types.Ordering
instance Prelude.SafeEnum.UpwardEnum GHC.Types.Char
instance Prelude.SafeEnum.UpwardEnum GHC.Types.Int
instance Prelude.SafeEnum.UpwardEnum GHC.Integer.Type.Integer


-- | Enumerate the rationals in Calkin--Wilf order. That is, when we give
--   enumeration a well-specified meaning (as <a>Prelude.SafeEnum</a> does)
--   this renders instances for <a>Ratio</a> problematic. <a>Ratio</a>
--   instances <i>can</i> be provided so long as the base type is integral
--   and enumerable; but they must be done in an obscure order that does
--   not coincide with the <a>Ord</a> instance for <a>Ratio</a>. Since this
--   is not what people may expect, we only provide an instance for the
--   newtype <a>CalkinWilf</a>, not for <a>Ratio</a> itself.
--   
--   <ul>
--   <li>Jeremy Gibbons, David Lester, and Richard Bird (2006).
--   <i>Enumerating the Rationals</i>. JFP 16(3):281--291.
--   DOI:10.1017/S0956796806005880
--   <a>http://www.cs.ox.ac.uk/jeremy.gibbons/publications/rationals.pdf</a></li>
--   </ul>
module Data.Number.CalkinWilf

-- | Enumerate the rationals in Calkin--Wilf order. The enumeration is
--   symmetric about zero, ensuring that all the negative rationals come
--   before zero and all the positive rationals come after zero.
--   
--   BUG: while the <a>succeeds</a>, <a>precedes</a>, <a>toEnum</a>, and
--   <a>fromEnum</a> methods are correct, they are horribly inefficient.
--   This can be rectified (or at least mitigated), but this remains to be
--   done.
newtype CalkinWilf a
CalkinWilf :: (Ratio a) -> CalkinWilf a

-- | Return the underlying <a>Ratio</a>. Not using record syntax to define
--   this in order to pretty up the derived <a>Show</a> instance.
unCalkinWilf :: CalkinWilf a -> Ratio a
instance GHC.Real.Integral a => GHC.Real.RealFrac (Data.Number.CalkinWilf.CalkinWilf a)
instance GHC.Real.Integral a => GHC.Real.Real (Data.Number.CalkinWilf.CalkinWilf a)
instance GHC.Real.Integral a => GHC.Real.Fractional (Data.Number.CalkinWilf.CalkinWilf a)
instance GHC.Real.Integral a => GHC.Num.Num (Data.Number.CalkinWilf.CalkinWilf a)
instance GHC.Real.Integral a => GHC.Classes.Ord (Data.Number.CalkinWilf.CalkinWilf a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Number.CalkinWilf.CalkinWilf a)
instance GHC.Show.Show a => GHC.Show.Show (Data.Number.CalkinWilf.CalkinWilf a)
instance (GHC.Real.Integral a, GHC.Read.Read a) => GHC.Read.Read (Data.Number.CalkinWilf.CalkinWilf a)
instance GHC.Real.Integral a => Prelude.SafeEnum.UpwardEnum (Data.Number.CalkinWilf.CalkinWilf a)
instance GHC.Real.Integral a => Prelude.SafeEnum.DownwardEnum (Data.Number.CalkinWilf.CalkinWilf a)
instance GHC.Real.Integral a => Prelude.SafeEnum.Enum (Data.Number.CalkinWilf.CalkinWilf a)
instance GHC.Real.Integral a => GHC.Enum.Enum (Data.Number.CalkinWilf.CalkinWilf a)
