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

[Gü?nther Schmidt]

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.schmidt at web.de 
> <mailto:gue.schmidt at 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
>