/usr/share/doc/libghc-data-memocombinators-doc/html/src/Data-MemoCombinators.html is in libghc-data-memocombinators-doc 0.5.1-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 164 165 166 | <?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/MemoCombinators.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.MemoCombinators</span>
<a name="line-4"></a><span class='hs-comment'>-- Copyright : (c) Luke Palmer 2008-2010</span>
<a name="line-5"></a><span class='hs-comment'>-- License : BSD3</span>
<a name="line-6"></a><span class='hs-comment'>--</span>
<a name="line-7"></a><span class='hs-comment'>-- Maintainer : Luke Palmer <lrpalmer@gmail.com></span>
<a name="line-8"></a><span class='hs-comment'>-- Stability : experimental</span>
<a name="line-9"></a><span class='hs-comment'>--</span>
<a name="line-10"></a><span class='hs-comment'>-- This module provides combinators for building memo tables</span>
<a name="line-11"></a><span class='hs-comment'>-- over various data types, so that the type of table can</span>
<a name="line-12"></a><span class='hs-comment'>-- be customized depending on the application.</span>
<a name="line-13"></a><span class='hs-comment'>--</span>
<a name="line-14"></a><span class='hs-comment'>-- This module is designed to be imported /qualified/, eg.</span>
<a name="line-15"></a><span class='hs-comment'>--</span>
<a name="line-16"></a><span class='hs-comment'>-- > import qualified Data.MemoCombinators as Memo</span>
<a name="line-17"></a><span class='hs-comment'>--</span>
<a name="line-18"></a><span class='hs-comment'>-- Usage is straightforward: apply an object of type @Memo a@</span>
<a name="line-19"></a><span class='hs-comment'>-- to a function of type @a -> b@, and get a memoized function</span>
<a name="line-20"></a><span class='hs-comment'>-- of type @a -> b@. For example:</span>
<a name="line-21"></a><span class='hs-comment'>--</span>
<a name="line-22"></a><span class='hs-comment'>-- > fib = Memo.integral fib'</span>
<a name="line-23"></a><span class='hs-comment'>-- > where</span>
<a name="line-24"></a><span class='hs-comment'>-- > fib' 0 = 0</span>
<a name="line-25"></a><span class='hs-comment'>-- > fib' 1 = 1</span>
<a name="line-26"></a><span class='hs-comment'>-- > fib' x = fib (x-1) + fib (x-2)</span>
<a name="line-27"></a><span class='hs-comment'>------------------------------------------------</span>
<a name="line-28"></a>
<a name="line-29"></a><span class='hs-keyword'>module</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>MemoCombinators</span>
<a name="line-30"></a> <span class='hs-layout'>(</span> <span class='hs-conid'>Memo</span>
<a name="line-31"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>wrap</span>
<a name="line-32"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>memo2</span><span class='hs-layout'>,</span> <span class='hs-varid'>memo3</span><span class='hs-layout'>,</span> <span class='hs-varid'>memoSecond</span><span class='hs-layout'>,</span> <span class='hs-varid'>memoThird</span>
<a name="line-33"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>bool</span><span class='hs-layout'>,</span> <span class='hs-varid'>char</span><span class='hs-layout'>,</span> <span class='hs-varid'>list</span><span class='hs-layout'>,</span> <span class='hs-varid'>boundedList</span><span class='hs-layout'>,</span> <span class='hs-varid'>either</span><span class='hs-layout'>,</span> <span class='hs-varid'>maybe</span><span class='hs-layout'>,</span> <span class='hs-varid'>unit</span><span class='hs-layout'>,</span> <span class='hs-varid'>pair</span>
<a name="line-34"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>enum</span><span class='hs-layout'>,</span> <span class='hs-varid'>integral</span><span class='hs-layout'>,</span> <span class='hs-varid'>bits</span>
<a name="line-35"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>switch</span>
<a name="line-36"></a> <span class='hs-layout'>,</span> <span class='hs-conid'>RangeMemo</span>
<a name="line-37"></a> <span class='hs-layout'>,</span> <span class='hs-varid'>arrayRange</span><span class='hs-layout'>,</span> <span class='hs-varid'>unsafeArrayRange</span><span class='hs-layout'>,</span> <span class='hs-varid'>chunks</span>
<a name="line-38"></a> <span class='hs-layout'>)</span>
<a name="line-39"></a><span class='hs-keyword'>where</span>
<a name="line-40"></a>
<a name="line-41"></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'>either</span><span class='hs-layout'>,</span> <span class='hs-varid'>maybe</span><span class='hs-layout'>)</span>
<a name="line-42"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>Bits</span>
<a name="line-43"></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'>Array</span> <span class='hs-keyword'>as</span> <span class='hs-conid'>Array</span>
<a name="line-44"></a><span class='hs-keyword'>import</span> <span class='hs-conid'>Data</span><span class='hs-varop'>.</span><span class='hs-conid'>Char</span> <span class='hs-layout'>(</span><span class='hs-varid'>ord</span><span class='hs-layout'>,</span><span class='hs-varid'>chr</span><span class='hs-layout'>)</span>
<a name="line-45"></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'>IntTrie</span> <span class='hs-keyword'>as</span> <span class='hs-conid'>IntTrie</span>
<a name="line-46"></a>
<a name="line-47"></a><a name="Memo"></a><span class='hs-comment'>-- | The type of a memo table for functions of a.</span>
<a name="line-48"></a><a name="Memo"></a><span class='hs-keyword'>type</span> <span class='hs-conid'>Memo</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>forall</span> <span class='hs-varid'>r</span><span class='hs-varop'>.</span> <span class='hs-layout'>(</span><span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>r</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'>r</span><span class='hs-layout'>)</span>
<a name="line-49"></a>
<a name="line-50"></a><a name="wrap"></a><span class='hs-comment'>-- | Given a memoizer for a and an isomorphism between a and b, build</span>
<a name="line-51"></a><span class='hs-comment'>-- a memoizer for b.</span>
<a name="line-52"></a><span class='hs-definition'>wrap</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-layout'>(</span><span class='hs-varid'>b</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-conid'>Memo</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Memo</span> <span class='hs-varid'>b</span>
<a name="line-53"></a><span class='hs-definition'>wrap</span> <span class='hs-varid'>i</span> <span class='hs-varid'>j</span> <span class='hs-varid'>m</span> <span class='hs-varid'>f</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>m</span> <span class='hs-layout'>(</span><span class='hs-varid'>f</span> <span class='hs-varop'>.</span> <span class='hs-varid'>i</span><span class='hs-layout'>)</span> <span class='hs-varop'>.</span> <span class='hs-varid'>j</span>
<a name="line-54"></a>
<a name="line-55"></a><a name="memo2"></a><span class='hs-comment'>-- | Memoize a two argument function (just apply the table directly for</span>
<a name="line-56"></a><span class='hs-comment'>-- single argument functions).</span>
<a name="line-57"></a><span class='hs-definition'>memo2</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Memo</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Memo</span> <span class='hs-varid'>b</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-keyglyph'>-></span> <span class='hs-varid'>r</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-keyglyph'>-></span> <span class='hs-varid'>r</span><span class='hs-layout'>)</span>
<a name="line-58"></a><span class='hs-definition'>memo2</span> <span class='hs-varid'>a</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-layout'>(</span><span class='hs-varid'>b</span> <span class='hs-varop'>.</span><span class='hs-layout'>)</span>
<a name="line-59"></a>
<a name="line-60"></a><a name="memo3"></a><span class='hs-comment'>-- | Memoize a three argument function.</span>
<a name="line-61"></a><span class='hs-definition'>memo3</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Memo</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Memo</span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Memo</span> <span class='hs-varid'>c</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-keyglyph'>-></span> <span class='hs-varid'>c</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>r</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-keyglyph'>-></span> <span class='hs-varid'>c</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>r</span><span class='hs-layout'>)</span>
<a name="line-62"></a><span class='hs-definition'>memo3</span> <span class='hs-varid'>a</span> <span class='hs-varid'>b</span> <span class='hs-varid'>c</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>a</span> <span class='hs-varop'>.</span> <span class='hs-layout'>(</span><span class='hs-varid'>memo2</span> <span class='hs-varid'>b</span> <span class='hs-varid'>c</span> <span class='hs-varop'>.</span><span class='hs-layout'>)</span>
<a name="line-63"></a>
<a name="line-64"></a><a name="memoSecond"></a><span class='hs-comment'>-- | Memoize the second argument of a function.</span>
<a name="line-65"></a><span class='hs-definition'>memoSecond</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Memo</span> <span class='hs-varid'>b</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-keyglyph'>-></span> <span class='hs-varid'>r</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-keyglyph'>-></span> <span class='hs-varid'>r</span><span class='hs-layout'>)</span>
<a name="line-66"></a><span class='hs-definition'>memoSecond</span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-varid'>b</span> <span class='hs-varop'>.</span><span class='hs-layout'>)</span>
<a name="line-67"></a>
<a name="line-68"></a><a name="memoThird"></a><span class='hs-comment'>-- | Memoize the third argument of a function.</span>
<a name="line-69"></a><span class='hs-definition'>memoThird</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Memo</span> <span class='hs-varid'>c</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-keyglyph'>-></span> <span class='hs-varid'>c</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>r</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-keyglyph'>-></span> <span class='hs-varid'>c</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>r</span><span class='hs-layout'>)</span>
<a name="line-70"></a><span class='hs-definition'>memoThird</span> <span class='hs-varid'>c</span> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-varid'>memoSecond</span> <span class='hs-varid'>c</span> <span class='hs-varop'>.</span><span class='hs-layout'>)</span>
<a name="line-71"></a>
<a name="line-72"></a><a name="bool"></a><span class='hs-definition'>bool</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Memo</span> <span class='hs-conid'>Bool</span>
<a name="line-73"></a><span class='hs-definition'>bool</span> <span class='hs-varid'>f</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>cond</span> <span class='hs-layout'>(</span><span class='hs-varid'>f</span> <span class='hs-conid'>True</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>f</span> <span class='hs-conid'>False</span><span class='hs-layout'>)</span>
<a name="line-74"></a> <span class='hs-keyword'>where</span>
<a name="line-75"></a> <span class='hs-varid'>cond</span> <span class='hs-varid'>t</span> <span class='hs-varid'>f</span> <span class='hs-conid'>True</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>t</span>
<a name="line-76"></a> <span class='hs-varid'>cond</span> <span class='hs-varid'>t</span> <span class='hs-varid'>f</span> <span class='hs-conid'>False</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>f</span>
<a name="line-77"></a>
<a name="line-78"></a><a name="list"></a><span class='hs-definition'>list</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Memo</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Memo</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span>
<a name="line-79"></a><span class='hs-definition'>list</span> <span class='hs-varid'>m</span> <span class='hs-varid'>f</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>table</span> <span class='hs-layout'>(</span><span class='hs-varid'>f</span> <span class='hs-conid'>[]</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-keyglyph'>\</span><span class='hs-varid'>x</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>list</span> <span class='hs-varid'>m</span> <span class='hs-layout'>(</span><span class='hs-varid'>f</span> <span class='hs-varop'>.</span> <span class='hs-layout'>(</span><span class='hs-varid'>x</span><span class='hs-conop'>:</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
<a name="line-80"></a> <span class='hs-keyword'>where</span>
<a name="line-81"></a> <span class='hs-varid'>table</span> <span class='hs-varid'>nil</span> <span class='hs-varid'>cons</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>nil</span>
<a name="line-82"></a> <span class='hs-varid'>table</span> <span class='hs-varid'>nil</span> <span class='hs-varid'>cons</span> <span class='hs-layout'>(</span><span class='hs-varid'>x</span><span class='hs-conop'>:</span><span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>cons</span> <span class='hs-varid'>x</span> <span class='hs-varid'>xs</span>
<a name="line-83"></a>
<a name="line-84"></a><a name="char"></a><span class='hs-definition'>char</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Memo</span> <span class='hs-conid'>Char</span>
<a name="line-85"></a><span class='hs-definition'>char</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>wrap</span> <span class='hs-varid'>chr</span> <span class='hs-varid'>ord</span> <span class='hs-varid'>integral</span>
<a name="line-86"></a>
<a name="line-87"></a><a name="boundedList"></a><span class='hs-comment'>-- | Build a table which memoizes all lists of less than the given length.</span>
<a name="line-88"></a><span class='hs-definition'>boundedList</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Int</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Memo</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Memo</span> <span class='hs-keyglyph'>[</span><span class='hs-varid'>a</span><span class='hs-keyglyph'>]</span>
<a name="line-89"></a><span class='hs-definition'>boundedList</span> <span class='hs-num'>0</span> <span class='hs-varid'>m</span> <span class='hs-varid'>f</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>f</span>
<a name="line-90"></a><span class='hs-definition'>boundedList</span> <span class='hs-varid'>n</span> <span class='hs-varid'>m</span> <span class='hs-varid'>f</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>table</span> <span class='hs-layout'>(</span><span class='hs-varid'>f</span> <span class='hs-conid'>[]</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-keyglyph'>\</span><span class='hs-varid'>x</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>boundedList</span> <span class='hs-layout'>(</span><span class='hs-varid'>n</span><span class='hs-comment'>-</span><span class='hs-num'>1</span><span class='hs-layout'>)</span> <span class='hs-varid'>m</span> <span class='hs-layout'>(</span><span class='hs-varid'>f</span> <span class='hs-varop'>.</span> <span class='hs-layout'>(</span><span class='hs-varid'>x</span><span class='hs-conop'>:</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
<a name="line-91"></a> <span class='hs-keyword'>where</span>
<a name="line-92"></a> <span class='hs-varid'>table</span> <span class='hs-varid'>nil</span> <span class='hs-varid'>cons</span> <span class='hs-conid'>[]</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>nil</span>
<a name="line-93"></a> <span class='hs-varid'>table</span> <span class='hs-varid'>nil</span> <span class='hs-varid'>cons</span> <span class='hs-layout'>(</span><span class='hs-varid'>x</span><span class='hs-conop'>:</span><span class='hs-varid'>xs</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>cons</span> <span class='hs-varid'>x</span> <span class='hs-varid'>xs</span>
<a name="line-94"></a>
<a name="line-95"></a><a name="either"></a><span class='hs-definition'>either</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Memo</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Memo</span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Memo</span> <span class='hs-layout'>(</span><span class='hs-conid'>Either</span> <span class='hs-varid'>a</span> <span class='hs-varid'>b</span><span class='hs-layout'>)</span>
<a name="line-96"></a><span class='hs-definition'>either</span> <span class='hs-varid'>m</span> <span class='hs-varid'>m'</span> <span class='hs-varid'>f</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>table</span> <span class='hs-layout'>(</span><span class='hs-varid'>m</span> <span class='hs-layout'>(</span><span class='hs-varid'>f</span> <span class='hs-varop'>.</span> <span class='hs-conid'>Left</span><span class='hs-layout'>)</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'>f</span> <span class='hs-varop'>.</span> <span class='hs-conid'>Right</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
<a name="line-97"></a> <span class='hs-keyword'>where</span>
<a name="line-98"></a> <span class='hs-varid'>table</span> <span class='hs-varid'>l</span> <span class='hs-varid'>r</span> <span class='hs-layout'>(</span><span class='hs-conid'>Left</span> <span class='hs-varid'>x</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>l</span> <span class='hs-varid'>x</span>
<a name="line-99"></a> <span class='hs-varid'>table</span> <span class='hs-varid'>l</span> <span class='hs-varid'>r</span> <span class='hs-layout'>(</span><span class='hs-conid'>Right</span> <span class='hs-varid'>x</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>r</span> <span class='hs-varid'>x</span>
<a name="line-100"></a>
<a name="line-101"></a><a name="maybe"></a><span class='hs-definition'>maybe</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Memo</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Memo</span> <span class='hs-layout'>(</span><span class='hs-conid'>Maybe</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span>
<a name="line-102"></a><span class='hs-definition'>maybe</span> <span class='hs-varid'>m</span> <span class='hs-varid'>f</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>table</span> <span class='hs-layout'>(</span><span class='hs-varid'>f</span> <span class='hs-conid'>Nothing</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'>f</span> <span class='hs-varop'>.</span> <span class='hs-conid'>Just</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
<a name="line-103"></a> <span class='hs-keyword'>where</span>
<a name="line-104"></a> <span class='hs-varid'>table</span> <span class='hs-varid'>n</span> <span class='hs-varid'>j</span> <span class='hs-conid'>Nothing</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>n</span>
<a name="line-105"></a> <span class='hs-varid'>table</span> <span class='hs-varid'>n</span> <span class='hs-varid'>j</span> <span class='hs-layout'>(</span><span class='hs-conid'>Just</span> <span class='hs-varid'>x</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>j</span> <span class='hs-varid'>x</span>
<a name="line-106"></a>
<a name="line-107"></a><a name="unit"></a><span class='hs-definition'>unit</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Memo</span> <span class='hs-conid'>()</span>
<a name="line-108"></a><span class='hs-definition'>unit</span> <span class='hs-varid'>f</span> <span class='hs-keyglyph'>=</span> <span class='hs-keyword'>let</span> <span class='hs-varid'>m</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>f</span> <span class='hs-conid'>()</span> <span class='hs-keyword'>in</span> <span class='hs-keyglyph'>\</span><span class='hs-conid'>()</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>m</span>
<a name="line-109"></a>
<a name="line-110"></a><a name="pair"></a><span class='hs-definition'>pair</span> <span class='hs-keyglyph'>::</span> <span class='hs-conid'>Memo</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Memo</span> <span class='hs-varid'>b</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Memo</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>
<a name="line-111"></a><span class='hs-definition'>pair</span> <span class='hs-varid'>m</span> <span class='hs-varid'>m'</span> <span class='hs-varid'>f</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>uncurry</span> <span class='hs-layout'>(</span><span class='hs-varid'>m</span> <span class='hs-layout'>(</span><span class='hs-keyglyph'>\</span><span class='hs-varid'>x</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>m'</span> <span class='hs-layout'>(</span><span class='hs-keyglyph'>\</span><span class='hs-varid'>y</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>f</span> <span class='hs-layout'>(</span><span class='hs-varid'>x</span><span class='hs-layout'>,</span><span class='hs-varid'>y</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span>
<a name="line-112"></a>
<a name="line-113"></a><a name="enum"></a><span class='hs-comment'>-- | Memoize an enum type.</span>
<a name="line-114"></a><span class='hs-definition'>enum</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>Enum</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>Memo</span> <span class='hs-varid'>a</span>
<a name="line-115"></a><span class='hs-definition'>enum</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>wrap</span> <span class='hs-varid'>toEnum</span> <span class='hs-varid'>fromEnum</span> <span class='hs-varid'>integral</span>
<a name="line-116"></a>
<a name="line-117"></a><a name="integral"></a><span class='hs-comment'>-- | Memoize an integral type.</span>
<a name="line-118"></a><span class='hs-definition'>integral</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>Integral</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>Memo</span> <span class='hs-varid'>a</span>
<a name="line-119"></a><span class='hs-definition'>integral</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>wrap</span> <span class='hs-varid'>fromInteger</span> <span class='hs-varid'>toInteger</span> <span class='hs-varid'>bits</span>
<a name="line-120"></a>
<a name="line-121"></a><a name="bits"></a><span class='hs-comment'>-- | Memoize an ordered type with a bits instance.</span>
<a name="line-122"></a><span class='hs-definition'>bits</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>Num</span> <span class='hs-varid'>a</span><span class='hs-layout'>,</span> <span class='hs-conid'>Ord</span> <span class='hs-varid'>a</span><span class='hs-layout'>,</span> <span class='hs-conid'>Bits</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>Memo</span> <span class='hs-varid'>a</span>
<a name="line-123"></a><span class='hs-definition'>bits</span> <span class='hs-varid'>f</span> <span class='hs-keyglyph'>=</span> <span class='hs-conid'>IntTrie</span><span class='hs-varop'>.</span><span class='hs-varid'>apply</span> <span class='hs-layout'>(</span><span class='hs-varid'>fmap</span> <span class='hs-varid'>f</span> <span class='hs-conid'>IntTrie</span><span class='hs-varop'>.</span><span class='hs-varid'>identity</span><span class='hs-layout'>)</span>
<a name="line-124"></a>
<a name="line-125"></a><a name="switch"></a><span class='hs-comment'>-- | @switch p a b@ uses the memo table a whenever p gives</span>
<a name="line-126"></a><span class='hs-comment'>-- true and the memo table b whenever p gives false.</span>
<a name="line-127"></a><span class='hs-definition'>switch</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-conid'>Bool</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Memo</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Memo</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Memo</span> <span class='hs-varid'>a</span>
<a name="line-128"></a><span class='hs-definition'>switch</span> <span class='hs-varid'>p</span> <span class='hs-varid'>m</span> <span class='hs-varid'>m'</span> <span class='hs-varid'>f</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>table</span> <span class='hs-layout'>(</span><span class='hs-varid'>m</span> <span class='hs-varid'>f</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>m'</span> <span class='hs-varid'>f</span><span class='hs-layout'>)</span>
<a name="line-129"></a> <span class='hs-keyword'>where</span>
<a name="line-130"></a> <span class='hs-varid'>table</span> <span class='hs-varid'>t</span> <span class='hs-varid'>f</span> <span class='hs-varid'>x</span> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>p</span> <span class='hs-varid'>x</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>t</span> <span class='hs-varid'>x</span>
<a name="line-131"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>f</span> <span class='hs-varid'>x</span>
<a name="line-132"></a>
<a name="line-133"></a><a name="RangeMemo"></a><span class='hs-comment'>-- | The type of builders for ranged tables; takes a lower bound and an upper</span>
<a name="line-134"></a><a name="RangeMemo"></a><span class='hs-comment'>-- bound, and returns a memo table for that range.</span>
<a name="line-135"></a><a name="RangeMemo"></a><span class='hs-keyword'>type</span> <span class='hs-conid'>RangeMemo</span> <span class='hs-varid'>a</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'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Memo</span> <span class='hs-varid'>a</span>
<a name="line-136"></a>
<a name="line-137"></a><a name="arrayRange"></a><span class='hs-comment'>-- | Build a memo table for a range using a flat array. If items are</span>
<a name="line-138"></a><span class='hs-comment'>-- given outside the range, don't memoize.</span>
<a name="line-139"></a><span class='hs-definition'>arrayRange</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>Array</span><span class='hs-varop'>.</span><span class='hs-conid'>Ix</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>RangeMemo</span> <span class='hs-varid'>a</span>
<a name="line-140"></a><span class='hs-definition'>arrayRange</span> <span class='hs-varid'>rng</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>switch</span> <span class='hs-layout'>(</span><span class='hs-conid'>Array</span><span class='hs-varop'>.</span><span class='hs-varid'>inRange</span> <span class='hs-varid'>rng</span><span class='hs-layout'>)</span> <span class='hs-layout'>(</span><span class='hs-varid'>unsafeArrayRange</span> <span class='hs-varid'>rng</span><span class='hs-layout'>)</span> <span class='hs-varid'>id</span>
<a name="line-141"></a>
<a name="line-142"></a><a name="unsafeArrayRange"></a><span class='hs-comment'>-- | Build a memo table for a range using a flat array. If items are</span>
<a name="line-143"></a><span class='hs-comment'>-- given outside the range, behavior is undefined.</span>
<a name="line-144"></a><span class='hs-definition'>unsafeArrayRange</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>Array</span><span class='hs-varop'>.</span><span class='hs-conid'>Ix</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>RangeMemo</span> <span class='hs-varid'>a</span>
<a name="line-145"></a><span class='hs-definition'>unsafeArrayRange</span> <span class='hs-varid'>rng</span> <span class='hs-varid'>f</span> <span class='hs-keyglyph'>=</span> <span class='hs-layout'>(</span><span class='hs-conid'>Array</span><span class='hs-varop'>.</span><span class='hs-varid'>listArray</span> <span class='hs-varid'>rng</span> <span class='hs-layout'>(</span><span class='hs-varid'>map</span> <span class='hs-varid'>f</span> <span class='hs-layout'>(</span><span class='hs-conid'>Array</span><span class='hs-varop'>.</span><span class='hs-varid'>range</span> <span class='hs-varid'>rng</span><span class='hs-layout'>)</span><span class='hs-layout'>)</span> <span class='hs-conid'>Array</span><span class='hs-varop'>.!</span><span class='hs-layout'>)</span>
<a name="line-146"></a>
<a name="line-147"></a>
<a name="line-148"></a><a name="chunks"></a><span class='hs-comment'>-- | Given a list of ranges, (lazily) build a memo table for each one</span>
<a name="line-149"></a><span class='hs-comment'>-- and combine them using linear search.</span>
<a name="line-150"></a><span class='hs-definition'>chunks</span> <span class='hs-keyglyph'>::</span> <span class='hs-layout'>(</span><span class='hs-conid'>Array</span><span class='hs-varop'>.</span><span class='hs-conid'>Ix</span> <span class='hs-varid'>a</span><span class='hs-layout'>)</span> <span class='hs-keyglyph'>=></span> <span class='hs-conid'>RangeMemo</span> <span class='hs-varid'>a</span> <span class='hs-keyglyph'>-></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'>a</span><span class='hs-layout'>)</span><span class='hs-keyglyph'>]</span> <span class='hs-keyglyph'>-></span> <span class='hs-conid'>Memo</span> <span class='hs-varid'>a</span>
<a name="line-151"></a><span class='hs-definition'>chunks</span> <span class='hs-varid'>rmemo</span> <span class='hs-varid'>cs</span> <span class='hs-varid'>f</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>lookup</span> <span class='hs-layout'>(</span><span class='hs-varid'>cs</span> <span class='hs-varop'>`zip`</span> <span class='hs-varid'>map</span> <span class='hs-layout'>(</span><span class='hs-keyglyph'>\</span><span class='hs-varid'>rng</span> <span class='hs-keyglyph'>-></span> <span class='hs-varid'>rmemo</span> <span class='hs-varid'>rng</span> <span class='hs-varid'>f</span><span class='hs-layout'>)</span> <span class='hs-varid'>cs</span><span class='hs-layout'>)</span>
<a name="line-152"></a> <span class='hs-keyword'>where</span>
<a name="line-153"></a> <span class='hs-varid'>lookup</span> <span class='hs-conid'>[]</span> <span class='hs-keyword'>_</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>error</span> <span class='hs-str'>"Element non in table"</span>
<a name="line-154"></a> <span class='hs-varid'>lookup</span> <span class='hs-layout'>(</span><span class='hs-layout'>(</span><span class='hs-varid'>r</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'>cs</span><span class='hs-layout'>)</span> <span class='hs-varid'>x</span> <span class='hs-keyglyph'>|</span> <span class='hs-conid'>Array</span><span class='hs-varop'>.</span><span class='hs-varid'>inRange</span> <span class='hs-varid'>r</span> <span class='hs-varid'>x</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>c</span> <span class='hs-varid'>x</span>
<a name="line-155"></a> <span class='hs-keyglyph'>|</span> <span class='hs-varid'>otherwise</span> <span class='hs-keyglyph'>=</span> <span class='hs-varid'>lookup</span> <span class='hs-varid'>cs</span> <span class='hs-varid'>x</span>
</pre></body>
</html>
|