/usr/share/doc/libghc-maths-doc/html/src/Math-Algebras-NonCommutative.html is in libghc-maths-doc 0.4.8-4.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 | <?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>Math/Algebras/NonCommutative.hs</title>
<link type='text/css' rel='stylesheet' href='hscolour.css' />
</head>
<body>
<pre><a name="line-1"></a><span class='hs-comment'>-- Copyright (c) 2010-2015, David Amos. All rights reserved.</span>
<a name="line-2"></a>
<a name="line-3"></a><span class='hs-comment'>{-# LANGUAGE FlexibleInstances, MultiParamTypeClasses #-}</span>
<a name="line-4"></a>
<a name="line-5"></a><span class='hs-comment'>-- |A module defining the algebra of non-commutative polynomials over a field k</span>
<a name="line-6"></a><span class='hs-keyword'>module</span> <span class='hs-conid'>Math</span><span class='hs-varop'>.</span><span class='hs-conid'>Algebras</span><span class='hs-varop'>.</span><span class='hs-conid'>NonCommutative</span> <span class='hs-keyword'>where</span>
<a name="line-7"></a>
<a name="line-8"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Prelude</span> <span class='hs-varid'>hiding</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>
<a name="line-9"></a>
<a name="line-10"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Math</span><span class='hs-varop'>.</span><span class='hs-conid'>Algebra</span><span class='hs-varop'>.</span><span class='hs-conid'>Field</span><span class='hs-varop'>.</span><span class='hs-conid'>Base</span> <span class='hs-varid'>hiding</span> <span class='hs-layout'>(</span><span class='hs-varid'>powers</span><span class='hs-layout'>)</span>
<a name="line-11"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Math</span><span class='hs-varop'>.</span><span class='hs-conid'>Algebras</span><span class='hs-varop'>.</span><span class='hs-conid'>VectorSpace</span>
<a name="line-12"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Math</span><span class='hs-varop'>.</span><span class='hs-conid'>Algebras</span><span class='hs-varop'>.</span><span class='hs-conid'>TensorProduct</span>
<a name="line-13"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Math</span><span class='hs-varop'>.</span><span class='hs-conid'>Algebras</span><span class='hs-varop'>.</span><span class='hs-conid'>Structures</span>
<a name="line-14"></a><span class='hs-keyword'>import</span> <span class='hs-keyword'>qualified</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>List</span> <span class='hs-keyword'>as</span> <span class='hs-conid'>L</span>
<a name="line-15"></a>
<a name="line-16"></a>
<a name="line-17"></a><a name="NonComMonomial"></a><span class='hs-keyword'>data</span> <span class='hs-conid'>NonComMonomial</span> <span class='hs-varid'>v</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>NCM</span> <span class='hs-conid'>Int</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>v</span><span class='hs-keyglyph'>]</span> <span class='hs-keyword'>deriving</span> <span class='hs-layout'>(</span><span class='hs-conid'>Eq</span><span class='hs-layout'>)</span>
<a name="line-18"></a>
<a name="line-19"></a><a name="instance%20Ord%20(NonComMonomial%20v)"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>Ord</span> <span class='hs-varid'>v</span> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>Ord</span> <span class='hs-layout'>(</span><span class='hs-conid'>NonComMonomial</span> <span class='hs-varid'>v</span><span class='hs-layout'>)</span> <span class='hs-keyword'>where</span>
<a name="line-20"></a> <span class='hs-varid'>compare</span> <span class='hs-layout'>(</span><span class='hs-conid'>NCM</span> <span class='hs-varid'>lx</span> <span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-conid'>NCM</span> <span class='hs-varid'>ly</span> <span class='hs-varid'>ys</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>compare</span> <span class='hs-layout'>(</span><span class='hs-comment'>-</span><span class='hs-varid'>lx</span><span class='hs-layout'>,</span> <span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-comment'>-</span><span class='hs-varid'>ly</span><span class='hs-layout'>,</span> <span class='hs-varid'>ys</span><span class='hs-layout'>)</span>
<a name="line-21"></a><span class='hs-comment'>-- ie Glex ordering</span>
<a name="line-22"></a>
<a name="line-23"></a><a name="instance%20Show%20(NonComMonomial%20v)"></a><span class='hs-keyword'>instance</span> <span class='hs-layout'>(</span><span class='hs-conid'>Eq</span> <span class='hs-varid'>v</span><span class='hs-layout'>,</span> <span class='hs-conid'>Show</span> <span class='hs-varid'>v</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>Show</span> <span class='hs-layout'>(</span><span class='hs-conid'>NonComMonomial</span> <span class='hs-varid'>v</span><span class='hs-layout'>)</span> <span class='hs-keyword'>where</span>
<a name="line-24"></a> <span class='hs-varid'>show</span> <span class='hs-layout'>(</span><span class='hs-conid'>NCM</span> <span class='hs-keyword'>_</span> <span class='hs-conid'>[]</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-str'>"1"</span>
<a name="line-25"></a> <span class='hs-varid'>show</span> <span class='hs-layout'>(</span><span class='hs-conid'>NCM</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>vs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>concatMap</span> <span class='hs-varid'>showPower</span> <span class='hs-layout'>(</span><span class='hs-conid'>L</span><span class='hs-varop'>.</span><span class='hs-varid'>group</span> <span class='hs-varid'>vs</span><span class='hs-layout'>)</span>
<a name="line-26"></a> <span class='hs-keyword'>where</span> <span class='hs-varid'>showPower</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>v</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>showVar</span> <span class='hs-varid'>v</span>
<a name="line-27"></a> <span class='hs-varid'>showPower</span> <span class='hs-varid'>vs</span><span class='hs-keyglyph'>@</span><span class='hs-layout'>(</span><span class='hs-varid'>v</span><span class='hs-conop'>:</span><span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>showVar</span> <span class='hs-varid'>v</span> <span class='hs-varop'>++</span> <span class='hs-str'>"^"</span> <span class='hs-varop'>++</span> <span class='hs-varid'>show</span> <span class='hs-layout'>(</span><span class='hs-varid'>length</span> <span class='hs-varid'>vs</span><span class='hs-layout'>)</span>
<a name="line-28"></a> <span class='hs-varid'>showVar</span> <span class='hs-varid'>v</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>filter</span> <span class='hs-layout'>(</span><span class='hs-varop'>/=</span> <span class='hs-chr'>'"'</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>show</span> <span class='hs-varid'>v</span><span class='hs-layout'>)</span>
<a name="line-29"></a>
<a name="line-30"></a><a name="instance%20Mon%20(NonComMonomial%20v)"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>Mon</span> <span class='hs-layout'>(</span><span class='hs-conid'>NonComMonomial</span> <span class='hs-varid'>v</span><span class='hs-layout'>)</span> <span class='hs-keyword'>where</span>
<a name="line-31"></a> <span class='hs-varid'>munit</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>NCM</span> <span class='hs-num'>0</span> <span class='hs-conid'>[]</span>
<a name="line-32"></a> <span class='hs-varid'>mmult</span> <span class='hs-layout'>(</span><span class='hs-conid'>NCM</span> <span class='hs-varid'>i</span> <span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-conid'>NCM</span> <span class='hs-varid'>j</span> <span class='hs-varid'>ys</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>NCM</span> <span class='hs-layout'>(</span><span class='hs-varid'>i</span><span class='hs-varop'>+</span><span class='hs-varid'>j</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>xs</span><span class='hs-varop'>++</span><span class='hs-varid'>ys</span><span class='hs-layout'>)</span>
<a name="line-33"></a>
<a name="line-34"></a><a name="instance%20Algebra%20k%20(NonComMonomial%20v)"></a><span class='hs-keyword'>instance</span> <span class='hs-layout'>(</span><span class='hs-conid'>Eq</span> <span class='hs-varid'>k</span><span class='hs-layout'>,</span> <span class='hs-conid'>Num</span> <span class='hs-varid'>k</span><span class='hs-layout'>,</span> <span class='hs-conid'>Ord</span> <span class='hs-varid'>v</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>Algebra</span> <span class='hs-varid'>k</span> <span class='hs-layout'>(</span><span class='hs-conid'>NonComMonomial</span> <span class='hs-varid'>v</span><span class='hs-layout'>)</span> <span class='hs-keyword'>where</span>
<a name="line-35"></a> <span class='hs-varid'>unit</span> <span class='hs-num'>0</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>zerov</span> <span class='hs-comment'>-- V []</span>
<a name="line-36"></a> <span class='hs-varid'>unit</span> <span class='hs-varid'>x</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>V</span> <span class='hs-keyglyph'>[</span><span class='hs-layout'>(</span><span class='hs-varid'>munit</span><span class='hs-layout'>,</span><span class='hs-varid'>x</span><span class='hs-layout'>)</span><span class='hs-keyglyph'>]</span>
<a name="line-37"></a> <span class='hs-varid'>mult</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>nf</span> <span class='hs-varop'>.</span> <span class='hs-varid'>fmap</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-layout'>,</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-varop'>`mmult`</span> <span class='hs-varid'>b</span><span class='hs-layout'>)</span>
<a name="line-38"></a>
<a name="line-39"></a><span class='hs-comment'>{-
<a name="line-40"></a>-- This is the monoid algebra for non-commutative monomials (which is the free monoid)
<a name="line-41"></a>instance (Num k, Ord v) => Algebra k (NonComMonomial v) where
<a name="line-42"></a> unit 0 = zero -- V []
<a name="line-43"></a> unit x = V [(munit,x)] where munit = NCM 0 []
<a name="line-44"></a> mult (V ts) = nf $ fmap (\(a,b) -> a `mmult` b) (V ts)
<a name="line-45"></a> where mmult (NCM lu us) (NCM lv vs) = NCM (lu+lv) (us++vs)
<a name="line-46"></a> -- mult (V ts) = nf $ V [(a `mmult` b, x) | (T a b, x) <- ts]
<a name="line-47"></a>-}</span>
<a name="line-48"></a>
<a name="line-49"></a><span class='hs-comment'>{-
<a name="line-50"></a>-- This is just the Set Coalgebra, so better to use a generic instance
<a name="line-51"></a>-- Also, not used anywhere. Hence commented out
<a name="line-52"></a>instance Num k => Coalgebra k (NonComMonomial v) where
<a name="line-53"></a> counit (V ts) = sum [x | (m,x) <- ts] -- trace
<a name="line-54"></a> comult = fmap (\m -> (m,m))
<a name="line-55"></a>-}</span>
<a name="line-56"></a>
<a name="line-57"></a>
<a name="line-58"></a><span class='hs-keyword'>class</span> <span class='hs-conid'>Monomial</span> <span class='hs-varid'>m</span> <span class='hs-keyword'>where</span>
<a name="line-59"></a> <span class='hs-varid'>var</span> <span class='hs-keyglyph'>::</span> <span class='hs-varid'>v</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Vect</span> <span class='hs-conid'>Q</span> <span class='hs-layout'>(</span><span class='hs-varid'>m</span> <span class='hs-varid'>v</span><span class='hs-layout'>)</span>
<a name="line-60"></a> <span class='hs-varid'>powers</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Eq</span> <span class='hs-varid'>v</span> <span class='hs-keyglyph'>=></span> <span class='hs-varid'>m</span> <span class='hs-varid'>v</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-layout'>(</span><span class='hs-varid'>v</span><span class='hs-layout'>,</span><span class='hs-conid'>Int</span><span class='hs-layout'>)</span><span class='hs-keyglyph'>]</span>
<a name="line-61"></a><span class='hs-comment'>-- why do we need "powers"??</span>
<a name="line-62"></a>
<a name="line-63"></a><span class='hs-conid'>V</span> <span class='hs-varid'>ts</span> <span class='hs-varop'>`bind`</span> <span class='hs-varid'>f</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>sum</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>c</span> <span class='hs-varop'>*></span> <span class='hs-varid'>product</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'>i</span> <span class='hs-keyglyph'>|</span> <span class='hs-layout'>(</span><span class='hs-varid'>x</span><span class='hs-layout'>,</span><span class='hs-varid'>i</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>powers</span> <span class='hs-varid'>m</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>|</span> <span class='hs-layout'>(</span><span class='hs-varid'>m</span><span class='hs-layout'>,</span> <span class='hs-varid'>c</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>ts</span><span class='hs-keyglyph'>]</span>
<a name="line-64"></a><span class='hs-comment'>-- flipbind f = linear (\m -> product [f x ^ i | (x,i) <- powers m])</span>
<a name="line-65"></a>
<a name="line-66"></a><a name="instance%20Monomial%20NonComMonomial"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>Monomial</span> <span class='hs-conid'>NonComMonomial</span> <span class='hs-keyword'>where</span>
<a name="line-67"></a> <span class='hs-varid'>var</span> <span class='hs-varid'>v</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>V</span> <span class='hs-keyglyph'>[</span><span class='hs-layout'>(</span><span class='hs-conid'>NCM</span> <span class='hs-num'>1</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>v</span><span class='hs-keyglyph'>]</span><span class='hs-layout'>,</span><span class='hs-num'>1</span><span class='hs-layout'>)</span><span class='hs-keyglyph'>]</span>
<a name="line-68"></a> <span class='hs-varid'>powers</span> <span class='hs-layout'>(</span><span class='hs-conid'>NCM</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>vs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>map</span> <span class='hs-varid'>power</span> <span class='hs-layout'>(</span><span class='hs-conid'>L</span><span class='hs-varop'>.</span><span class='hs-varid'>group</span> <span class='hs-varid'>vs</span><span class='hs-layout'>)</span>
<a name="line-69"></a> <span class='hs-keyword'>where</span> <span class='hs-varid'>power</span> <span class='hs-varid'>vs</span><span class='hs-keyglyph'>@</span><span class='hs-layout'>(</span><span class='hs-varid'>v</span><span class='hs-conop'>:</span><span class='hs-keyword'>_</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-varid'>v</span><span class='hs-layout'>,</span><span class='hs-varid'>length</span> <span class='hs-varid'>vs</span><span class='hs-layout'>)</span>
<a name="line-70"></a>
<a name="line-71"></a>
<a name="line-72"></a><a name="NCPoly"></a><span class='hs-keyword'>type</span> <span class='hs-conid'>NCPoly</span> <span class='hs-varid'>v</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Vect</span> <span class='hs-conid'>Q</span> <span class='hs-layout'>(</span><span class='hs-conid'>NonComMonomial</span> <span class='hs-varid'>v</span><span class='hs-layout'>)</span>
<a name="line-73"></a>
<a name="line-74"></a><span class='hs-comment'>{-
<a name="line-75"></a>x,y,z :: NCPoly String
<a name="line-76"></a>x = var "x"
<a name="line-77"></a>y = var "y"
<a name="line-78"></a>z = var "z"
<a name="line-79"></a>-}</span>
<a name="line-80"></a>
<a name="line-81"></a>
<a name="line-82"></a><span class='hs-comment'>-- DIVISION</span>
<a name="line-83"></a>
<a name="line-84"></a><a name="DivisionBasis"></a><span class='hs-keyword'>class</span> <span class='hs-conid'>DivisionBasis</span> <span class='hs-varid'>m</span> <span class='hs-keyword'>where</span>
<a name="line-85"></a> <span class='hs-varid'>divM</span> <span class='hs-keyglyph'>::</span> <span class='hs-varid'>m</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>m</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Maybe</span> <span class='hs-layout'>(</span><span class='hs-varid'>m</span><span class='hs-layout'>,</span><span class='hs-varid'>m</span><span class='hs-layout'>)</span>
<a name="line-86"></a> <span class='hs-comment'>-- divM a b tries to find l, r such that a = lbr</span>
<a name="line-87"></a><span class='hs-comment'>{-
<a name="line-88"></a> findOverlap :: m -> m -> Maybe (m,m,m)
<a name="line-89"></a> -- given two monomials f g, find if possible a,b,c with f=ab g=bc
<a name="line-90"></a>-}</span>
<a name="line-91"></a>
<a name="line-92"></a><a name="instance%20DivisionBasis%20(NonComMonomial%20v)"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>Eq</span> <span class='hs-varid'>v</span> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>DivisionBasis</span> <span class='hs-layout'>(</span><span class='hs-conid'>NonComMonomial</span> <span class='hs-varid'>v</span><span class='hs-layout'>)</span> <span class='hs-keyword'>where</span>
<a name="line-93"></a> <span class='hs-varid'>divM</span> <span class='hs-layout'>(</span><span class='hs-conid'>NCM</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-conid'>NCM</span> <span class='hs-keyword'>_</span> <span class='hs-varid'>b</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>divM'</span> <span class='hs-conid'>[]</span> <span class='hs-varid'>a</span> <span class='hs-keyword'>where</span>
<a name="line-94"></a> <span class='hs-varid'>divM'</span> <span class='hs-varid'>ls</span> <span class='hs-layout'>(</span><span class='hs-varid'>r</span><span class='hs-conop'>:</span><span class='hs-varid'>rs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span>
<a name="line-95"></a> <span class='hs-keyword'>if</span> <span class='hs-varid'>b</span> <span class='hs-varop'>`</span><span class='hs-conid'>L</span><span class='hs-varop'>.</span><span class='hs-varid'>isPrefixOf</span><span class='hs-varop'>`</span> <span class='hs-layout'>(</span><span class='hs-varid'>r</span><span class='hs-conop'>:</span><span class='hs-varid'>rs</span><span class='hs-layout'>)</span>
<a name="line-96"></a> <span class='hs-keyword'>then</span> <span class='hs-conid'>Just</span> <span class='hs-layout'>(</span><span class='hs-varid'>ncm</span> <span class='hs-varop'>$</span> <span class='hs-varid'>reverse</span> <span class='hs-varid'>ls</span><span class='hs-layout'>,</span> <span class='hs-varid'>ncm</span> <span class='hs-varop'>$</span> <span class='hs-varid'>drop</span> <span class='hs-layout'>(</span><span class='hs-varid'>length</span> <span class='hs-varid'>b</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>r</span><span class='hs-conop'>:</span><span class='hs-varid'>rs</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
<a name="line-97"></a> <span class='hs-keyword'>else</span> <span class='hs-varid'>divM'</span> <span class='hs-layout'>(</span><span class='hs-varid'>r</span><span class='hs-conop'>:</span><span class='hs-varid'>ls</span><span class='hs-layout'>)</span> <span class='hs-varid'>rs</span>
<a name="line-98"></a> <span class='hs-varid'>divM'</span> <span class='hs-keyword'>_</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>Nothing</span>
<a name="line-99"></a><a name="ncm"></a><span class='hs-comment'>{-
<a name="line-100"></a> findOverlap (NCM _ xs) (NCM _ ys) = findOverlap' [] xs ys where
<a name="line-101"></a> findOverlap' as [] cs = Nothing -- (reverse as, [], cs)
<a name="line-102"></a> findOverlap' as (b:bs) cs =
<a name="line-103"></a> if (b:bs) `L.isPrefixOf` cs
<a name="line-104"></a> then Just (ncm $ reverse as, ncm $ b:bs, ncm $ drop (length (b:bs)) cs)
<a name="line-105"></a> else findOverlap' (b:as) bs cs
<a name="line-106"></a>-}</span>
<a name="line-107"></a><span class='hs-definition'>ncm</span> <span class='hs-varid'>xs</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>NCM</span> <span class='hs-layout'>(</span><span class='hs-varid'>length</span> <span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-varid'>xs</span>
<a name="line-108"></a>
<a name="line-109"></a><a name="lm"></a><span class='hs-definition'>lm</span> <span class='hs-layout'>(</span><span class='hs-conid'>V</span> <span class='hs-layout'>(</span><span class='hs-layout'>(</span><span class='hs-varid'>m</span><span class='hs-layout'>,</span><span class='hs-varid'>c</span><span class='hs-layout'>)</span><span class='hs-conop'>:</span><span class='hs-varid'>ts</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>m</span>
<a name="line-110"></a><a name="lc"></a><span class='hs-definition'>lc</span> <span class='hs-layout'>(</span><span class='hs-conid'>V</span> <span class='hs-layout'>(</span><span class='hs-layout'>(</span><span class='hs-varid'>m</span><span class='hs-layout'>,</span><span class='hs-varid'>c</span><span class='hs-layout'>)</span><span class='hs-conop'>:</span><span class='hs-varid'>ts</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>c</span>
<a name="line-111"></a><a name="lt"></a><span class='hs-definition'>lt</span> <span class='hs-layout'>(</span><span class='hs-conid'>V</span> <span class='hs-layout'>(</span><span class='hs-varid'>t</span><span class='hs-conop'>:</span><span class='hs-varid'>ts</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>V</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>t</span><span class='hs-keyglyph'>]</span>
<a name="line-112"></a>
<a name="line-113"></a><a name="quotRemNP"></a><span class='hs-comment'>-- given f, gs, find ls, rs, f' such that f = sum (zipWith3 (*) ls gs rs) + f', with f' not divisible by any g</span>
<a name="line-114"></a><span class='hs-definition'>quotRemNP</span> <span class='hs-varid'>f</span> <span class='hs-varid'>gs</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>all</span> <span class='hs-layout'>(</span><span class='hs-varop'>/=</span><span class='hs-num'>0</span><span class='hs-layout'>)</span> <span class='hs-varid'>gs</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>quotRemNP'</span> <span class='hs-varid'>f</span> <span class='hs-layout'>(</span><span class='hs-varid'>replicate</span> <span class='hs-varid'>n</span> <span class='hs-layout'>(</span><span class='hs-num'>0</span><span class='hs-layout'>,</span><span class='hs-num'>0</span><span class='hs-layout'>)</span><span class='hs-layout'>,</span> <span class='hs-num'>0</span><span class='hs-layout'>)</span>
<a name="line-115"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>error</span> <span class='hs-str'>"quotRemNP: division by zero"</span>
<a name="line-116"></a> <span class='hs-keyword'>where</span>
<a name="line-117"></a> <span class='hs-varid'>n</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>length</span> <span class='hs-varid'>gs</span>
<a name="line-118"></a> <span class='hs-varid'>quotRemNP'</span> <span class='hs-num'>0</span> <span class='hs-layout'>(</span><span class='hs-varid'>lrs</span><span class='hs-layout'>,</span><span class='hs-varid'>f'</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-varid'>lrs</span><span class='hs-layout'>,</span><span class='hs-varid'>f'</span><span class='hs-layout'>)</span>
<a name="line-119"></a> <span class='hs-varid'>quotRemNP'</span> <span class='hs-varid'>h</span> <span class='hs-layout'>(</span><span class='hs-varid'>lrs</span><span class='hs-layout'>,</span><span class='hs-varid'>f'</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>divisionStep</span> <span class='hs-varid'>h</span> <span class='hs-layout'>(</span><span class='hs-varid'>gs</span><span class='hs-layout'>,</span><span class='hs-conid'>[]</span><span class='hs-layout'>,</span><span class='hs-varid'>lrs</span><span class='hs-layout'>,</span><span class='hs-varid'>f'</span><span class='hs-layout'>)</span>
<a name="line-120"></a> <span class='hs-varid'>divisionStep</span> <span class='hs-varid'>h</span> <span class='hs-layout'>(</span><span class='hs-varid'>g</span><span class='hs-conop'>:</span><span class='hs-varid'>gs</span><span class='hs-layout'>,</span> <span class='hs-varid'>lrs'</span><span class='hs-layout'>,</span> <span class='hs-layout'>(</span><span class='hs-varid'>l</span><span class='hs-layout'>,</span><span class='hs-varid'>r</span><span class='hs-layout'>)</span><span class='hs-conop'>:</span><span class='hs-varid'>lrs</span><span class='hs-layout'>,</span> <span class='hs-varid'>f'</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span>
<a name="line-121"></a> <span class='hs-keyword'>case</span> <span class='hs-varid'>lm</span> <span class='hs-varid'>h</span> <span class='hs-varop'>`divM`</span> <span class='hs-varid'>lm</span> <span class='hs-varid'>g</span> <span class='hs-keyword'>of</span>
<a name="line-122"></a> <span class='hs-conid'>Just</span> <span class='hs-layout'>(</span><span class='hs-varid'>l'</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-keyword'>let</span> <span class='hs-varid'>l''</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>V</span> <span class='hs-keyglyph'>[</span><span class='hs-layout'>(</span><span class='hs-varid'>l'</span><span class='hs-layout'>,</span><span class='hs-varid'>lc</span> <span class='hs-varid'>h</span> <span class='hs-varop'>/</span> <span class='hs-varid'>lc</span> <span class='hs-varid'>g</span><span class='hs-layout'>)</span><span class='hs-keyglyph'>]</span>
<a name="line-123"></a> <span class='hs-varid'>r''</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>V</span> <span class='hs-keyglyph'>[</span><span class='hs-layout'>(</span><span class='hs-varid'>r'</span><span class='hs-layout'>,</span><span class='hs-num'>1</span><span class='hs-layout'>)</span><span class='hs-keyglyph'>]</span>
<a name="line-124"></a> <span class='hs-varid'>h'</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>h</span> <span class='hs-comment'>-</span> <span class='hs-varid'>l''</span> <span class='hs-varop'>*</span> <span class='hs-varid'>g</span> <span class='hs-varop'>*</span> <span class='hs-varid'>r''</span>
<a name="line-125"></a> <span class='hs-keyword'>in</span> <span class='hs-varid'>quotRemNP'</span> <span class='hs-varid'>h'</span> <span class='hs-layout'>(</span><span class='hs-varid'>reverse</span> <span class='hs-varid'>lrs'</span> <span class='hs-varop'>++</span> <span class='hs-layout'>(</span><span class='hs-varid'>l</span><span class='hs-varop'>+</span><span class='hs-varid'>l''</span><span class='hs-layout'>,</span><span class='hs-varid'>r</span><span class='hs-varop'>+</span><span class='hs-varid'>r''</span><span class='hs-layout'>)</span><span class='hs-conop'>:</span><span class='hs-varid'>lrs</span><span class='hs-layout'>,</span> <span class='hs-varid'>f'</span><span class='hs-layout'>)</span>
<a name="line-126"></a> <span class='hs-conid'>Nothing</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>divisionStep</span> <span class='hs-varid'>h</span> <span class='hs-layout'>(</span><span class='hs-varid'>gs</span><span class='hs-layout'>,</span><span class='hs-layout'>(</span><span class='hs-varid'>l</span><span class='hs-layout'>,</span><span class='hs-varid'>r</span><span class='hs-layout'>)</span><span class='hs-conop'>:</span><span class='hs-varid'>lrs'</span><span class='hs-layout'>,</span><span class='hs-varid'>lrs</span><span class='hs-layout'>,</span><span class='hs-varid'>f'</span><span class='hs-layout'>)</span>
<a name="line-127"></a> <span class='hs-varid'>divisionStep</span> <span class='hs-varid'>h</span> <span class='hs-layout'>(</span><span class='hs-conid'>[]</span><span class='hs-layout'>,</span><span class='hs-varid'>lrs'</span><span class='hs-layout'>,</span><span class='hs-conid'>[]</span><span class='hs-layout'>,</span><span class='hs-varid'>f'</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span>
<a name="line-128"></a> <span class='hs-keyword'>let</span> <span class='hs-varid'>lth</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>lt</span> <span class='hs-varid'>h</span> <span class='hs-comment'>-- can't reduce lt h, so add it to the remainder and try to reduce the remaining terms</span>
<a name="line-129"></a> <span class='hs-keyword'>in</span> <span class='hs-varid'>quotRemNP'</span> <span class='hs-layout'>(</span><span class='hs-varid'>h</span><span class='hs-comment'>-</span><span class='hs-varid'>lth</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>reverse</span> <span class='hs-varid'>lrs'</span><span class='hs-layout'>,</span> <span class='hs-varid'>f'</span><span class='hs-varop'>+</span><span class='hs-varid'>lth</span><span class='hs-layout'>)</span>
<a name="line-130"></a>
<a name="line-131"></a><a name="remNP"></a><span class='hs-comment'>-- It is only marginally (5-10%) more space/time efficient not to track the (lazily unevaluated) factors</span>
<a name="line-132"></a><span class='hs-definition'>remNP</span> <span class='hs-varid'>f</span> <span class='hs-varid'>gs</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>all</span> <span class='hs-layout'>(</span><span class='hs-varop'>/=</span><span class='hs-num'>0</span><span class='hs-layout'>)</span> <span class='hs-varid'>gs</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>remNP'</span> <span class='hs-varid'>f</span> <span class='hs-num'>0</span>
<a name="line-133"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>error</span> <span class='hs-str'>"remNP: division by zero"</span>
<a name="line-134"></a> <span class='hs-keyword'>where</span>
<a name="line-135"></a> <span class='hs-varid'>n</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>length</span> <span class='hs-varid'>gs</span>
<a name="line-136"></a> <span class='hs-varid'>remNP'</span> <span class='hs-num'>0</span> <span class='hs-varid'>f'</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>f'</span>
<a name="line-137"></a> <span class='hs-varid'>remNP'</span> <span class='hs-varid'>h</span> <span class='hs-varid'>f'</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>divisionStep</span> <span class='hs-varid'>h</span> <span class='hs-varid'>gs</span> <span class='hs-varid'>f'</span>
<a name="line-138"></a> <span class='hs-varid'>divisionStep</span> <span class='hs-varid'>h</span> <span class='hs-layout'>(</span><span class='hs-varid'>g</span><span class='hs-conop'>:</span><span class='hs-varid'>gs</span><span class='hs-layout'>)</span> <span class='hs-varid'>f'</span> <span class='hs-keyglyph'>=</span>
<a name="line-139"></a> <span class='hs-keyword'>case</span> <span class='hs-varid'>lm</span> <span class='hs-varid'>h</span> <span class='hs-varop'>`divM`</span> <span class='hs-varid'>lm</span> <span class='hs-varid'>g</span> <span class='hs-keyword'>of</span>
<a name="line-140"></a> <span class='hs-conid'>Just</span> <span class='hs-layout'>(</span><span class='hs-varid'>l'</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-keyword'>let</span> <span class='hs-varid'>l''</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>V</span> <span class='hs-keyglyph'>[</span><span class='hs-layout'>(</span><span class='hs-varid'>l'</span><span class='hs-layout'>,</span><span class='hs-varid'>lc</span> <span class='hs-varid'>h</span> <span class='hs-varop'>/</span> <span class='hs-varid'>lc</span> <span class='hs-varid'>g</span><span class='hs-layout'>)</span><span class='hs-keyglyph'>]</span>
<a name="line-141"></a> <span class='hs-varid'>r''</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>V</span> <span class='hs-keyglyph'>[</span><span class='hs-layout'>(</span><span class='hs-varid'>r'</span><span class='hs-layout'>,</span><span class='hs-num'>1</span><span class='hs-layout'>)</span><span class='hs-keyglyph'>]</span>
<a name="line-142"></a> <span class='hs-varid'>h'</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>h</span> <span class='hs-comment'>-</span> <span class='hs-varid'>l''</span> <span class='hs-varop'>*</span> <span class='hs-varid'>g</span> <span class='hs-varop'>*</span> <span class='hs-varid'>r''</span>
<a name="line-143"></a> <span class='hs-keyword'>in</span> <span class='hs-varid'>remNP'</span> <span class='hs-varid'>h'</span> <span class='hs-varid'>f'</span>
<a name="line-144"></a> <span class='hs-conid'>Nothing</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>divisionStep</span> <span class='hs-varid'>h</span> <span class='hs-varid'>gs</span> <span class='hs-varid'>f'</span>
<a name="line-145"></a> <span class='hs-varid'>divisionStep</span> <span class='hs-varid'>h</span> <span class='hs-conid'>[]</span> <span class='hs-varid'>f'</span> <span class='hs-keyglyph'>=</span>
<a name="line-146"></a> <span class='hs-keyword'>let</span> <span class='hs-varid'>lth</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>lt</span> <span class='hs-varid'>h</span> <span class='hs-comment'>-- can't reduce lt h, so add it to the remainder and try to reduce the remaining terms</span>
<a name="line-147"></a> <span class='hs-keyword'>in</span> <span class='hs-varid'>remNP'</span> <span class='hs-layout'>(</span><span class='hs-varid'>h</span><span class='hs-comment'>-</span><span class='hs-varid'>lth</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>f'</span><span class='hs-varop'>+</span><span class='hs-varid'>lth</span><span class='hs-layout'>)</span>
<a name="line-148"></a>
<a name="line-149"></a><span class='hs-keyword'>infixl</span> <span class='hs-num'>7</span> <span class='hs-varop'>%%</span>
<a name="line-150"></a><a name="%25%25"></a><span class='hs-comment'>-- f %% gs = r where (_,r) = quotRemNP f gs</span>
<a name="line-151"></a><a name="f"></a><span class='hs-definition'>f</span> <span class='hs-varop'>%%</span> <span class='hs-varid'>gs</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>remNP</span> <span class='hs-varid'>f</span> <span class='hs-varid'>gs</span>
<a name="line-152"></a>
</pre></body>
</html>
|