Beefy Boxes and Bandwidth Generously Provided by pair Networks
We don't bite newbies here... much
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??
Hi

Introduction

I'm doing a case study to simulate Perl6 -Meta-Operators in Perl5 and I'm stuck with a special when restricting myself to pure FP.

See for instance the Cross operator X

<a b> X 1,2 X <x y> #produces ('a', 1, 'x'), ('a', 1, 'y'), ('a', 2, 'x'), ('a', 2, 'y'), ('b', 1, 'x'), ('b', 1, 'y'), ('b', 2, 'x'), ('b', 2, 'y')

can be simulated with

pp X {"a".."d"}; pp X {"a".."b"} X {1..2} X {'x','y'}; my $iter = X {"a","b"} X {1..2} X {'x','y'}; while ( my ($aref)= $iter->() ) { pp $aref; } __DATA__ (["a"], ["b"], ["c"], ["d"]) ( ["a", 1, "x"], ["a", 1, "y"], ["a", 2, "x"], ["a", 2, "y"], ["b", 1, "x"], ["b", 1, "y"], ["b", 2, "x"], ["b", 2, "y"], ) ["a", 1, "x"] ["a", 1, "y"] ["a", 2, "x"] ["a", 2, "y"] ["b", 1, "x"] ["b", 1, "y"] ["b", 2, "x"] ["b", 2, "y"]

Where X is a function with signature (&;$) which accepts an iterator as second argument and returns an iterator.

So in LIST context it produces the whole array in scalar context it just returns a lazy iterator. (i.e. allowing infinite lists)

This functions (and similar others) can be nested and produce nice syntactic sugar, for instance the above has the following precedence

 X {"a","b"} ( X {1..2} ( X {"x","y"} ) )

Here my purely functional implementation so far.

(Please note that this is a case study for the API and not optimized for speed. A well designed and tested set of such operators could be optimized and/or reimplemented in XS later, w/o messing with the P5's parser while being as closs as possible to P6 semantics.)

use strict; use warnings; use feature qw/say/; use Data::Dump qw/pp/; sub gen_listiter { my @init=@_; my @list=@init; sub { if (@list) { return shift @list } else { @list=@init; return () } } } sub get_array { my $iter=shift; my @res; while ( my ($res)= $iter->() ) { push @res,$res; } return @res; } my %operations =( '+' => sub { defined $_[1] ? $_[0] + $_[1]->[0] : $_[ +0] }, ); sub X (&;$) { my ($cr,$tail_itr)=@_; # my $op = $operations{$tail_itr} if defined $tail_itr; # undef $tail_itr if $op; $tail_itr //= gen_listiter([]); my $head_itr = gen_listiter($cr->()); my $state='INIT'; my $head; my $tail; my $op //= sub { [ $_[0],@{$_[1]} ] }; my $cross_itr = sub { goto $state; INIT: $state="RESUME"; while ( ($head) = $head_itr->() ) { while ( ($tail) = $tail_itr->() ) { return $op->($head,$tail); RESUME: } } $state='INIT'; return; }; if (wantarray) { return get_array($cross_itr); } else { return $cross_itr; } } pp X {"a".."d"}; pp X {"a".."b"} X {1..2} X {'x','y'}; my $iter = X {"a","b"} X {1..2} X {'x','y'}; while ( my ($aref)= $iter->() ) { pp $aref; }

Extension

Perl6 also allows to use sub-operators which are applied to each combination, like:

my @a = 1, 2; my @b = 3, 4; my @c = @a X+ @b; # 1+3, 1+4, 2+3, 2+4

this could be simulated by passing a string or a anonymous sub in the last parameter slot.

my @a = 1, 2; my @b = 3, 4; my @c = X{@a} X{@b} '+'

An operator symbol like '+' would just be looked up and produce something like 'sub {$a+$b}' to be applied.

Problem

Only the rightmost X has the information about the operation and there is only one slot free to pass an iterator.

Is it possible to write the intermediate (and final) iterators in a purely functional way that the operation (here plus) is incapsulated within the logic of the passed iterators?

Of course there are ways to cheat with OOP by blessing/tying the iterator-ref and returning the operation with something like $op = $iter->get_op()

Another (ugly) way is to check the passed parameters within the iterator  $op = $iter->("get_op")

One functional solution could be that all nested iterators just call the next one and append the values so far, and the lowest nested iterator encapsulates the operation and adds over all values  reduce {$a+$b} @_ and returns the result thru all levels.

This approach is less optimal, since it inhibits any benefit from memoization, cause sum($a,$b,$c) = sum($a, sum($b,$c)), so many intermediate results from subtrees could be cached. Memoization would result in an extreme performance boost.

I hope my intention is clear now, I don't know there is a solution but it helped talking about it. =)

So there are work arounds but I wonder if a purely functional approach with just one passed function is possible...

Cheers Rolf

( addicted to the Perl Programming Language)

update

PS: If you are wondering about the title ... I was in a hurry and my brain entered a German word so s/mit/with/. :)


In reply to Simulating Perl6 Meta/Hyper operators with pure Functional Programming by LanX

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • Outside of code tags, you may need to use entities for some characters:
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others pondering the Monastery: (6)
    As of 2014-09-20 13:00 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      How do you remember the number of days in each month?











      Results (159 votes), past polls