Talk:Tying the Knot

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 (n-1) (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 "\n--go{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 (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)