 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 06/09/2011 04:05 PM, Warp wrote:
> Invisible<voi### [at] dev null> wrote:
>> On 05/09/2011 07:45 PM, Warp wrote:
>
>>> The lack of separators is also confusing to someone who is accustomed to
>>> programming languages that use separators.
>
>> Don't try Lisp. ;-)
>
> I thought Lisp separates everything with parentheses.
In Haskell, you say
abc def ghi
In Lisp, you say
(abc def ghi)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 06/09/2011 04:03 PM, Warp wrote:
> Darren New<dne### [at] sanrrcom> wrote:
>> Then the old heap is in oldheap and the new heap is in newheap.
>
> Is this supposed to be efficient?
Modifying log N nodes of the old heap to construct the new one? I'd say
it's reasonably efficient, yes.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible <voi### [at] devnull> wrote:
> On 06/09/2011 04:03 PM, Warp wrote:
> > Darren New<dne### [at] sanrrcom> wrote:
> >> Then the old heap is in oldheap and the new heap is in newheap.
> >
> > Is this supposed to be efficient?
> Modifying log N nodes of the old heap to construct the new one? I'd say
> it's reasonably efficient, yes.
Not modifying. *Copying*. There's a huge difference. (All in-place data
containers and algorithms *modify* the elements, that's not the problem.
The problem I see there with Haskell is that it *copies* the elements.)
(Also: Imagine that the elements of the heap had some mutable data
container in them. Of course that's not purely functional anymore, but
AFAIK that's *possible* in Haskell. How can you avoid having to copy the
entire tree when you insert or remove a node? It's not like the new heap
and the old heap could share some of the nodes, because if you modify the
mutable container of one of those nodes, the other heap is going to see
the modification.)
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible <voi### [at] devnull> wrote:
> On 06/09/2011 04:05 PM, Warp wrote:
> > Invisible<voi### [at] devnull> wrote:
> >> On 05/09/2011 07:45 PM, Warp wrote:
> >
> >>> The lack of separators is also confusing to someone who is accustomed to
> >>> programming languages that use separators.
> >
> >> Don't try Lisp. ;-)
> >
> > I thought Lisp separates everything with parentheses.
> In Haskell, you say
> abc def ghi
Are those three commands or one command with two arguments?
> In Lisp, you say
> (abc def ghi)
Because, AFAIK, that is the latter.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>>> I thought Lisp separates everything with parentheses.
>
>> In Haskell, you say
>
>> abc def ghi
>
> Are those three commands or one command with two arguments?
That's the function "abc" with arguments "def" and "ghi". In more
typical syntax, you would write
abc(def, ghi)
>> In Lisp, you say
>
>> (abc def ghi)
>
> Because, AFAIK, that is the latter.
Indeed.
I suppose the major difference is that in Haskell, you can write
1 + 2
whereas in Lisp, you say
(+ 1 2)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>>>> Then the old heap is in oldheap and the new heap is in newheap.
>>>
>>> Is this supposed to be efficient?
>
>> Modifying log N nodes of the old heap to construct the new one? I'd say
>> it's reasonably efficient, yes.
>
> Not modifying. *Copying*. There's a huge difference.
Not really. We're talking about 4 machine words. Modifying one of those
words would be faster than copying all 4 of them, but I doubt that the
speed difference is astronomical. I'm sure C++ passes bigger structs
than that by value all the time...
> (All in-place data
> containers and algorithms *modify* the elements, that's not the problem.
> The problem I see there with Haskell is that it *copies* the elements.)
>
> (Also: Imagine that the elements of the heap had some mutable data
> container in them. Of course that's not purely functional anymore, but
> AFAIK that's *possible* in Haskell. How can you avoid having to copy the
> entire tree when you insert or remove a node? It's not like the new heap
> and the old heap could share some of the nodes, because if you modify the
> mutable container of one of those nodes, the other heap is going to see
> the modification.)
I'm not really following what you're trying to say here.
If you're saying "immutable structures are inefficient", I'd have to say
that I'll take the vast increase in reliability, maintainability,
flexibility and so forth over a few percent performance hit.
If you're saying "if you put mutable data into an immutable container,
things can go wrong", I'd say don't do that. Unless you really clearly
understand the implications and there's some advantage to doing it this way.
I would like to point out that the whole /benefit/ of a min-heap is that
it provides O(1) access to the minimum element. Well, that's only
possible because of the heap invariant - i.e., because data is stored in
semi-sorted order. If you can mutate the elements, you can trivially
break that invariant.
If you implemented this in Java or Pascal, you'd write a note in the
documentation saying "please don't mutate the elements in a way that
changes their relative ordering". In Haskell, you can make it so people
/can't/ change the relative ordering.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible <voi### [at] devnull> wrote:
> >>> I thought Lisp separates everything with parentheses.
> >
> >> In Haskell, you say
> >
> >> abc def ghi
> >
> > Are those three commands or one command with two arguments?
> That's the function "abc" with arguments "def" and "ghi". In more
> typical syntax, you would write
> abc(def, ghi)
So Lisp does use parentheses as separators.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 06/09/2011 04:57 PM, Warp wrote:
> Invisible<voi### [at] devnull> wrote:
>>>>> I thought Lisp separates everything with parentheses.
>>>
>>>> In Haskell, you say
>>>
>>>> abc def ghi
>>>
>>> Are those three commands or one command with two arguments?
>
>> That's the function "abc" with arguments "def" and "ghi". In more
>> typical syntax, you would write
>
>> abc(def, ghi)
>
> So Lisp does use parentheses as separators.
No, I'm saying that's what you'd write in C or Java or whatever. In Lisp
you'd say (abc def ghi), like I originally posted.
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 9/6/2011 8:03, Warp wrote:
> Darren New<dne### [at] sanrrcom> wrote:
>> Then the old heap is in oldheap and the new heap is in newheap.
>
> Is this supposed to be efficient?
If your functional language is pure enough, your compiler can often optimize
out the apparent inefficiency. Of course, that requires a Sufficiently Smart
Compiler.
In practice, it's less efficient, but not as obviously awful as it would appear.
--
Darren New, San Diego CA, USA (PST)
How come I never get only one kudo?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New <dne### [at] sanrrcom> wrote:
> On 9/6/2011 8:03, Warp wrote:
> > Darren New<dne### [at] sanrrcom> wrote:
> >> Then the old heap is in oldheap and the new heap is in newheap.
> >
> > Is this supposed to be efficient?
> If your functional language is pure enough, your compiler can often optimize
> out the apparent inefficiency. Of course, that requires a Sufficiently Smart
> Compiler.
Hmm, for the compiler to be able to elide the copying and make the changes
in-place, it would have to know for sure that those nodes that are being
changed are not being referenced from anywhere else in the program. (Because,
obviously, if they are referenced by something else, that something else is
going to see the change although it shouldn't.)
I'm not sure how a compiler would be able to do that in a complex program
where nodes and containers are being passed around.
(Of course the copying is not a big deal if each node contains eg. a
couple of integers. However, it begins to matter if they contain for example
large strings, which isn't all that unusual.)
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
