Haskell vs Perl 6 (was Re: Capturing parenthesis and grouping square brackets)

[raiph]

I've moved this comment to top level from here so code formatting is sane.

---

Jenda said:

No, I don't think Perl5ers would find the {P6 example below} most approachable. ... I would find the Haskell version much easier to explain.

I've explained the P6 code below. Would you (or someone else) be willing to explain the Haskell code to me or P5ers who don't know Haskell?

---

Problem definition: Write a routine that will compare the leaves ("fringe") of two binary trees to determine whether they are the same list of leaves when visited left-to-right.

Solutions:

=== haskell ===


data Tree a = Leaf a | Node (Tree a) (Tree a)
    deriving (Show, Eq)
 
fringe :: Tree a -> [a]
fringe (Leaf x) = [x]
fringe (Node n1 n2) = fringe n1 ++ fringe n2
 
sameFringe :: (Eq a) => Tree a -> Tree a -> Bool
sameFringe t1 t2 = fringe t1 == fringe t2

 

=== Perl 6 ===

sub fringe ($tree) {

    multi sub fringey (Pair $node) { fringey $_ for $node.kv }
    multi sub fringey ( Any $leaf) { take $leaf }                

    (gather fringey $tree), Cool;
}
 
sub samefringe ($a, $b) { all fringe($a) Z=== fringe($b) }

---

And now the P6 code again with my explanatory comments:

sub fringe ($tree) {                  # $tree is aliased to $a passed
                                      # by the fringe($a) call below.

    multi sub fringey (Pair $node)    # multi sub means other sub defs
                                      # will use the same sub name.

                                      # Pair is a builtin type.
                                      # It's like a one element hash.

                                      # $node is "type constrained" -
                                      # it may only contain a Pair.

        { fringey $_ for $node.kv }   # .kv is a method that returns
                                      # (key, value) of a Pair.

                                      # fringey is called twice, with
                                      # key as arg then value as arg.
                                      # If arg is a Pair, call this
                                      # fringey recursively. If not,
                                      # call sub fringey(Any $leaf).

    multi sub fringey (Any $leaf)     # Each multi sub def must have a
                                      # different signature (params).
                                      # This def's param has Any type.

        { take $leaf }                # take yields a value that is
                                      # added to a gather'd list.

    (gather fringey $tree), Cool;     # This gather lazily gathers a
                                      # list yielded by take $leaf's.

                                      # Calls to fringe return a list.
                                      # Cool is a flavor of undef.

    }
 
    sub samefringe ($a, $b)           # $a and $b are binary trees
                                      # built from Pairs eg:
                                      # $a = 1=>((2=>3)=>(4=>5));
                                      # $b = 1=>2=>(3=>4)=>5;
                                      # $c = 1=>2=>(4=>3)=>5;
                                      # samefringe($a,$b) # True
                                      # samefringe($a,$c) # False

        { all                         # Builtin "all" returns True if
                                      # all following items are True.
                                      # Parallelizes & short-circuits.

          fringe($a)

          Z===                        # === returns True if its LHS
                                      # and RHS are the same value.
                                      # Z is the zipwith metaop.
                                      # Z=== does === between each of
                                      # the items in the LHS list with
                                      # each of those in the RHS list.

          fringe($b)
        }

}

[BrowserUk]

Would you (or someone else) be willing to explain the Haskell code to me or P5ers who don't know Haskell?

With license:

=== haskell ===

--data type Tree is 
--either 
--    a Leaf containing a single item (of type a)
-- or
--   a Node containing two subtrees (that can have leaves of type a)
data Tree a = Leaf a | Node (Tree a) (Tree a)
-- and it inherits 'methods' / 'roles' from types Show and Eq,
   deriving (Show, Eq)

-- Fringe is a function that extracts a list of type a from a tree con
+taining type a
fringe :: Tree a -> [a]

-- If its argument is of type leaf
-- it returns a single element list containing the element held in the
+ leaf
fringe (Leaf x) = [x]

-- If its argument is a Node
-- it returns the list returned by the left subtree 
-- concatenated to the list returned by the right subtree
fringe (Node n1 n2) = fringe n1 ++ fringe n2

-- sameFringe takes two Trees as its arguments
-- and uses the == method inherited/included from the Eq role
-- to compare the lists returned from the two trees for equality
-- returning true if they are the same.
sameFringe :: (Eq a) => Tree a -> Tree a -> Bool
sameFringe t1 t2 = fringe t1 == fringe t2

Personally, I find the Perl6 far easier to read. I'd be very happy to use Perl6 if it had threading and ran at perl5 speed.

[Jenda]

I'd add a note saying something like "While the code looks like the two trees are flattened to lists first and then compared, Haskell is lazy, which means that behind the scenes it will only do as much work as it has to and stop flattening once it finds the first mismatch. Simply don't worry about it. It works."

I've read both codes and both explanations (the fact that the one for Haskell is quite a bit shorter is telling. On a Perl forum.) and still think the Haskell code is much clearer and cleaner.

A better explanation of the Perl6 code might help somewhat. "take yields a value that is added to a gather'd list." Humpf?!? "Cool is a flavor of undef." Whatafuck?

Heck the all fringe($a) Z=== fringe($b) alone is crazy enough to require two pages of explanation.

[BrowserUk]

A better explanation of the Perl6 code might help somewhat.

If you look at Re: Challenge: Perl 5: lazy sameFringe()? (threads::Gather Configurably truely lazy or semi-lazy), you see a Perl5 implementation that more closely mirrors the Haskell variant.

It uses a home brewed implementation of take & gather that uses a thread and a queue under the covers to provide a truly lazy process.

That homebrew take/gather looks like this:

#! perl -slw
package threads::Gather;
use strict;
use Exporter;
use threads;
use threads::Q;

our @ISA = qw[ Exporter threads::Q ];
our @EXPORT = qw[ take gather ];

sub take;

sub gather (&$@) {
    no strict 'refs';# no warnings 'redefine';
    my( $code, $Qsize ) = ( shift, shift );
    my $Q = threads::Q->new( $Qsize );
    my $caller = caller;
    local *{ "$caller\:\:take" } = sub (_) { $Q->nq( @_ ); };
    local $^R = $code;
    async( sub{ &$code; $Q->nq( undef ); }, @_ )->detach;
    return sub { $Q->dq; };
}

return 1 if caller;

The take() sub is only available within the gather code block, and simple pushes its argument(s) onto a queue.

The code block itself is run in a separate thread; and the return of the gather sub is an iterator that simply dequeues values from the queue.

If teh size of the queue is set to 1, then each it take() will block the queue until the value it pushed is popped off using the iterator.

Not efficient -- a thread swap for every leaf -- but truly lazy.

If you supply a bigger queue size than one -- on the call to gather(), then gather block will be able to take() that many values before blocking and a thread swap is forces; thus you get a 'batching' behaviour which is more efficient.

This is (I suspect) the intent of the perl6 take/gather "at some future point in time", but currently it take is simply a push to a hidden array and once all the values have been collected, the gather subroutine iterates over that array popping them off as it goes. (See Perl6::Gather for a crude Perl5 implementation.)

But, as of yet -- and if I am any judge, for the foreseeable future -- that "at some future point in time" is unlikely to ever arrive.

Not that threading is the only way a lazy take/gather could be implemented. It could be done today in Perl5 using Coro if that runs where you live.

It could also be done using green (user space) threading; or continuations; or go-style goroutines. And if you believe the P6 specs, it intends to support all of those and more.

But, when (to my knowledge) there has been no (ZERO) attempt to provide and flavour of multitasking in any of the p6-ish interpreters, it doesn't look likely. YOU cannot add this stuff successfully as an after thought; you have to architect it in from the ground up or you end up with iThreads or similar.

And it is actually quite easy to do, if you do it from the start. As soon as the run-loop/dispatcher is capable of executing any single opcode, it should be possible to start two copies each in its own thread and dispatch them concurrently.

Heck the all fringe($a) Z=== fringe($b) alone is crazy enough to require two pages of explanation.

I'm far from expert in P6, but I don't have a problem with that line. The Z=== looks a bit weird, (but so did <=> and =~ etc. when I first came to perl5), but its obviously some form of comparison operator.

all is like the function of the same name in List::MoreUtils. Only true if all the arguments are true, and short-circuiting as soon as the first one is false.

So, if all the fringes of $a are equal to all the fringes of $b, the trees are equivalent. Seems clear enough, even if I'd have to look up the details. (I had to do that for the Haskell code; and I often have to do the same for C-runtime routines and the more obscure Perl built-ins.)

[raiph]

I'd add a note saying something like "While the code looks like the two trees are flattened to lists first and then compared, Haskell is lazy, which means that behind the scenes it will only do as much work as it has to and stop flattening once it finds the first mismatch. Simply don't worry about it. It works."

This is misleading, as it suggests that P6's gather/take is not lazy. Would you be willing to update your comment to fix this mistake?

Update: I was wrong. Apologies to Jenda.