2009/3/26 Luke Palmer
The spine of this trie is maximally lazy: this is key. If the structure of the spine depended on the input data (as it does for Data.Map), then we wouldn't be able to process infinite data, because we can never get it all. So even making a trie out of the list _|_ gives us:
{ 0 -> _|_, 1 -> _|_, 2 -> _|_, ... }
I.e. the keys are still there. Then we can combine two tries just by combining them pointwise (which is what infZipWith does). It is essential that the pattern matches on infZipWith are lazy. We're zipping together an infinite sequence of lists, and normally the result would be the length of the shortest one, which is unknowable. So the lazy pattern match forces the result ('s spine) to be infinite.
It's also important that (++) is non-strict in its second argument.
Using infZipWith with (+) requires examining the entire input before
getting any output.
Unfortunately, Günther's original post indicated that he wanted the
*sum* of the values for each key. Unless you're using non-strict
natural numbers, that pretty much requires examining the entire input
list before producing any output.
--
Incidentally, this also works (in that it produces the right answers):
type MultiMap k v = k -> [v]
-- The Monoid instance is pre-defined; here's the relevant code:
-- mappend map1 map2 = \k -> map1 k ++ map2 k
singleton :: Eq k => k -> v -> MultiMap k v
singleton k v = \k' -> if k == k' then [v] else []
test = mconcat [ singleton (n `mod` 42) n | n <- [0..]] 10
Or, using insert instead of singleton/union,
insert :: k -> v -> MultiMap k v -> MultiMap k v
insert k v map = \k' -> if k == k' then v : map k' else map k'
fromList :: Eq k => [(k,v)] -> MultiMap k v
fromList = foldr (\(k,v) -> insert k v) (const [])
Note that insert is non-strict in its third argument, meaning that
foldr can return an answer immediately.
--
Dave Menendez