<?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://www.cs.york.ac.uk/fp/darcs/hscolour/ --> <title>Data/Function.hs</title> <link type='text/css' rel='stylesheet' href='hscolour.css' /> </head> <body> <pre><a name="line-1"></a><span class='hs-comment'>-----------------------------------------------------------------------------</span> <a name="line-2"></a><span class='hs-comment'>-- |</span> <a name="line-3"></a><span class='hs-comment'>-- Module : Data.Function</span> <a name="line-4"></a><span class='hs-comment'>-- Copyright : Nils Anders Danielsson 2006</span> <a name="line-5"></a><span class='hs-comment'>-- License : BSD-style (see the LICENSE file in the distribution)</span> <a name="line-6"></a><span class='hs-comment'>--</span> <a name="line-7"></a><span class='hs-comment'>-- Maintainer : libraries@haskell.org</span> <a name="line-8"></a><span class='hs-comment'>-- Stability : experimental</span> <a name="line-9"></a><span class='hs-comment'>-- Portability : portable</span> <a name="line-10"></a><span class='hs-comment'>--</span> <a name="line-11"></a><span class='hs-comment'>-- Simple combinators working solely on and with functions.</span> <a name="line-12"></a> <a name="line-13"></a><span class='hs-keyword'>module</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>Function</span> <a name="line-14"></a> <span class='hs-layout'>(</span> <span class='hs-comment'>-- * "Prelude" re-exports</span> <a name="line-15"></a> <span class='hs-varid'>id</span><span class='hs-layout'>,</span> <span class='hs-varid'>const</span><span class='hs-layout'>,</span> <span class='hs-layout'>(</span><span class='hs-varop'>.</span><span class='hs-layout'>)</span><span class='hs-layout'>,</span> <span class='hs-varid'>flip</span><span class='hs-layout'>,</span> <span class='hs-layout'>(</span><span class='hs-varop'>$</span><span class='hs-layout'>)</span> <a name="line-16"></a> <span class='hs-comment'>-- * Other combinators</span> <a name="line-17"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>fix</span> <a name="line-18"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>on</span> <a name="line-19"></a> <span class='hs-layout'>)</span> <span class='hs-keyword'>where</span> <a name="line-20"></a> <a name="line-21"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Prelude</span> <a name="line-22"></a> <a name="line-23"></a><span class='hs-keyword'>infixl</span> <span class='hs-num'>0</span> <span class='hs-varop'>`on`</span> <a name="line-24"></a> <a name="line-25"></a><a name="fix"></a><span class='hs-comment'>-- | @'fix' f@ is the least fixed point of the function @f@,</span> <a name="line-26"></a><span class='hs-comment'>-- i.e. the least defined @x@ such that @f x = x@.</span> <a name="line-27"></a><span class='hs-definition'>fix</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></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-28"></a><span class='hs-definition'>fix</span> <span class='hs-varid'>f</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>let</span> <span class='hs-varid'>x</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>f</span> <span class='hs-varid'>x</span> <span class='hs-keyword'>in</span> <span class='hs-varid'>x</span> <a name="line-29"></a> <a name="line-30"></a><span class='hs-comment'>-- | @(*) \`on\` f = \\x y -> f x * f y@.</span> <a name="line-31"></a><span class='hs-comment'>--</span> <a name="line-32"></a><span class='hs-comment'>-- Typical usage: @'Data.List.sortBy' ('compare' \`on\` 'fst')@.</span> <a name="line-33"></a><span class='hs-comment'>--</span> <a name="line-34"></a><span class='hs-comment'>-- Algebraic properties:</span> <a name="line-35"></a><span class='hs-comment'>--</span> <a name="line-36"></a><span class='hs-comment'>-- * @(*) \`on\` 'id' = (*)@ (if @(*) &#x2209; {&#x22a5;, 'const' &#x22a5;}@)</span> <a name="line-37"></a><span class='hs-comment'>--</span> <a name="line-38"></a><span class='hs-comment'>-- * @((*) \`on\` f) \`on\` g = (*) \`on\` (f . g)@</span> <a name="line-39"></a><span class='hs-comment'>--</span> <a name="line-40"></a><span class='hs-comment'>-- * @'flip' on f . 'flip' on g = 'flip' on (g . f)@</span> <a name="line-41"></a> <a name="line-42"></a><span class='hs-comment'>-- Proofs (so that I don't have to edit the test-suite):</span> <a name="line-43"></a> <a name="line-44"></a><span class='hs-comment'>-- (*) `on` id</span> <a name="line-45"></a><span class='hs-comment'>-- =</span> <a name="line-46"></a><span class='hs-comment'>-- \x y -> id x * id y</span> <a name="line-47"></a><span class='hs-comment'>-- =</span> <a name="line-48"></a><span class='hs-comment'>-- \x y -> x * y</span> <a name="line-49"></a><span class='hs-comment'>-- = { If (*) /= _|_ or const _|_. }</span> <a name="line-50"></a><span class='hs-comment'>-- (*)</span> <a name="line-51"></a> <a name="line-52"></a><span class='hs-comment'>-- (*) `on` f `on` g</span> <a name="line-53"></a><span class='hs-comment'>-- =</span> <a name="line-54"></a><span class='hs-comment'>-- ((*) `on` f) `on` g</span> <a name="line-55"></a><span class='hs-comment'>-- =</span> <a name="line-56"></a><span class='hs-comment'>-- \x y -> ((*) `on` f) (g x) (g y)</span> <a name="line-57"></a><span class='hs-comment'>-- =</span> <a name="line-58"></a><span class='hs-comment'>-- \x y -> (\x y -> f x * f y) (g x) (g y)</span> <a name="line-59"></a><span class='hs-comment'>-- =</span> <a name="line-60"></a><span class='hs-comment'>-- \x y -> f (g x) * f (g y)</span> <a name="line-61"></a><span class='hs-comment'>-- =</span> <a name="line-62"></a><span class='hs-comment'>-- \x y -> (f . g) x * (f . g) y</span> <a name="line-63"></a><span class='hs-comment'>-- =</span> <a name="line-64"></a><span class='hs-comment'>-- (*) `on` (f . g)</span> <a name="line-65"></a><span class='hs-comment'>-- =</span> <a name="line-66"></a><span class='hs-comment'>-- (*) `on` f . g</span> <a name="line-67"></a> <a name="line-68"></a><span class='hs-comment'>-- flip on f . flip on g</span> <a name="line-69"></a><span class='hs-comment'>-- =</span> <a name="line-70"></a><span class='hs-comment'>-- (\h (*) -> (*) `on` h) f . (\h (*) -> (*) `on` h) g</span> <a name="line-71"></a><span class='hs-comment'>-- =</span> <a name="line-72"></a><span class='hs-comment'>-- (\(*) -> (*) `on` f) . (\(*) -> (*) `on` g)</span> <a name="line-73"></a><span class='hs-comment'>-- =</span> <a name="line-74"></a><span class='hs-comment'>-- \(*) -> (*) `on` g `on` f</span> <a name="line-75"></a><span class='hs-comment'>-- = { See above. }</span> <a name="line-76"></a><span class='hs-comment'>-- \(*) -> (*) `on` g . f</span> <a name="line-77"></a><span class='hs-comment'>-- =</span> <a name="line-78"></a><span class='hs-comment'>-- (\h (*) -> (*) `on` h) (g . f)</span> <a name="line-79"></a><span class='hs-comment'>-- =</span> <a name="line-80"></a><span class='hs-comment'>-- flip on (g . f)</span> <a name="line-81"></a> <a name="line-82"></a><a name="on"></a><span class='hs-definition'>on</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-varid'>b</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>c</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-layout'>(</span><span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>b</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>c</span> <a name="line-83"></a><a name=".*."></a><span class='hs-layout'>(</span><span class='hs-varop'>.*.</span><span class='hs-layout'>)</span> <span class='hs-varop'>`on`</span> <span class='hs-varid'>f</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyglyph'>\</span><span class='hs-varid'>x</span> <span class='hs-varid'>y</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>f</span> <span class='hs-varid'>x</span> <span class='hs-varop'>.*.</span> <span class='hs-varid'>f</span> <span class='hs-varid'>y</span> </pre></body> </html>