blog

Allison (1989) gives an example of tying the knot to build an immutable, doubly-linked list from a list. However, this does not support the usual insertion and deletion.

The below is a cut at "proper" doubly-linked lists, allowing insertion, deletion, peeking to the left or right, etc.

data DLList a = Cyc { n :: Int, bw :: DLList a, e :: a, fw :: DLList a }

singleton :: a -> DLList a
singleton x = xs where xs = Cyc 1 xs x xs

-- | Insert to the left; returning new node
insertL :: a -> DLList a -> DLList a
insertL x (Cyc n _ y r) = xs where
    xs = Cyc (n+1) penultimate x ys'
    (penultimate, ys') = propagateR (Cyc (n+1) xs y r)

propagateR :: DLList a -- ^ focus, with backlink to cycle stop
           -> (DLList a, DLList a) -- penultimate, updated focus
propagateR xs = step (m-2) xs (bw xs)
  where m=n xs
        end=bw xs

        step 0 (Cyc _ _ x _) b = (ys,ys) where ys = Cyc m b x end
        step k (Cyc _ _ x r) b = (penultimate, ys)
          where ys=Cyc m b x r'; (penultimate, r') = step (k-1) r ys

-- | Delete focus, returning right neighbor
deleteR :: DLList a -> DLList a
deleteR (Cyc 1 _ _ _)             = error "deleteR called on a singleton"
deleteR (Cyc 2 _ _ f)             = singleton (e f)
deleteR (Cyc _ _ _ (Cyc n _ y r)) = xs where
    xs = Cyc (n-1) penultimate y r'
    (penultimate, r') = propagateR (r { bw = xs, n = n-1 })

To see that this works, we define

dbg :: Int -> DLList a -> ([a], a, [a])
dbg m (Cyc _ l z r) = (reverse $ takeL (m-1) l, z, takeR (m-1) r)
  where
    takeL 0 _             = []
    takeL n (Cyc _ b x _) = x:takeL (n-1) b

    takeR 0 _             = []
    takeR n (Cyc _ _ x f) = x:takeR (n-1) f

Note the reverse so that, when displayed, it is as if the left traversal is going out from the focus.

Then:

ghci> dbg 20 (fw $ insertL 5 $ bw $ insertL 4 $ insertL 3 $ insertL 2 $ singleton (1 :: Int))
([4,3,2,5,1,4,3,2,5,1,4,3,2,5,1,4,3,2,5],1,[4,3,2,5,1,4,3,2,5,1,4,3,2,5,1,4,3,2,5])

This is inefficient compared to a mutable doubly-linked list to the point where it is not comparable, but the example is amusing.