# Difference between revisions of "Talk:Tying the Knot"

(Selected comments from old wiki transferred) |
m (Added attribution for "new" section) |
||

Line 51: | Line 51: | ||

[[User:WarDaft|WarDaft]] 17:25, 11 April 2012 (UTC) |
[[User:WarDaft|WarDaft]] 17:25, 11 April 2012 (UTC) |
||

+ | |||

+ | == Tying bigger knots === |
||

+ | ''Content'' by [[User:AndrewBromage|Andrew Bromage]]. |
||

== takeF and takeR in the DList example do not compile for me == |
== takeF and takeR in the DList example do not compile for me == |

## Revision as of 06:23, 19 April 2021

## 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 =

*Content* by Andrew Bromage.

## 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)