On 9/5/2011 14:36, Warp wrote:
>    What happens to the old heap?

It's functional. The old heap is still in x, where you passed it in. Or x'. 
Or something like that.

You would have to say
   newheap := insert 27 oldheap
or some such. Then the old heap is in oldheap and the new heap is in newheap.

-- 
Darren New, San Diego CA, USA (PST)
   How come I never get only one kudo?

Post a reply to this message

>
> PS. I just discovered that you can create local operator names in the
> same way that you create local variables. So you can make a function
> where the same operator name changes its meaning on each recursive call
> to the function. How evil is that?
>

That's an uterly devilish and abominaly sadistic way to obfuscate your code.
It's totaly /beyong/ *EVIL*.

Post a reply to this message

On 06/09/2011 02:29 AM, Alain wrote:

>
>>
>> PS. I just discovered that you can create local operator names in the
>> same way that you create local variables. So you can make a function
>> where the same operator name changes its meaning on each recursive call
>> to the function. How evil is that?
>>
>
> That's an uterly devilish and abominaly sadistic way to obfuscate your
> code.
> It's totaly /beyong/ *EVIL*.

Heh. If Haskell had obfuscated coding contests...

...my god, it's too terrifying to imagine! o_O

Post a reply to this message

On 05/09/2011 11:19 PM, Darren New wrote:
> On 9/5/2011 14:36, Warp wrote:
>> What happens to the old heap?
>
> It's functional. The old heap is still in x, where you passed it in. Or
> x'. Or something like that.

Actually, x' is the new element you're inserting, not the heap. I didn't 
give the heap itself a variable name at all.

> You would have to say
> newheap := insert 27 oldheap
> or some such. Then the old heap is in oldheap and the new heap is in
> newheap.

Quite.

(Although the actual syntax calls for "=", not ":=", but whatever.)

Post a reply to this message

>>>     This is a good example of where it becomes confusing.
>
>> I think part of it may be that you're thinking "insert" actually inserts
>> something in the heap. Nope! "insert" is a function that when given a value
>> and a heap, gives you back the new heap you would have were you to insert
>> that given value into that given heap.

I'm not sure a person unfamiliar with Haskell would even get that far.

>    What happens to the old heap?

Nothing. (That's exactly the point, of course.)

If nobody is using the old heap any more, the garbage collector will 
remove it at some point.

If you /really/ wanted to split hairs, the insert function is only 
duplicating log N heap nodes. The remaining N - log N nodes (and the 
data they point to) are shared between the old and new heaps. And if the 
old heap is no longer needed, the log N nodes it doesn't share with the 
new heap will automatically be removed eventually.

And if you really, really want to get picky, actually saying

   heap' = insert 27 heap

merely creates an expression node which heap' points to. Only if you 
attempt to /inspect/ this heap is any code executed. (And even then, 
inspecting each node only causes that single node to be constructed. 
It's child nodes remain unevaluated until you look at them.)

Post a reply to this message

On 05/09/2011 07:45 PM, Warp wrote:
> Orchid XP v8<voi### [at] devnull>  wrote:
>>     insert :: Ord x =>  x ->  MinHeap x ->  MinHeap x
>>     insert x' (Leaf        ) = Node x' Leaf Leaf
>>     insert x' (Node x h0 h1) = Node (min x x') (insert (max x x') h1) h0
>
>    This is a good example of where it becomes confusing. Even after
> studying it for a few minutes I can't really figure out what is it
> that it's doing.

The first line is a type signature. It says

   "For any type x which has ordering operations, this function takes an 
x and a MinHeap x and returns a MinHeap x."

The next two lines define the function. Each line conceptually means "if 
the function call looks like the thing on the left, the result looks 
like the thing on the right".

Therefore, if I were to write

   insert 5 Leaf

it should be just as if I had written

   Node 5 Leaf Leaf

The general rule of Haskell is that any name that begins with a *lower 
case* letter is a variable name. (This isn't merely a convention, it is 
formally part of the actual language syntax.) This is why "x" is a 
variable name, but "Leaf" is not.

(If you're paying attention, you'll notice that "insert" is a variable 
name by these rules. In Haskell, a named function is simply a named 
variable who's value just happens to be a function. Which is kinda 
weird, but consistent.)

So, textually, insert 5 Leaf means Node 5 Leaf Leaf. Operationally, what 
does that actually /mean/? Well, in more typical syntax it would be 
something like

   MinHeap insert(x)
   {
     MinHeap out = new MinHeap_Node();
     out.datum = x';
     out.child0 = Leaf.singleton;
     out.child1 = Leaf.singleton;
     return out;
   }

(Since "Leaf" has no data fields, it is essentially a global constant.) 
In other words, we're constructing a new Node object and setting it to 
point to the new datum we're inserting, and setting both of its children 
to be the empty heap.

So how about that last line?

   insert x' (Node x h0 h1) = ...

So if you're inserting into a heap that /isn't/ empty, then

   x' is the thing you want to insert.
   x is the datum in the root node of the heap.
   h0 is the left child of the root node.
   h1 is the right child of the root node.

Given that, the right-hand side says

   ... = Node (min x x') (insert (max x x') h1) h0

That parses basically as

   ... = new Node(min(x, x'), insert(max(x, x'), h1), h0);

In other words, create a new heap node, where the datum is x or x', 
whichever is lowest. The left child is the result of running 
insert(max(x, x'), h1) - in other words, recursively insert x or x' 
(whichever is highest) into h1. The right child is h0.

So, we compare the existing root datum to the new datum, and keep the 
lowest one in the new root node. We then recursively insert the other 
datum into one of the child heaps.

Notice carefully how h0 and h1 get swapped around. This keeps the heap 
balanced. (If you stare at delete_top, you'll see it also swaps the 
children around - and deletes from the other side.) I haven't formally 
proven it, but I /think/ this arrangement keeps the tree balanced for 
all valid operation sequences. Certainly it does if you repeatedly 
insert items; I'm not 100% sure about interleaved inserts and deletes.



So really, there's two ways to interpret Haskell functions. You can view 
each one as a textual substitution. Given pencil and paper, you can 
expand out the work that each one does. For example:

   insert 1 (insert 2 (insert 3 (insert 4 empty)))
   insert 1 (insert 2 (insert 3 (insert 4 Leaf))) [Because empty = Leaf]
   insert 1 (insert 2 (insert 3 (Node 4 Leaf Leaf)))
   insert 1 (insert 2 (Node 3 (insert 4 Leaf) Leaf))
   insert 1 (insert 2 (Node 3 (Node 4 Leaf Leaf) Leaf))
   insert 1 (Node 2 (insert 3 Leaf) (Node 4 Leaf Leaf))
   insert 1 (Node 2 (Node 3 Leaf Leaf) (Node 4 Leaf Leaf))
   Node 1 (insert 2 (Node 4 Leaf Leaf)) (Node 3 Leaf Leaf)
   Node 1 (Node 2 (insert 4 Leaf) Leaf) (Node 3 Leaf Leaf)
   Node 1 (Node 2 (Node 4 Leaf Leaf) Leaf) (Node 3 Leaf Leaf)

It's not hard to throw together a little program that shunts text around 
like this. (Although the brackets are fiddly if you want to do it right.)

If you draw a little graph, the final expression there looks like

                     Node 1
         Node 2                 Node 3
     Node 4   Leaf           Leaf    Leaf
   Leaf Leaf

Which is a balanced tree. (As balanced as a tree containing 4 items can 
be, anyway.)

So textually, that's how to run Haskell. Operationally, the thing on the 
left checks which "constructor" is present (i.e., whether a node is a 
Leaf or a Node), and then binds variables to things. It then constructs 
the value described on the right.

It's not shown in my example, but the notation is quite powerful. It 
lets you do things like inspect multiple levels of the tree:

   rotate :: MinHeap x -> MinHeap x
   rotate (Node x1 (Node x2 c1 c2) c3) = Node x2 c1 (Node x1 c2 c3)

That's a tree rotation [which obviously isn't a valid thing to do to a 
min-heap tree, but you get the idea]. Every time "Node" appears on the 
left, it means "this part has to be a Node object". Every time it 
appears on the right, it means "please construct a new Node object".

Once you get over the notation, it's actually a very clear and succinct 
way to work. Consider the alternative:

   function rotate(root)
   {
     if (root.type == "node")
     {
       x1 = root.datum;
       c3 = root.child1;
       child = root.child0;
       if (child.type == "node")
       {
         x2 = child.datum;
         c1 = child.child0;
         c2 = child.child1;
         return new Node(x2, c1, new Node(x1, c2, c3));
       }
     }
   }

All that code to do the same thing as the 1-liner above. Not only is the 
Haskell version shorter, it's clearer: It says "my input must look like 
THIS, and then I will change it to look like THAT". You don't have to 
mentally execute a series of one-at-a-time baby steps to see what's 
happening. It's a bit like

   temp1 = 1 + 2;
   temp2 = 3 + 4;
   temp3 = temp1 * temp2;
   temp4 = temp3 ^ 2;

verses

   temp4 = ((1+2) * (3+4))^2;

The latter is not only shorter, but infinitely clearer.



...again, "more maybe I'm just delusional"...

Post a reply to this message

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. ;-) (Or Smalltalk. Or Tcl. Or...)

Anyway, just for giggles, I wanted to see if I could hack the language 
hard enough to make it support separators. The answer is... yeah, kinda.

   insert|< 5 # my_heap >|j

I can't get it to use a comma, colon, semicolon or any similarly 
separator-like symbol, since these are all reserved symbols. The best I 
could manage is #, @, $ or similar. (I did try more unusual Unicode 
symbols, but that crashed the compiler - ridiculously enough...)

Obviously, the way I did this was to define some new operators. I could 
have gone for

   insert< 5 # my_heap >j

except that "<" and ">" are already in use. (You can reuse them... but 
would you want to?)

You may also notice the stray "j" at the end. That's not a semicolon, 
it's the letter J. Haskell doesn't support unary operators, only binary. 
So the final >| must have two operands. It actually ignores the second one.

The code is quite simple:

   f |< x = f x
   f #  x = f x
   x >| y = x
   j = undefined

That's literally it.

Post a reply to this message

On 06/09/2011 11:23 AM, Invisible wrote:

> Anyway, just for giggles, I wanted to see if I could hack the language
> hard enough to make it support separators. The answer is... yeah, kinda.
>
> insert|< 5 # my_heap >|j

I managed to go one better:

   insert&(5, my_heap)

Works for any valid Haskell function. With one small catch:

   foo&() -- Works fine.
   foo&(1) -- Doesn't work at all.
   foo&(1, 2) -- Works fine.
   foo&(1, 2, 3) -- Works fine.
   ...

Basically, the syntax "(1, 2, 3)" defines what Haskell calls a "tuple". 
You can write functions that accept a tuple:

   add (x, y, z) = x + y + z

You then then write "add (1, 2, 3)", but due to Haskell's parsing rules, 
"add(1, 2, 3)" (without the space) is also valid. And looks exactly like 
a function call in any other language.

Trouble is, it works only if the function you call is /expecting/ a 
tuple. As far as Haskell is concerned, "add" is a 1-argument function, 
not a 3-argument function.

With some clever type hackery, you can make a "&" operator (or any other 
operator name you'd like, providing it isn't reserved) that "un-tuples" 
a tuple. Using this, you can supply tuples to any existing Haskell function.

There's a glitch, however: Haskell is tuple sizes from 2 upwards. (IIRC, 
the language spec guarantees that sizes up to 5 will exist.) Haskell 
also has a size-zero tuple, commonly used as a dummy value for when you 
don't actually need to put data somewhere. But it doesn't have a size-1 
tuple. Because, let's face it, what would be the point of that?

As a result of this, foo&(5) is actually foo&5. And I can't get it so 
that that works. I can make it so a different sort of bracket works, or 
a different operator works, but I can't make it consistent with the rest.

And so ends today's lesson in raping your language syntax. :-)

{-# LANGUAGE TypeFamilies, MultiParamTypeClasses, FlexibleInstances #-}

module Test where

class Tuple t r where
   type Function t r :: *
   (&) :: Function t r -> t -> r

instance Tuple () r where
   type Function () r = r
   f & () = f

instance Tuple (x,y) r where
   type Function (x,y) r = x -> y -> r
   f & (x,y) = f x y

instance Tuple (x,y,z) r where
   type Function (x,y,z) r = x -> y -> z -> r
   f & (x,y,z) = f x y z

instance Tuple (x,y,z,w) r where
   type Function (x,y,z,w) r = x -> y -> z -> w -> r
   f & (x,y,z,w) = f x y z w

Post a reply to this message

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?

-- 
                                                          - Warp

Post a reply to this message

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.

-- 
                                                          - Warp

Post a reply to this message