<?xml version="1.0" encoding="UTF-8"?> <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"> <html> <head> <!-- Generated by HsColour, http://code.haskell.org/~malcolm/hscolour/ --> <title>Data/Number/Natural.hs</title> <link type='text/css' rel='stylesheet' href='hscolour.css' /> </head> <body> <pre><a name="line-1"></a><span class='hs-comment'>-- | Lazy natural numbers.</span> <a name="line-2"></a><span class='hs-comment'>-- Addition and multiplication recurses over the first argument, i.e.,</span> <a name="line-3"></a><span class='hs-comment'>-- @1 + n@ is the way to write the constant time successor function.</span> <a name="line-4"></a><span class='hs-comment'>--</span> <a name="line-5"></a><span class='hs-comment'>-- Note that (+) and (*) are not commutative for lazy natural numbers</span> <a name="line-6"></a><span class='hs-comment'>-- when considering bottom.</span> <a name="line-7"></a><span class='hs-keyword'>module</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>Number</span><span class='hs-varop'>.</span><span class='hs-conid'>Natural</span><span class='hs-layout'>(</span><span class='hs-conid'>Natural</span><span class='hs-layout'>,</span> <span class='hs-varid'>infinity</span><span class='hs-layout'>)</span> <span class='hs-keyword'>where</span> <a name="line-8"></a> <a name="line-9"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>Maybe</span> <a name="line-10"></a> <a name="line-11"></a><a name="Natural"></a><span class='hs-keyword'>data</span> <span class='hs-conid'>Natural</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Z</span> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>S</span> <span class='hs-conid'>Natural</span> <a name="line-12"></a> <a name="line-13"></a><a name="instance%20Show%20Natural"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>Show</span> <span class='hs-conid'>Natural</span> <span class='hs-keyword'>where</span> <a name="line-14"></a> <span class='hs-varid'>showsPrec</span> <span class='hs-varid'>p</span> <span class='hs-varid'>n</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>showsPrec</span> <span class='hs-varid'>p</span> <span class='hs-layout'>(</span><span class='hs-varid'>toInteger</span> <span class='hs-varid'>n</span><span class='hs-layout'>)</span> <a name="line-15"></a> <a name="line-16"></a><a name="instance%20Eq%20Natural"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>Eq</span> <span class='hs-conid'>Natural</span> <span class='hs-keyword'>where</span> <a name="line-17"></a> <span class='hs-varid'>x</span> <span class='hs-varop'>==</span> <span class='hs-varid'>y</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>x</span> <span class='hs-varop'>`compare`</span> <span class='hs-varid'>y</span> <span class='hs-varop'>==</span> <span class='hs-conid'>EQ</span> <a name="line-18"></a> <a name="line-19"></a><a name="instance%20Ord%20Natural"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>Ord</span> <span class='hs-conid'>Natural</span> <span class='hs-keyword'>where</span> <a name="line-20"></a> <span class='hs-conid'>Z</span> <span class='hs-varop'>`compare`</span> <span class='hs-conid'>Z</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>EQ</span> <a name="line-21"></a> <span class='hs-conid'>Z</span> <span class='hs-varop'>`compare`</span> <span class='hs-conid'>S</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>LT</span> <a name="line-22"></a> <span class='hs-conid'>S</span> <span class='hs-keyword'>_</span> <span class='hs-varop'>`compare`</span> <span class='hs-conid'>Z</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>GT</span> <a name="line-23"></a> <span class='hs-conid'>S</span> <span class='hs-varid'>x</span> <span class='hs-varop'>`compare`</span> <span class='hs-conid'>S</span> <span class='hs-varid'>y</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>x</span> <span class='hs-varop'>`compare`</span> <span class='hs-varid'>y</span> <a name="line-24"></a> <a name="line-25"></a> <span class='hs-comment'>-- (_|_) `compare` Z == _|_, but (_|_) >= Z = True</span> <a name="line-26"></a> <span class='hs-comment'>-- so for maximum laziness, we need a specialized version of (>=) and (<=)</span> <a name="line-27"></a> <span class='hs-keyword'>_</span> <span class='hs-varop'>>=</span> <span class='hs-conid'>Z</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>True</span> <a name="line-28"></a> <span class='hs-conid'>Z</span> <span class='hs-varop'>>=</span> <span class='hs-conid'>S</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>False</span> <a name="line-29"></a> <span class='hs-conid'>S</span> <span class='hs-varid'>a</span> <span class='hs-varop'>>=</span> <span class='hs-conid'>S</span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>a</span> <span class='hs-varop'>>=</span> <span class='hs-varid'>b</span> <a name="line-30"></a> <a name="line-31"></a> <span class='hs-layout'>(</span><span class='hs-varop'><=</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>flip</span> <span class='hs-layout'>(</span><span class='hs-varop'>>=</span><span class='hs-layout'>)</span> <a name="line-32"></a> <a name="line-33"></a> <span class='hs-conid'>S</span> <span class='hs-varid'>x</span> <span class='hs-varop'>`max`</span> <span class='hs-conid'>S</span> <span class='hs-varid'>y</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>S</span> <span class='hs-layout'>(</span><span class='hs-varid'>x</span> <span class='hs-varop'>`max`</span> <span class='hs-varid'>y</span><span class='hs-layout'>)</span> <a name="line-34"></a> <span class='hs-varid'>x</span> <span class='hs-varop'>`max`</span> <span class='hs-varid'>y</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>x</span> <span class='hs-varop'>+</span> <span class='hs-varid'>y</span> <a name="line-35"></a> <a name="line-36"></a> <span class='hs-conid'>S</span> <span class='hs-varid'>x</span> <span class='hs-varop'>`min`</span> <span class='hs-conid'>S</span> <span class='hs-varid'>y</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>S</span> <span class='hs-layout'>(</span><span class='hs-varid'>x</span> <span class='hs-varop'>`min`</span> <span class='hs-varid'>y</span><span class='hs-layout'>)</span> <a name="line-37"></a> <span class='hs-keyword'>_</span> <span class='hs-varop'>`min`</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Z</span> <a name="line-38"></a> <a name="line-39"></a><a name="maybeSubtract"></a><span class='hs-definition'>maybeSubtract</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Natural</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Natural</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Maybe</span> <span class='hs-conid'>Natural</span> <a name="line-40"></a><a name="maybeSubtract"></a><span class='hs-definition'>a</span> <span class='hs-varop'>`maybeSubtract`</span> <span class='hs-conid'>Z</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Just</span> <span class='hs-varid'>a</span> <a name="line-41"></a><span class='hs-conid'>S</span> <span class='hs-varid'>a</span> <span class='hs-varop'>`maybeSubtract`</span> <span class='hs-conid'>S</span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>a</span> <span class='hs-varop'>`maybeSubtract`</span> <span class='hs-varid'>b</span> <a name="line-42"></a><span class='hs-keyword'>_</span> <span class='hs-varop'>`maybeSubtract`</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Nothing</span> <a name="line-43"></a> <a name="line-44"></a><a name="instance%20Num%20Natural"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>Num</span> <span class='hs-conid'>Natural</span> <span class='hs-keyword'>where</span> <a name="line-45"></a> <span class='hs-conid'>Z</span> <span class='hs-varop'>+</span> <span class='hs-varid'>y</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>y</span> <a name="line-46"></a> <span class='hs-conid'>S</span> <span class='hs-varid'>x</span> <span class='hs-varop'>+</span> <span class='hs-varid'>y</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>S</span> <span class='hs-layout'>(</span><span class='hs-varid'>x</span> <span class='hs-varop'>+</span> <span class='hs-varid'>y</span><span class='hs-layout'>)</span> <a name="line-47"></a> <a name="line-48"></a> <span class='hs-varid'>x</span> <span class='hs-comment'>-</span> <span class='hs-varid'>y</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>fromMaybe</span> <span class='hs-layout'>(</span><span class='hs-varid'>error</span> <span class='hs-str'>"Natural: (-)"</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>x</span> <span class='hs-varop'>`maybeSubtract`</span> <span class='hs-varid'>y</span><span class='hs-layout'>)</span> <a name="line-49"></a> <a name="line-50"></a> <span class='hs-conid'>Z</span> <span class='hs-varop'>*</span> <span class='hs-varid'>y</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Z</span> <a name="line-51"></a> <span class='hs-conid'>S</span> <span class='hs-varid'>x</span> <span class='hs-varop'>*</span> <span class='hs-varid'>y</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>y</span> <span class='hs-varop'>+</span> <span class='hs-varid'>x</span> <span class='hs-varop'>*</span> <span class='hs-varid'>y</span> <a name="line-52"></a> <a name="line-53"></a> <span class='hs-varid'>abs</span> <span class='hs-varid'>x</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>x</span> <a name="line-54"></a> <span class='hs-varid'>signum</span> <span class='hs-conid'>Z</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Z</span> <a name="line-55"></a> <span class='hs-varid'>signum</span> <span class='hs-layout'>(</span><span class='hs-conid'>S</span> <span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>S</span> <span class='hs-conid'>Z</span> <a name="line-56"></a> <a name="line-57"></a> <span class='hs-varid'>fromInteger</span> <span class='hs-varid'>x</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>x</span> <span class='hs-varop'><</span> <span class='hs-num'>0</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>error</span> <span class='hs-str'>"Natural: fromInteger"</span> <a name="line-58"></a> <span class='hs-varid'>fromInteger</span> <span class='hs-num'>0</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Z</span> <a name="line-59"></a> <span class='hs-varid'>fromInteger</span> <span class='hs-varid'>x</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>S</span> <span class='hs-layout'>(</span><span class='hs-varid'>fromInteger</span> <span class='hs-layout'>(</span><span class='hs-varid'>x</span><span class='hs-comment'>-</span><span class='hs-num'>1</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <a name="line-60"></a> <a name="line-61"></a><a name="instance%20Integral%20Natural"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>Integral</span> <span class='hs-conid'>Natural</span> <span class='hs-keyword'>where</span> <a name="line-62"></a> <span class='hs-comment'>-- Not the most efficient version, but efficiency isn't the point of this module. :)</span> <a name="line-63"></a> <span class='hs-varid'>quotRem</span> <span class='hs-varid'>x</span> <span class='hs-varid'>y</span> <span class='hs-keyglyph'>=</span> <a name="line-64"></a> <span class='hs-keyword'>if</span> <span class='hs-varid'>x</span> <span class='hs-varop'><</span> <span class='hs-varid'>y</span> <span class='hs-keyword'>then</span> <a name="line-65"></a> <span class='hs-layout'>(</span><span class='hs-num'>0</span><span class='hs-layout'>,</span> <span class='hs-varid'>x</span><span class='hs-layout'>)</span> <a name="line-66"></a> <span class='hs-keyword'>else</span> <a name="line-67"></a> <span class='hs-keyword'>let</span> <span class='hs-layout'>(</span><span class='hs-varid'>q</span><span class='hs-layout'>,</span> <span class='hs-varid'>r</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>quotRem</span> <span class='hs-layout'>(</span><span class='hs-varid'>x</span><span class='hs-comment'>-</span><span class='hs-varid'>y</span><span class='hs-layout'>)</span> <span class='hs-varid'>y</span> <a name="line-68"></a> <span class='hs-keyword'>in</span> <span class='hs-layout'>(</span><span class='hs-num'>1</span><span class='hs-varop'>+</span><span class='hs-varid'>q</span><span class='hs-layout'>,</span> <span class='hs-varid'>r</span><span class='hs-layout'>)</span> <a name="line-69"></a> <span class='hs-varid'>div</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>quot</span> <a name="line-70"></a> <span class='hs-varid'>mod</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>rem</span> <a name="line-71"></a> <span class='hs-varid'>toInteger</span> <span class='hs-conid'>Z</span> <span class='hs-keyglyph'>=</span> <span class='hs-num'>0</span> <a name="line-72"></a> <span class='hs-varid'>toInteger</span> <span class='hs-layout'>(</span><span class='hs-conid'>S</span> <span class='hs-varid'>x</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-num'>1</span> <span class='hs-varop'>+</span> <span class='hs-varid'>toInteger</span> <span class='hs-varid'>x</span> <a name="line-73"></a> <a name="line-74"></a><a name="instance%20Real%20Natural"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>Real</span> <span class='hs-conid'>Natural</span> <span class='hs-keyword'>where</span> <a name="line-75"></a> <span class='hs-varid'>toRational</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>toRational</span> <span class='hs-varop'>.</span> <span class='hs-varid'>toInteger</span> <a name="line-76"></a> <a name="line-77"></a><a name="instance%20Enum%20Natural"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>Enum</span> <span class='hs-conid'>Natural</span> <span class='hs-keyword'>where</span> <a name="line-78"></a> <span class='hs-varid'>succ</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>S</span> <a name="line-79"></a> <span class='hs-varid'>pred</span> <span class='hs-conid'>Z</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>error</span> <span class='hs-str'>"Natural: pred 0"</span> <a name="line-80"></a> <span class='hs-varid'>pred</span> <span class='hs-layout'>(</span><span class='hs-conid'>S</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>a</span> <a name="line-81"></a> <span class='hs-varid'>toEnum</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>fromIntegral</span> <a name="line-82"></a> <span class='hs-varid'>fromEnum</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>fromIntegral</span> <a name="line-83"></a> <span class='hs-varid'>enumFromThenTo</span> <span class='hs-varid'>from</span> <span class='hs-varid'>thn</span> <span class='hs-varid'>to</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>from</span> <span class='hs-varop'><=</span> <span class='hs-varid'>thn</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>go</span> <span class='hs-varid'>from</span> <span class='hs-layout'>(</span><span class='hs-varid'>to</span> <span class='hs-varop'>`maybeSubtract`</span> <span class='hs-varid'>from</span><span class='hs-layout'>)</span> <span class='hs-keyword'>where</span> <a name="line-84"></a> <span class='hs-varid'>go</span> <span class='hs-varid'>from</span> <span class='hs-conid'>Nothing</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>[]</span> <a name="line-85"></a> <span class='hs-varid'>go</span> <span class='hs-varid'>from</span> <span class='hs-layout'>(</span><span class='hs-conid'>Just</span> <span class='hs-varid'>count</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>from</span><span class='hs-conop'>:</span><span class='hs-varid'>go</span> <span class='hs-layout'>(</span><span class='hs-varid'>step</span> <span class='hs-varop'>+</span> <span class='hs-varid'>from</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>count</span> <span class='hs-varop'>`maybeSubtract`</span> <span class='hs-varid'>step</span><span class='hs-layout'>)</span> <a name="line-86"></a> <span class='hs-varid'>step</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>thn</span> <span class='hs-comment'>-</span> <span class='hs-varid'>from</span> <a name="line-87"></a> <span class='hs-varid'>enumFromThenTo</span> <span class='hs-varid'>from</span> <span class='hs-varid'>thn</span> <span class='hs-varid'>to</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>go</span> <span class='hs-layout'>(</span><span class='hs-varid'>from</span> <span class='hs-varop'>+</span> <span class='hs-varid'>step</span><span class='hs-layout'>)</span> <span class='hs-keyword'>where</span> <a name="line-88"></a> <span class='hs-varid'>go</span> <span class='hs-varid'>from</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>from</span> <span class='hs-varop'>>=</span> <span class='hs-varid'>to</span> <span class='hs-varop'>+</span> <span class='hs-varid'>step</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>let</span> <span class='hs-varid'>next</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>from</span> <span class='hs-comment'>-</span> <span class='hs-varid'>step</span> <span class='hs-keyword'>in</span> <span class='hs-varid'>next</span><span class='hs-conop'>:</span><span class='hs-varid'>go</span> <span class='hs-varid'>next</span> <a name="line-89"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>[]</span> <a name="line-90"></a> <span class='hs-varid'>step</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>from</span> <span class='hs-comment'>-</span> <span class='hs-varid'>thn</span> <a name="line-91"></a> <span class='hs-varid'>enumFrom</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>enumFromThenTo</span> <span class='hs-varid'>a</span> <span class='hs-layout'>(</span><span class='hs-conid'>S</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-varid'>infinity</span> <a name="line-92"></a> <span class='hs-varid'>enumFromThen</span> <span class='hs-varid'>a</span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>enumFromThenTo</span> <span class='hs-varid'>a</span> <span class='hs-varid'>b</span> <span class='hs-varid'>infinity</span> <a name="line-93"></a> <span class='hs-varid'>enumFromTo</span> <span class='hs-varid'>a</span> <span class='hs-varid'>c</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>enumFromThenTo</span> <span class='hs-varid'>a</span> <span class='hs-layout'>(</span><span class='hs-conid'>S</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-varid'>c</span> <a name="line-94"></a> <a name="line-95"></a><a name="infinity"></a><span class='hs-comment'>-- | The infinite natural number.</span> <a name="line-96"></a><span class='hs-definition'>infinity</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Natural</span> <a name="line-97"></a><span class='hs-definition'>infinity</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>S</span> <span class='hs-varid'>infinity</span> </pre></body> </html>
distrib
>
Fedora
>
18
>
x86_64
>
media
>
updates
>
by-pkgid
>
d9ab9b712c406347034632251e926a6d
>
files
>
70
