Difference between revisions of "Talk:Tying the Knot"
(Alternate example) |
(→takeF and takeR in the DList example do not compile for me: new section) |
||
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> |
Revision as of 14:53, 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)
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)