Explicit purely functional data structure for difference lists

Question

In Haskell, lists of differences , in the sense of

[a] list representation with efficient concatenation operation

It seems implemented in terms of functional composition .

Functions and (dynamic) compositions of functions, however, must also be somehow represented in computer memory using data structures, which raises the question of how dlists can be implemented in Haskell without using functional compositions, but rather through some basic pure functional data structures based on w630. How can this be done with the same performance guarantees as composition functions?

Answer 1

As shown in this answer , the trick is rebuilding the tree (.)into a list ($)upon access.

We can emulate this with

data Dlist a = List [a]  
             | Append (Dlist a) (Dlist a)

which will juggle with nodes Appendto press the leftmost one to become the topmost left, at the first access, after which the next operation tailwill become O (1) ^(*)

let x = (List [1..10] `Append` List [11..20]) `Append` List [21..30]

and tail xshould produce

List [2..10] `Append` (List [11..20] `Append` List [21..30])

tail . , List node ( (x:xs)), node - Append, , , .

---

^(*) edit: O (1), List node . , Append , , , List node, n O (n + m), m - .

---

update: : ( ), , 1977 , gopher ​​ ( ), tail.

Answer 2

(++) , , - , (++) (++). - .

: m,

((ws ++ xs) ++ ys) ++ zs  -- m = 3 in this example

WHNF m thunks, (++) .

case (
    case (
        case ws of { [] -> xs ; (w:ws) -> w:(ws ++ xs) }
    ) of { [] -> ys ; (x:xs) -> x:(xs ++ ys) }
) of { [] -> zs ; (y:ys) -> y:(ys ++ zs) }

, n , m thunks n , O (m * n). (.. (([w] ++ [x]) ++ [y]) ++ [z]), m = n, O (n ²).

,

ws ++ (xs ++ (ys ++ zs))

WHNF (O (1)):

case ws of
    [] -> xs ++ (ys ++ zs)
    (w:ws) -> w:(ws ++ (xs ++ (ys ++ zs)))

n n thunks, , .

---

, (O (m)) , (++).

newtype DList a = DList ([a] -> [a])
fromList xs = DList (xs ++)
toList (DList f) = f []

instance Monoid (DList a) where
    mempty = fromList []
    DList f `mappend` DList g = DList (f . g)

,

toList (((fromList ws <> fromList xs) <> fromList ys) <> fromList zs)

- :

((((ws ++) . (xs ++)) . (ys ++)) . (zs ++)) []

-- expand innermost (.)
(((\l0 -> ws ++ (xs ++ l0)) . (ys ++)) . (zs ++)) []

-- expand innermost (.)
((\l1 -> (\l0 -> ws ++ (xs ++ l0)) (ys ++ l1)) . (zs ++)) []
-- beta reduce
((\l1 -> ws ++ (xs ++ (ys ++ l1))) . (zs ++)) []

-- expand innermost (.)
(\l2 -> (\l1 -> ws ++ (xs ++ (ys ++ l1))) (zs ++ l2)) []
-- beta reduce
(\l2 -> ws ++ (xs ++ (ys ++ (zs ++ l2)))) []
-- beta reduce
ws ++ (xs ++ (ys ++ (zs ++ [])))

O (m) , O (n) O (m + n), O (m * n). , m = n O (2n) ~ O (n), O (n ²).

Monoid.

newtype RMonoid m = RMonoid (m -> m)  -- "right-associative monoid"
toRM m = RMonoid (m <>)
fromRM (RMonoid f) = f mempty
instance Monoid m => Monoid (RMonoid m):
    mempty = toRM mempty
    RMonoid f `mappend` RMonoid g = RMonoid (f . g)

. , , Codensity, , (>>=) ( (<>)).

---

, , (++) - . , , append , .

data Snoc a = Nil | Snoc (Snoc a) a

xs +++ Nil = xs
xs +++ (Snoc ys y) = Snoc (xs +++ ys) y

O (1) WHNF ,

((ws +++ xs) +++ ys) +++ zs

case zs of
    Nil -> (ws +++ xs) +++ ys
    Snoc zs z -> Snoc ((ws +++ xs) +++ ys) +++ zs) z

.

ws +++ (xs +++ (ys +++ zs))

case (
    case (
        case zs of { Nil -> ys ; (Snoc zs z) -> Snoc (ys +++ zs) z }
    ) of { Nil -> xs ; (Snoc ys y) -> Snoc (xs +++ ys) y }
) of { Nil -> ws ; (Snoc xs x) -> Snoc (ws +++ xs) y }

, , , !

newtype LMonoid m = LMonoid (m -> m)  -- "left-associative monoid"
toLM m = LMonoid (<> m)
fromLM (LMonoid f) = f mempty
instance Monoid m => Monoid (LMonoid m):
    mempty = toLM mempty
    LMonoid f `mappend` LMonoid g = LMonoid (g . f)

Answer 3

.

data TList a = Nil | Single a | Node !(TList a) (TList a)

singleton :: a -> TList a
singleton = Single

instance Monoid (TList a) where
  mempty = Nil
  mappend = Node

toList, Foldable, , , .

instance Foldable TList where
  foldMap _ Nil = mempty
  foldMap f (Single a) = f a
  foldMap f (Node t u) = foldMap f t <> foldMap f u

  toList as0 = go as0 [] where
    go Nil k = k
    go (Single a) k = a : k
    go (Node l r) k = go l (go r k)

toList - O (n), n - (.. mappend, TList). : Node . mempty, mappend singleton, , O (1).

, DList:

newtype DList a = DList ([a] -> [a])
singletonD :: a -> DList a
singletonD a = DList (a:)
instance Monoid (DList a) where
  mempty = DList id
  mappend (DList f) (DList g) = DList (f . g)
instance Foldable DList where
  foldr c n xs = foldr c n (toList xs)
  toList (DList f) = f []

, , ? , , . , TList s! singletonD x , () (:) x. , O (1). mempty id, O (1) . mappend as bs , O (1) , O ( + bs) .

, TList DList, . , : , .

---

DList TList , . , .

, , , . TList uncons ( ). unsnoc, fancier (catenable deque). . , , , .