Personal tools

Talk:Tying the Knot

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
(Alternate example)
 
 
(One intermediate revision by one user not shown)
Line 10: Line 10:
  
 
[[User:WarDaft|WarDaft]] 17:25, 11 April 2012 (UTC)
 
[[User:WarDaft|WarDaft]] 17:25, 11 April 2012 (UTC)
 +
 +
== takeF and takeR in the DList example do not compile for me ==
 +
 +
I had to modify them as so:
 +
 +
<haskell>
 +
takeF :: Integer -> DList a -> [a]
 +
takeF 0    _                = []
 +
takeF n (DLNode _ x next) = x : (takeF (n-1) next)
 +
 +
takeR :: Show a => Integer -> DList a -> [a]
 +
takeR 0    _                = []
 +
takeR n (DLNode prev x _) = x : (takeR (n-1) prev)
 +
</haskell>
 +
 +
[[User:Psybur|Psybur]] 15:10, 12 October 2017 (UTC)

Latest revision as of 14:54, 12 October 2017

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:

mkDLList list = head result where
  (result, n) = (zipWith mknode list [0..], length list)
  mknode x i  = DLList (result !! ((i - 1) `mod` n) ) x (result !! (i + 1 `mod` n) )

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.

With a slight tweak, this also serves as a simple method for defining arbitrary graphs, which is best given a different sort of optimization.

WarDaft 17:25, 11 April 2012 (UTC)

[edit] takeF and takeR in the DList example do not compile for me

I had to modify them as so:

takeF :: Integer -> DList a -> [a]
takeF 0     _                 = []
takeF n (DLNode _ x next) = x : (takeF (n-1) next)
 
takeR :: Show a => Integer -> DList a -> [a]
takeR 0     _                 = []
takeR n (DLNode prev x _) = x : (takeR (n-1) prev)

Psybur 15:10, 12 October 2017 (UTC)