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

[Peter Verswyvelen]

How do you plan to consume the running sums of these data? How many
different keys do you have?
If all pure stuff fails, you can always revert to imperative techniques,
using a mutable
arrayor
something  :)

On Fri, Mar 27, 2009 at 3:18 PM, GüŸnther Schmidt wrote:

> Guys,
>
> I appreciate the contribution but I'm now more confused than ever :)
>
> On the Co-Induction-whatever thingy: Thanks, that's certainly something
> interesting and I'll try to find out more about it.
>
> But it looks like none of all the proposals offers a true solution, at
> least none from start to finish. The amount of data is large, but finite.
>
> So for now, I'll just stick with my initial approach as I'm running out of
> time.
>
>
> Günther
>
> ___
> Haskell-Cafe mailing list
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

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

[GüŸnther Schmidt]

Guys,

I appreciate the contribution but I'm now more confused than ever :)

On the Co-Induction-whatever thingy: Thanks, that's certainly something 
interesting and I'll try to find out more about it.


But it looks like none of all the proposals offers a true solution, at 
least none from start to finish. The amount of data is large, but finite.


So for now, I'll just stick with my initial approach as I'm running out 
of time.


Günther

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

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

[wren ng thornton]

Gü?nther Schmidt wrote:
The depth this language has is just amazing and the stuff that is 
tackled in this language is just  aaahhh. Can't quite put it in 
words, maybe something along the lines "the ultimate thing, key to the 
universe" I don't know.


Humbling and frustrating especially when you come across the Lukes and 
they do to you what he did to me in about 12 lines of code. And then you 
come across the blogs of the Lukes and see all the other things where 
you stand in awe and your jaw drops. And you realize how far away from 
that you still are.


If you enjoy jaw-dropping brain-exploding fun, have you seen Martin 
Escardo's work on exhaustively searching infinite spaces?



http://math.andrej.com/2007/09/28/seemingly-impossible-functional-programs/
http://math.andrej.com/2008/11/21/a-haskell-monad-for-infinite-search-in-finite-time/

--
Live well,
~wren
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

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

[Gü?nther Schmidt]

Well Folks,

I've been programming for almost a decade now and making a living off it 
for almost 8 years.


To me programing in Haskell is sometimes quite a humbling experience, 
because I come to realize how shallow my ventures so far were.


The depth this language has is just amazing and the stuff that is 
tackled in this language is just  aaahhh. Can't quite put it in 
words, maybe something along the lines "the ultimate thing, key to the 
universe" I don't know.


Humbling and frustrating especially when you come across the Lukes and 
they do to you what he did to me in about 12 lines of code. And then you 
come across the blogs of the Lukes and see all the other things where 
you stand in awe and your jaw drops. And you realize how far away from 
that you still are.


And now you!

Sry for that Thomas, my prescription ran out today. I'll check on the 
link first thing once I got a refill.


Günther

Karl-Hinz, mei Drobbe!

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

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