Talk:Tying the Knot - Revision history
http://www.haskell.org/haskellwiki/index.php?title=Talk:Tying_the_Knot&action=history
Revision history for this page on the wikienMediaWiki 1.19.5-1+deb7u1Mon, 22 Sep 2014 09:47:18 GMTWarDaft: Alternate example
http://www.haskell.org/haskellwiki/index.php?title=Talk:Tying_the_Knot&diff=45220&oldid=prev
http://www.haskell.org/haskellwiki/index.php?title=Talk:Tying_the_Knot&diff=45220&oldid=prev<p>Alternate example</p>
<p><b>New page</b></p><div>There's a conceptually much simpler way build a circular structure, though it has a substantial performance overhead (n^2) the first time you run through the nodes:<br />
<br />
mkDLList list = head result where<br />
(result, n) = (zipWith mknode list [0..], length list)<br />
mknode x i = DLList (result !! ((i - 1) `mod` n) ) x (result !! (i + 1 `mod` n) )<br />
<br />
Since we already have the result - the list of all the relevant nodes - we just simply point to the items at the right points on the list. When we do it this way, it's obvious what is going on from just a basic understanding of laziness, then we see a huge waste of operations in the repeat list traversing, and look for some way to make it O(n). The trick, of course, being tying the knot.<br />
<br />
With a slight tweak, this also serves as a simple method for defining arbitrary graphs, which is best given a different sort of optimization.<br />
<br />
[[User:WarDaft|WarDaft]] 17:25, 11 April 2012 (UTC)</div>Wed, 11 Apr 2012 17:25:59 GMTWarDafthttp://www.haskell.org/haskellwiki/Talk:Tying_the_Knot