Difference between revisions of "Difference list"
m (→Examples: Update hackage URLs) 
(→Difference lists as functions: Remove "of the second sort" (made no sense out of context of Wikipedia article it was copypasted from), and give code in addition to prose.) 

Line 1:  Line 1:  
== Difference lists as functions == 
== Difference lists as functions == 

−  A difference list of 
+  A difference list representation of a list <hask>xs :: [T]</hask> is a function <hask>f :: [T] > [T]</hask>, which when given another list <hask>ys :: [T]</hask>, returns the list that <hask>f</hask> represents, prepended to <hask>ys</hask>. I.e. <hask>f ys = xs ++ ys</hask>. 
Whether this kind of difference list is more efficient than another list representations depends on usage patterns. 
Whether this kind of difference list is more efficient than another list representations depends on usage patterns. 

If an algorithm builds a list by concatenating smaller lists, which are themselves built by concatenating still smaller lists, 
If an algorithm builds a list by concatenating smaller lists, which are themselves built by concatenating still smaller lists, 
Latest revision as of 16:40, 1 August 2018
Difference lists as functions
A difference list representation of a list xs :: [T]
is a function f :: [T] > [T]
, which when given another list ys :: [T]
, returns the list that f
represents, prepended to ys
. I.e. f ys = xs ++ ys
.
Whether this kind of difference list is more efficient than another list representations depends on usage patterns.
If an algorithm builds a list by concatenating smaller lists, which are themselves built by concatenating still smaller lists,
then use of difference lists can improve performance by effectively "flattening" the list building computations.
This can best be exemplified by show
and shows
of Prelude, where the first one implements the naive approach and the second one uses difference lists.
Consider showing a binary tree.
LTR
gives

(show L) ++ (show T ++ (show R))

((show LL) ++ (show LT ++ (show LR))) ++ (show T ++ (show R))

(((show LLL) ++ (show LLT ++ (show LLR))) ++ (show LT ++ (show LR))) ++ (show T ++ (show R))
If the tree is large, you end up with a pretty large left association for the left subtree. True, there's lot of right association, too, but bad enough.
With difference lists you write

shows L . (shows T . shows R)

(shows LL . (shows LT . shows LR)) . (shows T . shows R)

((shows LLL . (shows LLT . shows LLR)) . (shows LT . shows LR)) . (shows T . shows R)
You still need to resolve three (.) until you get to the first character of the result string, but for the subsequent characters you do not need to resolve those dots. In the end, resolution of all (.) may need some time but then concatenation is performed entirely rightassociative.
Examples
 ShowS type in the Prelude of Haskell
 The Endo monoid from
Data.Monoid
allows a simple difference list implementation. E.g.Endo ("bla"++)
represents the list"bla"
,mempty
represents the empty list,mappend
is list concatenation andappEndo dlist []
converts the difference listdlist
to a regular list.  Donald Bruce Stewart's difference list library
 Bas van Dijk's difference strings library (which is just a newtype wrapper around a DList Char)
See also
 HaskellCafe: Difference lists and ShowS
 Wikipedia on Difference lists