 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 05/09/2011 09:52 AM, Invisible wrote:
> ...or maybe I'm just delusional from having spent too long with Haskell?
Trivial program... is trivial.
It seems everybody agrees on that. Now let's try the sort of code that
typically appears in an introductory Haskell textbook:
module Heap
(
MinHeap (), empty, is_empty,
top, insert, delete_top,
union, size, to_list, from_list, heap_sort
)
where
data MinHeap x = Leaf | Node x (MinHeap x) (MinHeap x)
empty :: MinHeap x
empty = Leaf
is_empty :: MinHeap x -> Bool
is_empty Leaf = True
is_empty _ = False
top :: MinHeap x -> x
top (Leaf ) = error "empty heap"
top (Node x _ _) = x
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
delete_top :: Ord x => MinHeap x -> MinHeap x
delete_top (Leaf ) = error "empty heap"
delete_top (Node _ h0 h1) = union h0 h1
union :: Ord x => MinHeap x -> MinHeap x -> MinHeap x
union h0 h1 =
case (h0, h1) of
(Leaf, _ ) -> h1
(_ , Leaf) -> h0
(_ , _ ) ->
if top h0 < top h1
then Node (top h0) h1 (delete_top h0)
else Node (top h1) h0 (delete_top h1)
size :: MinHeap x -> Int
size (Leaf ) = 0
size (Node _ h0 h1) = 1 + size h0 + size h1
to_list :: Ord x => MinHeap x -> [x]
to_list (Leaf ) = []
to_list (Node x h0 h1) = x : to_list (union h0 h1)
from_list :: Ord x => [x] -> MinHeap x
from_list = foldr insert empty
heap_sort :: Ord x => [x] -> [x]
heap_sort = to_list . from_list
(This one - or something resembling it - appears in "The Fun of
Programming", Jeremy Gibbons & Oege de Moor, Palgrave Macmillan, in
chapter 1. Then again, strictly this isn't a book about learning
Haskell. It's about functional programming in general - as best as I can
tell...)
This is classic functional programming. The only thing missing is that
there's no high-order functions or type-level programming. It's got just
about everything else. Now let's see if Warp's claims hold up.
While the identifier names are strongly suggestive, I doubt anybody not
mildly fuent in Haskell is going to figure out what's actually going on
here. I'll post a Java translation in a minute. Then we can see whether
the program becomes clearer (i.e., Haskell is the problem) or remains
opaque (i.e., the algorithm is the problem).
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 05/09/2011 07:17 PM, Orchid XP v8 wrote:
> While the identifier names are strongly suggestive, I doubt anybody not
> mildly fuent in Haskell is going to figure out what's actually going on
> here. I'll post a Java translation in a minute. Then we can see whether
> the program becomes clearer (i.e., Haskell is the problem) or remains
> opaque (i.e., the algorithm is the problem).
OK, so attempting to compare like for like, here's the most "natural"
way I could think of to implement this in Java:
public abstract class MinHeap
{
public abstract bool is_empty();
public abstract int top();
public abstract MinHeap insert(int x);
public abstract MinHeap delete_top();
public abstract MinHeap union(MinHeap h);
public abstract int size();
}
public class MinHeap_Emtpy extends MinHeap
{
private MinHeap_Empty() {}
public static MinHeap_Empty empty = new MinHeap_Empty();
public bool is_empty() {return true;}
public int top() // Throw exception
public MinHeap insert(int x)
{return new MinHeap_Node(x, null, null);}
public MinHeap delete_top() // Throw exception
public MinHeap union(MinHeap h) {return h;}
public int size() {return 0;}
}
public class MinHeap_Node extends MinHeap
{
public int datum;
public MinHeap child0, child1;
public bool is_empty() {return false;}
public int top() {return this.datum;}
public MinHeap insert(int x)
{
let h = this.datum;
let l = x;
if (h < l) {h = x; l = this.datum;}
return new MinHeap_Node(l, this.child1.insert(h), this.child0);
}
public MinHeap delete_top() {return this.child0.union(this.child1);}
public MinHeap union(MinHeap h)
{
if (h.is_empty()) return this;
MinHeap_Node that = (MinHeap_Node)h;
if (this.datum < that.datum)
return new MinHeap_Node(this.datum, that, this.delete_top());
return new MinHeap_Node(that.datum, this, that.delete_top());
}
public int size()
{return 1 + this.child0.size() + this.child1.size();}
}
Differences:
- I don't know how Java does generics, so this min-heap handles int only.
- I left out the list conversion stuff, because I'm not sure about
Java's container types off the top of my head. The "idiomatic" way is
probably to define an interator or something anyway...
- It's a while since I did Java. This might not actually compile for one
reason or other. (In particular, I'm fuzzy on how auto-constructors work...)
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 <voi### [at] dev null> 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. (Or, more precisely *how* it's doing it. The 'insert'
name makes it obvious what is it that it does, but the code doesn't make
it at all clear how.)
Maybe the problem is that in an imperative language the different
situations would be more explicitly expressed with an 'if...then...else'
block. Here it's not clear at all what is it that the code is expressing.
Of course it doesn't help that the syntax is quite uncommon, and the
meaning of the different operators isn't clear. (For instance, it's unclear
whether the ' is some kind of operator, and if it is, what exactly its role
is. If it isn't an operator but somehow just part of the variable name, it's
highly unusual.)
The lack of separators is also confusing to someone who is accustomed to
programming languages that use separators.
--
- Warp
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.
Hmm, OK. Apparently I've spent longer doing this than I thought...
Is the Java translation any easier to grok? Or is that equally baffling?
> (Or, more precisely *how* it's doing it. The 'insert'
> name makes it obvious what is it that it does, but the code doesn't make
> it at all clear how.)
Well, yeah, you can take a stab at identifier names in most languages.
> Maybe the problem is that in an imperative language the different
> situations would be more explicitly expressed with an 'if...then...else'
> block. Here it's not clear at all what is it that the code is expressing.
I can rephrase it to
insert x' h =
case h of
Leaf -> Node x' Leaf Leaf
Node x h0 h1 -> Node (min x x') (insert (max x x') h1) h0
if you prefer. I don't suppose that's any more enlightening though.
The irony is that "case" is a more powerful version of "if/then/else".
(The latter is rigorously a special-case of the former.) Haskell's
"case" is like what other languages have, on steriods. On the other
hand, if/then/else is pretty self-explanatory, whereas a case-expression
isn't quite so immediately obvious.
The fact that you can write [what appear to be] multiple definitions of
the same function as a short-cut to a case-expression isn't the most
intuitive thing. Until somebody tells you that's what it means.
> Of course it doesn't help that the syntax is quite uncommon, and the
> meaning of the different operators isn't clear.
Sure. You can find strange operators in any language; I guess one of the
biggest things about Haskell is that its syntax just plain /isn't like/
anything else.
C, C++, C#, Java, JavaScript, Pascal and a half-dozen other languages
all have virtually identical function-call syntax, and (apart from
Pascal) the rest of the basic guts of the language has mild syntactic
differences. So if you know any of those languages, you can take a stab
at reading any of the others. Haskell is utterly different. Doesn't even
resemble anything else. (Except other obscure languages like ML.)
> (For instance, it's unclear
> whether the ' is some kind of operator, and if it is, what exactly its role
> is. If it isn't an operator but somehow just part of the variable name, it's
> highly unusual.)
It's not an operator, merely part of the variable name. It's a de facto
Haskell idiom; if you have a variable named foo, the new version of it
is named foo'. (If you have more than two versions, it's probably better
to number them, although you do see people write foo'' and even foo'''.)
Apparently it's supposed to look like the mathematical "prime" symbol
(which is more usually used for derivatives, actually).
I'll grant you that one's /highly/ non-obvious. I could perhaps have
called it y instead of x' for increased clarity. That's only one of your
points, though.
> The lack of separators is also confusing to someone who is accustomed to
> programming languages that use separators.
Sure. You do see a lot of people look at an expression like
foo x y + z bar
and think to themselves "now what the hell does that mean?" Knowing the
barest bit of Haskell, possible options include:
- foo(x, y + z, bar)
- foo(x, y) + z(bar)
- foo(x, y, +, z, bar)
It's also common for beginner's Haskell code to contain more brackets
than a typical Lisp snippet because it's so disconcerting to figure out.
You apparently can't see far enough into the syntax to realise this, but
I think perhaps part of the problem is the whole symmetry of it all.
The syntax for /inspecting/ data is identical to the syntax for
/constructing/ data. Which makes the language very regular and
beautiful, but it also perhaps makes it rather baffling to anybody
trying to figure out whether you're inspecting or constructing stuff.
The syntax for a tuple /type/ is identical to the syntax for a tuple
/value/. Compare:
('1', 2, 3.4, "five") :: (Char, Int, Double, String)
Thing on the left is data. Thing on the right is a type signature. Now
consider
(x, y, z) :: (x, y, z)
This perfectly valid Haskell expression has three value variables on the
left, and (unrelated but identically named) three type variables on the
right.
The exact same thing happens with list values and list types.
Here, the very symmetry of the language is arguably somewhat baffling.
Patterns look like expressions. Types look like values. Once you know
Haskell modestly well, you realise that patterns /only/ go in certain
places, and everything else is an expression. Types /only/ go in certain
places, so everything else is values. But until you reach that point,
the language design certainly isn't helping you much.
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?
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 9/5/2011 11:45, 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. (Or, more precisely *how* it's doing it. The 'insert'
> name makes it obvious what is it that it does, but the code doesn't make
> it at all clear how.)
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.
--
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/5/2011 11:45, 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. (Or, more precisely *how* it's doing it. The 'insert'
> > name makes it obvious what is it that it does, but the code doesn't make
> > it at all clear how.)
> 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.
What happens to the old heap?
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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
|
|
| |
| |
|
|
|
|
| |
|
|
