úÎK      portable (Haskell 98) experimentaldons@cse.unsw.edu.au Safe-Inferred?A difference list is a function that given a list, returns the F original contents of the difference list prepended at the given list This structure supports O(1)& append and snoc operations on lists, B making it very useful for append-heavy uses, such as logging and  pretty printing. EFor example, using DList as the state type when printing a tree with  the Writer monad  import Control.Monad.Writer  import Data.DList  1 data Tree a = Leaf a | Branch (Tree a) (Tree a)  % flatten_writer :: Tree x -> DList x , flatten_writer = snd . runWriter . flatten  where 1 flatten (Leaf x) = tell (singleton x) 5 flatten (Branch x y) = flatten x >> flatten y $Converting a normal list to a dlist )Converting a dlist back to a normal list 0Create a difference list containing no elements 1Create difference list with given single element O(1)0, Prepend a single element to a difference list O(1)/, Append a single element at a difference list O(1), Appending difference lists O(spine), Concatenate difference lists O(n);, Create a difference list of the given number of elements  O(length dl) , List elimination, head, tail. Return the head of the list Return the tail of the list Unfoldr for difference lists Foldr over difference lists Map over difference lists.           dlist-0.5 Data.DListDListDLunDLfromListtoListempty singletonconssnocappendconcat replicatelistheadtailunfoldrfoldrmap maybeReturn$fMonadPlusDList $fMonadDList$fApplicativeDList$fFunctorDList $fMonoidDList