[Haskell-cafe] Really need some help understanding a solution

[David Menendez]

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/>