On Monday 28 December 2009 18:04:32 Gautam bt wrote:
> On Tue, Dec 29, 2009 at 12:04 AM, Jon Harrop wrote:
> > Forcing the evaluating of a thunk replaces the unevaluated expression
> > with the value it evaluates to. That is effectively in-place mutation.
>
> How can one use that to gain on effici
On Tue, Dec 29, 2009 at 12:04 AM, Jon Harrop wrote:
>
> Forcing the evaluating of a thunk replaces the unevaluated expression with
> the
> value it evaluates to. That is effectively in-place mutation.
>
How can one use that to gain on efficiency? I understand that laziness
allows a modified data
On Monday 28 December 2009 17:11:14 Gautam bt wrote:
> On Sat, Dec 26, 2009 at 12:49 AM, Svein Ove Aas wrote:
> > Lazyness can be considered to be a controlled form of mutation
>
> Can someone explain why this is true (or link me to an explanation)?
Forcing the evaluating of a thunk replaces the
On Sat, Dec 26, 2009 at 12:49 AM, Svein Ove Aas wrote:
>
> Lazyness can be considered to be a controlled form of mutation
Can someone explain why this is true (or link me to an explanation)?
--
Gautam
___
Haskell-Cafe mailing list
Haskell-Cafe@haske
On Friday 25 December 2009 19:59:39 Louis Wasserman wrote:
> >> One of the correspondents in that thread claims that it is
> >> provably impossible to have an efficient priority queue implementation
> >> without mutability. I think he's cuckoo. But I'd like to have some
> >> numbers to back me up
>> One of the correspondents in that thread claims that it is
>> provably impossible to have an efficient priority queue implementation
>> without mutability. I think he's cuckoo. But I'd like to have some
>> numbers to back me up.
He is cuckoo, and here's proof:
http://www.brics.dk/RS/96/37/BRI
2009/12/25 Svein Ove Aas :
> On Mon, Jun 15, 2009 at 4:18 AM, Richard O'Keefe wrote:
>> There's a current thread in the Erlang mailing list about
>> priority queues. I'm aware of, for example, the Brodal/Okasaki
>> paper and the David King paper. I'm also aware of James Cook's
>> priority queue p
On Mon, Jun 15, 2009 at 4:18 AM, Richard O'Keefe wrote:
> There's a current thread in the Erlang mailing list about
> priority queues. I'm aware of, for example, the Brodal/Okasaki
> paper and the David King paper. I'm also aware of James Cook's
> priority queue package in Hackage, have my own co
On Friday 25 December 2009 06:09:55 Matt Morrow wrote:
> On 12/23/09, Jon Harrop wrote:
> > And your results above indicate that the fastest imperative heap is over
> > 3x faster than the fastest functional heap?
>
> It's saying that
>
> (1) Using an imprecise an
> inefficient-relative-to-a-accu
On 12/25/09, Matt Morrow wrote:
> On 12/23/09, Jon Harrop wrote:
>> And your results above indicate that the fastest imperative heap is over
>> 3x
>> faster than the fastest functional heap?
Also, I've now added you to (1) my list of people never to hire to
perform statistical computations for m
On 12/23/09, Jon Harrop wrote:
> And your results above indicate that the fastest imperative heap is over 3x
> faster than the fastest functional heap?
It's saying that
(1) Using an imprecise an inefficient-relative-to-a-accurate-GC-that-doesn't-
have-to-assume-the-entire-memory-space-
On Tuesday 16 June 2009 23:50:45 Richard O'Keefe wrote:
> I've now done some benchmarks myself in C, Java, and Smalltalk,
> comparing "imperative" versions of leftist heaps with "functional" ones.
> For what it's worth, on a 2.16GHz Intel Core 2 Duo Mac, the
> coefficient in front of the log(n) par
Richard O'Keefe wrote:
There's a current thread in the Erlang mailing list about
priority queues. I'm aware of, for example, the Brodal/Okasaki
paper and the David King paper. I'm also aware of James Cook's
priority queue package in Hackage, have my own copy of Okasaki's
book, and have just spen
On 16 Jun 2009, at 11:49 am, Bertram Felgenhauer wrote:
What about decreaseKey in a purely functional setting? I suppose it's
O(log n), based on the intuition of trees with limited branching
factor.
Fibonacci heaps can do it in O(1), which makes a difference for
Dijkstra's algorithm, for exam
Am Mittwoch 17 Juni 2009 00:50:45 schrieb Richard O'Keefe:
> > One of the correspondents in that thread claims that it is
> > provably impossible to have an efficient priority queue implementation
> > without mutability.
> >
> > If he so claims, maybe you can challenge him by asking for a proof?
>
He sounds like a bit of a troll, but I agree the question itself is an
interesting one and I'd be interested to see if anyone has an "answer"
(although given the lack of criteria, it'll be hard to address his
points exactly)
On Tue, Jun 16, 2009 at 6:50 PM, Richard O'Keefe wrote:
>
> On 15 Jun 200
On 15 Jun 2009, at 7:54 pm, Luke Palmer wrote:
One of the correspondents in that thread claims that it is
provably impossible to have an efficient priority queue implementation
without mutability.
If he so claims, maybe you can challenge him by asking for a proof?
He claims that the burden is
Sebastian Sylvan wrote:
> On Mon, Jun 15, 2009 at 4:18 AM, Richard O'Keefe wrote:
> > There's a current thread in the Erlang mailing list about
> > priority queues. I'm aware of, for example, the Brodal/Okasaki
> > paper and the David King paper. I'm also aware of James Cook's
> > priority queue
I wasn't contradicting you, just clarifying that this is indeed the
optimal asymtotic complexity.
On Mon, Jun 15, 2009 at 3:43 PM, Sebastian
Sylvan wrote:
> Is that not what I said?
>
> On Mon, Jun 15, 2009 at 2:12 PM, Lennart Augustsson
> wrote:
>>
>> A priority queue can't have all operations b
Is that not what I said?
On Mon, Jun 15, 2009 at 2:12 PM, Lennart Augustsson
wrote:
> A priority queue can't have all operations being O(1), because then
> you would be able to sort in O(n) time. So O(log n) deleteMin and
> O(1) for the rest is as good as it gets.
>
> On Mon, Jun 15, 2009 at 10:
A priority queue can't have all operations being O(1), because then
you would be able to sort in O(n) time. So O(log n) deleteMin and
O(1) for the rest is as good as it gets.
On Mon, Jun 15, 2009 at 10:40 AM, Sebastian
Sylvan wrote:
>
>
> On Mon, Jun 15, 2009 at 4:18 AM, Richard O'Keefe wrote:
>
On Mon, Jun 15, 2009 at 4:18 AM, Richard O'Keefe wrote:
> There's a current thread in the Erlang mailing list about
> priority queues. I'm aware of, for example, the Brodal/Okasaki
> paper and the David King paper. I'm also aware of James Cook's
> priority queue package in Hackage, have my own c
On Sun, Jun 14, 2009 at 9:18 PM, Richard O'Keefe wrote:
> There's a current thread in the Erlang mailing list about
> priority queues. I'm aware of, for example, the Brodal/Okasaki
> paper and the David King paper. I'm also aware of James Cook's
> priority queue package in Hackage, have my own c
There's a current thread in the Erlang mailing list about
priority queues. I'm aware of, for example, the Brodal/Okasaki
paper and the David King paper. I'm also aware of James Cook's
priority queue package in Hackage, have my own copy of Okasaki's
book, and have just spent an hour searching the
24 matches
Mail list logo
