2009/3/26 Luke Palmer <[email protected]>: > 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 <[email protected]> <http://www.eyrie.org/~zednenem/> _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
