in reply to
Capturing parenthesis and grouping square brackets

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) } }

In Section
Meditations