úÎ?=2     portable experimentalbos@serpentine.com"AThe suffix tree type. The implementation is exposed to ease the 7 development of custom traversal functions. Note that ( a,   a)$ pairs are not stored in any order. An edge in the suffix tree. %The prefix string associated with an . Use  to " create a value of this type, and  to deconstruct one. The list of symbols that   can possibly see in its  input. BThe length of a prefix list. This type is formulated to do cheap A work eagerly (to avoid constructing a pile of deferred thunks), E while deferring potentially expensive work (computing the length of  a list). O(1). Construct a  value. O(n). Obtain the list stored in a . O(t)9. Folds the edges in a tree, using post-order traversal.  Suitable for lazy use. O(t)=. Folds the edges in a tree, using pre-order traversal. The & step function is evaluated strictly. #step function (evaluated strictly) initial state O(t). Generic fold over a tree. A few simple examples.  /countLeaves == fold id id (const const) (1+) 0  -countEdges = fold id id (\_ a _ -> a+1) id 0 BThis more complicated example generates a tree of the same shape, & but new type, with annotated leaves.   data GenTree a b = GenNode [( a, GenTree a b)]  | GenLeaf b  deriving ()    gentree ::  a -> GenTree a Int  gentree =   reset id fprefix reset leaf  where leaf = GenLeaf 1  reset =  leaf 3 fprefix p t (GenLeaf _) = GenNode [(p, t)] 9 fprefix p t (GenNode es) = GenNode ((p, t):es) downwards state transformer upwards state transformer edge state transformer leaf state transformer initial state tree #Increments the length of a prefix.  O(n):. Returns all non-empty suffixes of the argument, longest  first. Behaves as follows: suffixes xs == init (tails xs)  !"  O(k n log n),. Constructs a suffix tree using the given C alphabet. The performance of this function is linear in the size  k? of the alphabet. That makes this function suitable for small A alphabets, such as DNA nucleotides. For an alphabet containing  more than a few symbols,   is usually several orders of  magnitude faster.  O(n log n). Constructs a suffix tree. #O(n)8. Indicates whether the suffix tree contains the given / sublist. Performance is linear in the length n of the  sublist. O(n)7. Finds the given subsequence in the suffix tree. On  failure, returns $. On success, returns the  in the E suffix tree at which the subsequence ends, along with the number of ) elements to drop from the prefix of the  to get the "real"  remaining prefix. Here is an example:  (> find "ssip" (construct "mississippi") Just ((mkPrefix "ppi",Leaf),1) This indicates that the edge ( "ppi",) matches, 4 and that we must strip 1 character from the string "ppi" to get  the remaining prefix string "pi". $Performance is linear in the length n of the query list. O(n)9. Finds the subtree rooted at the end of the given query  sequence. On failure, returns $. $Performance is linear in the length n of the query list. O(n). Returns the path from the  in the suffix tree at C which the given subsequence ends, up to the root of the tree. If 7 the subsequence is not found, returns the empty list. 7Performance is linear in the length of the query list. O(t)(. Count the number of leaves in a tree. $Performance is linear in the number t of elements in the tree. O(n + r)3. Count the number of times a sequence is repeated C in the input sequence that was used to construct the suffix tree. $Performance is linear in the length n of the input sequence, plus  the number of times r the sequence is repeated.      %      !"#$%&'()*suffixtree-0.2.2.1Data.SuffixTreeSTreeLeafNodeEdgePrefixAlphabetmkPrefixprefixfoldrfoldlfoldsuffixes constructWith constructelemfindEdgefindTreefindPath countLeaves countRepeats EdgeFunctionLengthSumExactlypmapsmapbaseGHC.ShowShowGHC.Baseconstinc lazyTreeWithlazyTree suffixMapcstpstsuffix Data.MaybeNothing