On Thu, Jul 8, 2010 at 5:30 PM, Angel de Vicente <span dir="ltr">&lt;<a href="mailto:angelv@iac.es">angelv@iac.es</a>&gt;</span> wrote:<br><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
Hi,<br>
<br>
I&#39;m going through the first chapters of the Real World Haskell book,<br>
so I&#39;m still a complete newbie, but today I was hoping I could solve<br>
the following function in Haskell, for large numbers (n &gt; 108)<br>
<br>
f(n) = max(n,f(n/2)+f(n/3)+f(n/4))<br>
<br>
I&#39;ve seen examples of memoization in Haskell to solve fibonacci<br>
numbers, which involved computing (lazily) all the fibonacci numbers<br>
up to the required n. But in this case, for a given n, we only need to<br>
compute very few intermediate results.<br>
<br>
How could one go about solving this efficiently with Haskell?<br>
<br></blockquote><div><div>We can do this very efficiently by making a structure that we can index in sub-linear time.</div><div><br></div><div>But first,</div><div><br></div><div>&gt;    {-# LANGUAGE BangPatterns #-}</div>
<div><br></div><div>&gt;    import Data.Function (fix)</div><div><br></div><div>Lets define f, but make it use &#39;open recursion&#39; rather than call itself directly.</div><div><br></div><div>&gt;    f :: (Int -&gt; Int) -&gt; Int -&gt; Int</div>
<div>&gt;    f mf 0 = 0</div><div>&gt;    f mf n = max n $ mf (div n 2) +</div><div>&gt;                     mf (div n 3) +</div><div>&gt;                     mf (div n 4)</div><div><br></div><div>You can get an unmemoized f by using `fix f` </div>
<div><br></div><div>This will let you test that f does what you mean for small values of f by calling, for example: `fix f 123` = 144</div><div><br></div><div>We could memoize this by defining:</div><div><br></div><div>&gt;    f_list :: [Int]</div>
<div>&gt;    f_list = map (f faster_f) [0..]</div><div><br></div><div>&gt;    faster_f :: Int -&gt; Int</div><div>&gt;    faster_f n = f_list !! n</div><div><br></div><div>That performs passably well, and replaces what was going to take O(n^3) time with something that memoizes the intermediate results.</div>
<div><br></div><div>But it still takes linear time just to index to find the memoized answer for `mf`. This means that results like:</div><div><br></div><div>    *Main Data.List&gt; faster_f 123801</div><div>    248604</div>
<div><br></div><div>are tolerable, but the result doesn&#39;t scale much better than that. We can do better!</div><div><br></div><div>First lets define an infinite tree:</div><div><br></div><div>&gt;    data Tree a = Tree (Tree a) a (Tree a)</div>
<div>&gt;    instance Functor Tree where</div><div>&gt;        fmap f (Tree l m r) = Tree (fmap f l) (f m) (fmap f r)</div><div><br></div><div>And then we&#39;ll define a way to index into it, so we can find a node with index n in O(log n) time instead:</div>
<div><br></div><div>&gt;    index :: Tree a -&gt; Int -&gt; a</div><div>&gt;    index (Tree _ m _) 0 = m</div><div>&gt;    index (Tree l _ r) n = case (n - 1) `divMod` 2 of</div><div>&gt;        (q,0) -&gt; index l q</div>
<div>&gt;        (q,1) -&gt; index r q</div><div><br></div><div>... and we may find a tree full of natural numbers to be convenient so we don&#39;t have to fiddle around with those indices:</div><div><br></div><div>&gt;    nats :: Tree Int</div>
<div>&gt;    nats = go 0 1</div><div>&gt;        where</div><div>&gt;            go !n !s = Tree (go l s&#39;) n (go r s&#39;)</div><div>&gt;                where</div><div>&gt;                    l = n + s</div><div>&gt;                    r = l + s</div>
<div>&gt;                    s&#39; = s * 2</div><div><br></div><div>Since we can index, you can just convert a tree into a list:</div><div><br></div><div>&gt;    toList :: Tree a -&gt; [a]</div><div>&gt;    toList as = map (index as) [0..]</div>
<div><br></div><div>You can check the work so far by verifying that `toList nats` gives you [0..]</div><div><br></div><div>Now, </div><div><br></div><div>&gt;    f_tree :: Tree Int</div><div>&gt;    f_tree = fmap (f fastest_f) nats</div>
<div><br></div><div>&gt;    fastest_f :: Int -&gt; Int</div><div>&gt;    fastest_f = index f_tree</div><div><br></div><div>works just like with list above, but instead of taking linear time to find each node, can chase it down in logarithmic time.</div>
<div><br></div><div>The result is considerably faster:</div><div><br></div><div>    *Main&gt; fastest_f 12380192300</div><div>    67652175206</div><div><br></div><div>    *Main&gt; fastest_f 12793129379123</div><div>    120695231674999</div>
<div><br></div><div>In fact it is so much faster that you can go through and replace Int with Integer above and get ridiculously large answers almost instantaneously</div><div><br></div><div>    *Main&gt; fastest_f&#39; 1230891823091823018203123</div>
<div>    93721573993600178112200489</div><div><br></div><div>    *Main&gt; fastest_f&#39; 12308918230918230182031231231293810923</div><div>    11097012733777002208302545289166620866358</div></div><div></div></div><br><div>
-Edward Kmett</div>