Difference between revisions of "Talk:Tying the Knot"
m (Another attribution transferred) 
m (Minor remediation) 

Line 52:  Line 52:  
[[User:WarDaftWarDaft]] 17:25, 11 April 2012 (UTC) 
[[User:WarDaftWarDaft]] 17:25, 11 April 2012 (UTC) 

−  == Tying bigger knots 
+  == Tying bigger knots == 
−  +  Contents by [[User:AndrewBromageAndrew Bromage]] (but not the title). 

== Cyclic graph transformations == 
== Cyclic graph transformations == 
Latest revision as of 07:00, 19 April 2021
Contents
Building cyclic data structures
Somehow the following seems more straightforward to me, though perhaps I'm missing the point here:
data DList a = DLNode (DList a) a (DList a)
rot :: Integer > [a] > [a]
rot n xs  n < 0 = rot (n+1) ((last xs):(init xs))
 n == 0 = xs
 n > 0 = rot (n1) (tail xs ++ [head xs])
mkDList :: [a] > DList a
mkDList [] = error "Must have at least one element."
mkDList xs = DLNode (mkDList $ rot (1) xs) (head xs) (mkDList $ rot 1 xs)
 Cale Gibbard
The problem with this is it won't make a truly cyclic data structure, rather it will constantly be generating the rest of the list. To see this use trace (in Debug.Trace for GHC) in mkDList (e.g. mkDList xs = trace "mkDList" $ ...) and then takeF 10 (mkDList "a"). Add a trace to mkDList or go or wherever you like in the other version and note the difference.
 Derek Elkins
Yeah, thanks, I see what you mean.
This is so amazing that everybody should have seen it, so here's the trace. I put trace "\ngo{1/2}" $ directly after the two go definitions:
*Main> takeF 10 $ mkDList [1..3]
go2
[1
go2
,2
go2
,3
go1
,1,2,3,1,2,3,1]
 Cale Gibbard
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)
Tying bigger knots
Contents by Andrew Bromage (but not the title).
Cyclic graph transformations
Contents by Oleg Kiselyov.
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 (n1) next)
takeR :: Show a => Integer > DList a > [a]
takeR 0 _ = []
takeR n (DLNode prev x _) = x : (takeR (n1) prev)
Psybur 15:10, 12 October 2017 (UTC)