On Thu, Mar 26, 2009 at 12:21 PM, Günther Schmidt <span dir="ltr"><<a href="mailto:gue.schmidt@web.de">gue.schmidt@web.de</a>></span> wrote:<br><div class="gmail_quote"><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Hi guys,<br>
<br>
I tried for days now to figure out a solution that Luke Palmer has presented me with, by myself, I'm getting nowhere.</blockquote><div><br>Sorry, I meant to respond earlier.<br><br>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...<br>
<br><i>Lazy</i> list processing is all about <i>right</i> 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:<br>
<br>(1,2):(3,4):(3,5):...<br><br>And turn it into a structure like this:<br><br>{<br>0 -> ...<br>1 -> 2:...<br>2 -> ...<br>3 -> 4:5:...<br>...<br>}<br><br>(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)<br>
<br>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!)<br>
<br>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:<br>
<br>{ 0 -> _|_, 1 -> _|_, 2 -> _|_, ... }<br><br>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.<br>
<br>Umm... yeah, that's a braindump. Sorry I couldn't be more helpful. I'm happy to answer any specific questions.<br><br>Luke<br><br></div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<br>
<br>
He has kindly provided me with this code:<br>
<br>
import Data.Monoid<br>
<br>
newtype IntTrie a = IntTrie [a]<br>
deriving Show<br>
<br>
singleton :: (Monoid a) => Int -> a -> IntTrie a<br>
singleton ch x = IntTrie $ replicate ch mempty ++ [x] ++ repeat mempty<br>
<br>
lookupTrie :: IntTrie a -> Int -> a<br>
lookupTrie (IntTrie xs) n = xs !! n<br>
<br>
instance (Monoid a) => Monoid (IntTrie a) where<br>
mempty = IntTrie (repeat mempty)<br>
mappend (IntTrie xs) (IntTrie ys) = IntTrie (infZipWith mappend xs ys)<br>
<br>
infZipWith f ~(x:xs) ~(y:ys) = f x y : infZipWith f xs ys<br>
<br>
test = mconcat [singleton (n `mod` 42) [n] | n <- [0..]] `lookupTrie` 10<br>
<br>
It's supposed to eventually help me group a list of key value pairs and then further process them in a linear (streaming like) way.<br>
<br>
The original list being something like [('a', 23), ('b', 18), ('a', 34) ...].<br>
<br>
There are couple of techniques employed in this solution, but I'm just guessing here.<br>
<br>
The keywords I've been looking up so far:<br>
<br>
Memmoization, Deforestation, Single Pass, Linear Map and some others.<br>
<br>
Can someone please fill me in?<br>
<br>
Günther<br>
<br>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org" target="_blank">Haskell-Cafe@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
</blockquote></div><br>