The tree with internal nodes of type Char and leaves of type v is a representation of a finite state machine, a common tool in parsing certain grammars. I'm not sure your type Compact v captures exactly this, since a value v may be followed by more Chars down in the tree. You'd want type Compact v = [Either (More v) v] -- akin to Data.Tree.Forest data More v = More Char (Compact v) -- akin to Data.Tree.Tree What you may want to look at is a so-called trie [1,2]. In textbooks, it is common to assume that there is a charcter '$' not element of your alphabet. Then '$' is appended to each string before compressing all into a tree structure. This way, one can put both a string and a prefix of it into the same tree. A special kind of trie is the suffix trie. It holds all suffixes of a string and facilitates fast full-text search. More efficient variants are extensively used in bioinformatics [3]. Olaf [1] http://hackage.haskell.org/package/word-trie-0.3.0/docs/Data-Trie.html [2] https://en.wikipedia.org/wiki/Trie [3] http://mummer.sourceforge.net