Dear Luke,
let me thank you first of all for your response, period, and let me also
assure you that your efforts are not (totally) in vain. :)
Of course I had all kinds of guesses what sort of dark arts you employed
here, mostly really long shots (Memoization, CPS ...). And at the end of
the day it turns out to be a lot simpler than that.
You've basically chosen a data structure that can be consumed while it's
still being built (due to Lazy Evaluation). I certainly haven't figured
it all out and it will take a lot more time to play with Tries before I
have.
I'm already eager to sift through the other goodies that are on your
blog once I have finished my app, very interesting stuff even if can't
understand half of it. :)
Would you happen to know a good starting point about tries?
Günther
Luke Palmer schrieb:
On Thu, Mar 26, 2009 at 12:21 PM, GüŸnther Schmidt <gue.schm...@web.de
<mailto:gue.schm...@web.de>> wrote:
Hi guys,
I tried for days now to figure out a solution that Luke Palmer has
presented me with, by myself, I'm getting nowhere.
Sorry, I meant to respond earlier.
They say you don't really understand something until you can explain it
to a six year old. So trying to explain this to a colleague made me
realize how little I must understand it :-).. But I'll try by saying
whatever come to mind...
/Lazy/ list processing is all about /right/ associativity. We need to
be able to output some information knowing that our input looks like
a:b:c:..., where we don't know the ... I see IntTrie [a] as an infinite
collection of lists (well, it is [[a]], after all :-), one for each
integer. So I want to take a structure like this:
(1,2):(3,4):(3,5):...
And turn it into a structure like this:
{
0 -> ...
1 -> 2:...
2 -> ...
3 -> 4:5:...
...
}
(This is just a list in my implementation, but I intended it to be a
trie, ideally, which is why I wrote the keys explicitly)
So the yet-unknown information at the tail of the list turns into
yet-unknown information about the tails of the keys. In fact, if you
replace .... with _|_, you get exactly the same thing (this is no
coincidence!)
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.
Umm... yeah, that's a braindump. Sorry I couldn't be more helpful.
I'm happy to answer any specific questions.
Luke
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
