[Haskell-cafe] Really need some help understanding a solution
David Menendez
dave at zednenem.com
Thu Mar 26 23:05:28 EDT 2009
2009/3/26 Luke Palmer <lrpalmer at gmail.com>:
> 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 <dave at zednenem.com>
<http://www.eyrie.org/~zednenem/>
More information about the Haskell-Cafe
mailing list