# Difference list

### From HaskellWiki

(Wikipedia) |
m |
||

(4 intermediate revisions by 3 users not shown) | |||

Line 6: | Line 6: | ||

then use of difference lists can improve performance by effectively "flattening" the list building computations. |
then use of difference lists can improve performance by effectively "flattening" the list building computations. |
||

− | This can best be exemplified by <hask>show</hask> and <hask>shows</hask> of Prelude, |
+ | This can best be exemplified by <hask>show</hask> and <hask>shows</hask> of Prelude, where the first one implements the naive approach and the second one uses difference lists. |

− | where the first one implements the naive approach and the second one uses difference lists. |
||

Consider showing a binary tree. |
Consider showing a binary tree. |
||

<hask>L-T-R</hask> gives |
<hask>L-T-R</hask> gives |
||

* <hask> (show L) ++ (show T ++ (show R)) </hask> |
* <hask> (show L) ++ (show T ++ (show R)) </hask> |
||

− | * <hask> ((show LL) ++ (showLT ++ (show LR))) ++ (show T ++ (show R)) </hask> |
+ | * <hask> ((show LL) ++ (show LT ++ (show LR))) ++ (show T ++ (show R)) </hask> |

* <hask> (((show LLL) ++ (show LLT ++ (show LLR))) ++ (show LT ++ (show LR))) ++ (show T ++ (show R)) </hask> |
* <hask> (((show LLL) ++ (show LLT ++ (show LLR))) ++ (show LT ++ (show LR))) ++ (show T ++ (show R)) </hask> |
||

Line 20: | Line 20: | ||

* <hask> shows L . (shows T . shows R) </hask> |
* <hask> shows L . (shows T . shows R) </hask> |
||

− | * <hask> (shows LL . (showsLT . shows LR)) . (shows T . shows R) </hask> |
+ | * <hask> (shows LL . (shows LT . shows LR)) . (shows T . shows R) </hask> |

− | * <hask> ((shows LLL . (shows LLT . shows LLR)) . (showsLT . shows LR)) . (shows T . shows R) </hask> |
+ | * <hask> ((shows LLL . (shows LLT . shows LLR)) . (shows LT . shows LR)) . (shows T . shows R) </hask> |

You still need to resolve three (.) until you get to the first character of the result string, |
You still need to resolve three (.) until you get to the first character of the result string, |
||

Line 30: | Line 30: | ||

* [[ShowS]] type in the Prelude of Haskell |
* [[ShowS]] type in the Prelude of Haskell |
||

+ | * The Endo monoid from <hask>Data.Monoid</hask> allows a simple difference list implementation. E.g. <hask>Endo ("bla"++)</hask> represents the list <hask>"bla"</hask>, <hask>mempty</hask> represents the empty list, <hask>mappend</hask> is list concatenation and <hask>appEndo dlist []</hask> converts the difference list <hask>dlist</hask> to a regular list. |
||

* Donald Bruce Stewart's [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/dlist difference list library] |
* Donald Bruce Stewart's [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/dlist difference list library] |
||

+ | * Bas van Dijk's [http://hackage.haskell.org/cgi-bin/hackage-scripts/package/dstring difference strings library] (which is just a newtype wrapper around a DList Char) |
||

== See also == |
== See also == |

## Latest revision as of 11:24, 22 April 2012

## [edit] 1 Difference lists as functions

A difference list of the second sort represents lists as a functionWhether 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 byConsider showing a binary tree.

- (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 right-associative.

## [edit] 2 Examples

- ShowS type in the Prelude of Haskell
- The Endo monoid from allows a simple difference list implementation. E.g.Data.Monoidrepresents the listEndo ("bla"++),"bla"represents the empty list,memptyis list concatenation andmappendconverts the difference listappEndo dlist []to a regular list.dlist
- Donald Bruce Stewart's difference list library
- Bas van Dijk's difference strings library (which is just a newtype wrapper around a DList Char)

## [edit] 3 See also

- Haskell-Cafe: Difference lists and ShowS
- Wikipedia on Difference lists