[Haskell-cafe] Musings on lists

[Olaf Klinke]

The fact that [a] is a linked list is exploited in Data.List.tails as
well as in 
https://hackage.haskell.org/package/suffixtree
where suffixes and internal segments of the tree all use Cons cells of
the original list, so the overhead is only in the tree structure
itself. In fact, exploiting the location of the internal tree nodes
relative to the original list, one could compress the list similarly to
the Lempel-Ziv 78 algorithm. This way, bioinformaticians manage to
create full-text index structures [*] that are not much larger, or even
smaller than, the original text. 

Olaf

[*] Lempel-Ziv 78 creates a suffix tree of the text holding only a
subset of all suffixes, namely those starting at a block boundary. This
already suffices to find all occurrences of substrings spanning a block
boundary.