/usr/share/doc/libghc-flexible-defaults-doc/html/src/Language-Haskell-TH-FlexibleDefaults-Solve.html is in libghc-flexible-defaults-doc 0.0.1.2-3.
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 | <?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>src/Language/Haskell/TH/FlexibleDefaults/Solve.hs</title>
<link type='text/css' rel='stylesheet' href='hscolour.css' />
</head>
<body>
<pre><a name="line-1"></a><span class='hs-keyword'>module</span> <span class='hs-conid'>Language</span><span class='hs-varop'>.</span><span class='hs-conid'>Haskell</span><span class='hs-varop'>.</span><span class='hs-conid'>TH</span><span class='hs-varop'>.</span><span class='hs-conid'>FlexibleDefaults</span><span class='hs-varop'>.</span><span class='hs-conid'>Solve</span>
<a name="line-2"></a> <span class='hs-layout'>(</span> <span class='hs-conid'>ImplSpec</span><span class='hs-layout'>(</span><span class='hs-keyglyph'>..</span><span class='hs-layout'>)</span>
<a name="line-3"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>scoreImplSpec</span>
<a name="line-4"></a> <span class='hs-layout'>,</span> <span class='hs-conid'>Problem</span>
<a name="line-5"></a> <span class='hs-layout'>,</span> <span class='hs-conid'>Solution</span>
<a name="line-6"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>scoreSolution</span>
<a name="line-7"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>chooseImplementations</span>
<a name="line-8"></a> <span class='hs-layout'>)</span> <span class='hs-keyword'>where</span>
<a name="line-9"></a>
<a name="line-10"></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-varid'>all</span><span class='hs-layout'>)</span>
<a name="line-11"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>Foldable</span> <span class='hs-layout'>(</span><span class='hs-varid'>all</span><span class='hs-layout'>)</span>
<a name="line-12"></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-13"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>Monoid</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'>Map</span> <span class='hs-keyword'>as</span> <span class='hs-conid'>M</span>
<a name="line-15"></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'>Set</span> <span class='hs-keyword'>as</span> <span class='hs-conid'>S</span>
<a name="line-16"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Language</span><span class='hs-varop'>.</span><span class='hs-conid'>Haskell</span><span class='hs-varop'>.</span><span class='hs-conid'>TH</span>
<a name="line-17"></a>
<a name="line-18"></a><a name="ImplSpec"></a><span class='hs-keyword'>data</span> <span class='hs-conid'>ImplSpec</span> <span class='hs-varid'>s</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>ImplSpec</span>
<a name="line-19"></a> <span class='hs-layout'>{</span> <span class='hs-varid'>implScore</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Maybe</span> <span class='hs-varid'>s</span>
<a name="line-20"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>dependencies</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>S</span><span class='hs-varop'>.</span><span class='hs-conid'>Set</span> <span class='hs-conid'>String</span>
<a name="line-21"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>definition</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Q</span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Dec</span><span class='hs-keyglyph'>]</span>
<a name="line-22"></a> <span class='hs-layout'>}</span>
<a name="line-23"></a>
<a name="line-24"></a><a name="instance%20Functor%20ImplSpec"></a><span class='hs-keyword'>instance</span> <span class='hs-conid'>Functor</span> <span class='hs-conid'>ImplSpec</span> <span class='hs-keyword'>where</span>
<a name="line-25"></a> <span class='hs-varid'>fmap</span> <span class='hs-varid'>f</span> <span class='hs-varid'>s</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>s</span> <span class='hs-layout'>{</span><span class='hs-varid'>implScore</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>fmap</span> <span class='hs-varid'>f</span> <span class='hs-layout'>(</span><span class='hs-varid'>implScore</span> <span class='hs-varid'>s</span><span class='hs-layout'>)</span><span class='hs-layout'>}</span>
<a name="line-26"></a>
<a name="line-27"></a><a name="Problem"></a><span class='hs-keyword'>type</span> <span class='hs-conid'>Problem</span> <span class='hs-varid'>s</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>M</span><span class='hs-varop'>.</span><span class='hs-conid'>Map</span> <span class='hs-conid'>String</span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>ImplSpec</span> <span class='hs-varid'>s</span><span class='hs-keyglyph'>]</span>
<a name="line-28"></a><a name="Solution"></a><span class='hs-keyword'>type</span> <span class='hs-conid'>Solution</span> <span class='hs-varid'>s</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>M</span><span class='hs-varop'>.</span><span class='hs-conid'>Map</span> <span class='hs-conid'>String</span> <span class='hs-layout'>(</span><span class='hs-conid'>ImplSpec</span> <span class='hs-varid'>s</span><span class='hs-layout'>)</span>
<a name="line-29"></a>
<a name="line-30"></a><a name="scoreImplSpec"></a><span class='hs-definition'>scoreImplSpec</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Monoid</span> <span class='hs-varid'>s</span> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>ImplSpec</span> <span class='hs-varid'>s</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>s</span>
<a name="line-31"></a><span class='hs-definition'>scoreImplSpec</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>fromMaybe</span> <span class='hs-varid'>mempty</span> <span class='hs-varop'>.</span> <span class='hs-varid'>implScore</span>
<a name="line-32"></a>
<a name="line-33"></a><a name="scoreSolution"></a><span class='hs-definition'>scoreSolution</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Monoid</span> <span class='hs-varid'>s</span> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>Solution</span> <span class='hs-varid'>s</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>s</span>
<a name="line-34"></a><span class='hs-definition'>scoreSolution</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>mconcat</span> <span class='hs-varop'>.</span> <span class='hs-varid'>map</span> <span class='hs-varid'>scoreImplSpec</span> <span class='hs-varop'>.</span> <span class='hs-conid'>M</span><span class='hs-varop'>.</span><span class='hs-varid'>elems</span>
<a name="line-35"></a>
<a name="line-36"></a><a name="chooseImplementations"></a><span class='hs-comment'>-- Find all feasible solutions. This is not particularly efficient but I believe</span>
<a name="line-37"></a><span class='hs-comment'>-- it works and is correct. At any given point, the solution set is well-founded:</span>
<a name="line-38"></a><span class='hs-comment'>-- initially, it is those functions which have direct implementations. At each</span>
<a name="line-39"></a><span class='hs-comment'>-- step it adds an implementation which only depends upon already-implemented</span>
<a name="line-40"></a><span class='hs-comment'>-- functions.</span>
<a name="line-41"></a><span class='hs-comment'>--</span>
<a name="line-42"></a><span class='hs-comment'>-- Considers all possible orderings of resolutions, which means this takes</span>
<a name="line-43"></a><span class='hs-comment'>-- O(n!) time, where 'n' is the number of missing functions.</span>
<a name="line-44"></a><span class='hs-definition'>chooseImplementations</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Problem</span> <span class='hs-varid'>s</span> <span class='hs-keyglyph'>-></span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>Solution</span> <span class='hs-varid'>s</span><span class='hs-keyglyph'>]</span>
<a name="line-45"></a><span class='hs-definition'>chooseImplementations</span> <span class='hs-varid'>unimplemented</span>
<a name="line-46"></a> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>M</span><span class='hs-varop'>.</span><span class='hs-varid'>null</span> <span class='hs-varid'>unimplemented</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyglyph'>[</span><span class='hs-conid'>M</span><span class='hs-varop'>.</span><span class='hs-varid'>empty</span><span class='hs-keyglyph'>]</span>
<a name="line-47"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>do</span>
<a name="line-48"></a> <span class='hs-layout'>(</span><span class='hs-varid'>name</span><span class='hs-layout'>,</span> <span class='hs-varid'>impls</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'><-</span> <span class='hs-conid'>M</span><span class='hs-varop'>.</span><span class='hs-varid'>assocs</span> <span class='hs-varid'>unimplemented</span>
<a name="line-49"></a> <span class='hs-keyword'>let</span> <span class='hs-varid'>newUnimplemented</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>M</span><span class='hs-varop'>.</span><span class='hs-varid'>delete</span> <span class='hs-varid'>name</span> <span class='hs-varid'>unimplemented</span>
<a name="line-50"></a> <span class='hs-varid'>implemented</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>not</span> <span class='hs-varop'>.</span> <span class='hs-varid'>flip</span> <span class='hs-conid'>M</span><span class='hs-varop'>.</span><span class='hs-varid'>member</span> <span class='hs-varid'>newUnimplemented</span>
<a name="line-51"></a> <span class='hs-varid'>impl</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>take</span> <span class='hs-num'>1</span> <span class='hs-layout'>(</span><span class='hs-varid'>filter</span> <span class='hs-layout'>(</span><span class='hs-varid'>all</span> <span class='hs-varid'>implemented</span> <span class='hs-varop'>.</span> <span class='hs-varid'>dependencies</span><span class='hs-layout'>)</span> <span class='hs-varid'>impls</span><span class='hs-layout'>)</span>
<a name="line-52"></a> <span class='hs-varid'>otherImpls</span> <span class='hs-keyglyph'><-</span> <span class='hs-varid'>chooseImplementations</span> <span class='hs-varid'>newUnimplemented</span>
<a name="line-53"></a> <span class='hs-varid'>return</span> <span class='hs-layout'>(</span><span class='hs-conid'>M</span><span class='hs-varop'>.</span><span class='hs-varid'>insert</span> <span class='hs-varid'>name</span> <span class='hs-varid'>impl</span> <span class='hs-varid'>otherImpls</span><span class='hs-layout'>)</span>
<a name="line-54"></a>
</pre></body>
</html>
|