1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
{- |
This creates a lazy Trie based on a finite range of Ints and is used to
memorize a function over the subsets of this range.
To create a Trie you need two supply 2 things
* Range of keys to bound
* A function or functions used to construct the value for a subset of keys
The Trie uses the Array type internally.
-}
module Text.Regex.TDFA.IntArrTrieSet where
{- By Chris Kuklewicz, 2007. BSD License, see the LICENSE file. -}
import Data.Array.IArray(Array,(!),listArray)
data TrieSet v = TrieSet { value :: v
, next :: Array Int (TrieSet v) }
-- | This is the accessor for the Trie. The list of keys should be
-- sorted.
lookupAsc :: TrieSet v -> [Int] -> v
lookupAsc (TrieSet {value=v,next=n}) =
(\keys -> case keys of [] -> v
(key:keys') -> lookupAsc (n!key) keys')
-- | This is a Trie constructor for a complete range of keys.
fromBounds :: (Int,Int) -- ^ (lower,upper) range of keys, lower<=upper
-> ([Int] -> v) -- ^ Function from list of keys to its value.
-- It must work for distinct ascending lists.
-> TrieSet v -- ^ The constructed Trie
fromBounds (start,stop) keysToValue = build id start where
build keys low = TrieSet { value = keysToValue (keys [])
, next = listArray (low,stop)
[build (keys.(x:)) (succ x) | x <- [low..stop] ] }
-- | This is a Trie constructor for a complete range of keys that uses
-- a function from single values and a merge operation on values to
-- fill the Trie.
fromSinglesMerge :: v -- ^ value for (lookupAsc trie [])
-> (v->v->v) -- ^ merge operation on values
-> (Int,Int) -- ^ (lower,upper) range of keys, lower<=upper
-> (Int->v) -- ^ Function from a single key to its value
-> TrieSet v -- ^ The constructed Trie
fromSinglesMerge emptyValue mergeValues bound keyToValue = trieSet where
trieSet = fromBounds bound keysToValue'
keysToValue' keys =
case keys of
[] -> emptyValue
[key] -> keyToValue key
_ -> mergeValues (keysToValue (init keys)) (keysToValue [last keys])
keysToValue = lookupAsc trieSet
-- | This is a Trie constructor for a complete range of keys that uses
-- a function from single values and a sum operation of values to fill
-- the Trie.
fromSinglesSum :: ([v]->v) -- ^ summation operation for values
-> (Int,Int) -- ^ (lower,upper) range of keys, lower <= upper
-> (Int->v) -- ^ Function from a single key to its value
-> TrieSet v -- ^ The constructed Trie
fromSinglesSum mergeValues bound keyToValue = trieSet where
trieSet = fromBounds bound keysToValue'
keysToValue' = mergeValues . map keyToValue
|
