## Wednesday, April 8, 2009

### Higher Order Perl (Python Style) : Chapter 7 - Higher Order Functions And Currying

TOC

### 7.1 Currying

# @tagged_texts = walk_html(\$tree, sub { ['MAYBE', \$_[0]] },
# \&promote_if_h1tag);
# sub promote_if_h1tag {
# my \$element = shift;
# if (\$element->{_tag} eq 'h1') {
# return ['KEEPER', join '', map {\$_->[1]} @_];
# } else {
# return @_;
# }
# }
# my \$tree = shift;
# my @tagged_texts = walk_html(\$tree, sub { ['MAYBE', \$_[0]] },
# \&promote_if_h1tag);
# my @keepers = grep { \$_->[0] eq 'KEEPER' } @tagged_texts;
# my @keeper_text = map { \$_->[1] } @keepers;
# my \$header_text = join '', @keeper_text;
# }
def extender(accum, item):
accum.extend(item)
tagged_texts = walk_html(tree, lambda x: [["MAYBE", x]],
promote_if_h1tag,
extender)
def promote_if_h1tag(element, results):
if element["_tag"] == "h1":
return [["KEEPER", "".join([ _x[1] for _x in results])]]
else:
return results

tagged_texts = walk_html(tree, lambda x: [["MAYBE", x]],
promote_if_h1tag,
extender)
keepers = [x for x in tagged_texts if x[0] == "KEEPER"]
keeper_text = [x[1] for x in keepers]

# sub promote_if {
# my \$is_interesting = shift;
# my \$element = shift;
# if (\$is_interesting->(\$element->{_tag}) {
# return ['keeper', join '', map {\$_->[1]} @_];
# } else {
# return @_;
# }
# }
# my @tagged_texts = walk_html(\$tree,
# sub { ['maybe', \$_[0]] },
# sub { promote_if(
# sub { \$_[0] eq 'h1' },
# \$_[0])
# });
def promote_if(is_interesting, element, results):
if is_interesting(element["_tag"]):
return [["KEEPER", "".join([ _x[1] for _x in results])]]
else:
return results
tagged_texts = walk_html(tree, lambda x: [["MAYBE", x]],
lambda y,z: (promote_if((lambda _y: _y == "h1"), y,z)),
extender)

# sub promote_if {
# my \$is_interesting = shift;
# return sub {
# my \$element = shift;
# if (\$is_interesting->(\$element->{_tag}) {
# return ['keeper', join '', map {\$_->[1]} @_];
# } else {
# return @_;
# }
# }
# }
def promote_if(is_interesting):
def _foo(element, results):
if is_interesting(element["_tag"]):
return [["KEEPER", "".join([ _x[1] for _x in results])]]
else:
return results
return _foo

# my @tagged_texts = walk_html(\$tree,
# sub { ['maybe', \$_[0]] },
# promote_if(sub { \$_[0] eq 'h1' }),
# );
tagged_texts = walk_html(tree, lambda x: [["MAYBE", x]],
promote_if(lambda y: y == "h1"),
extender)

# my (\$s, \$t) = @_;
# return unless \$s && \$t;
# promise { add2(tail(\$s), tail(\$t)) });
# }
# sub mul2 {
# my (\$s, \$t) = @_;
# return unless \$s && \$t;
# promise { mul2(tail(\$s), tail(\$t)) });
# }
if not (t and s):
return None
def mul2(s,t):
if not (s and t):
return None
promise(lambda: mul2(tail(s),tail(t))))

# sub combine2 {
# my (\$s, \$t, \$op) = @_;
# return unless \$s && \$t;
# promise { combine2(tail(\$s), tail(\$t), \$op) });
# }
def combine2(s,t,op):
if not (s and t):
return None
promise(lambda: combine2(tail(s),tail(t), op)))

# sub add2 { combine2(@_, sub { \$_[0] + \$_[1] }) }
# sub mul2 { combine2(@_, sub { \$_[0] * \$_[1] }) }
return combine2(s, t, lambda _s, _t: _s + _t)
def mul2(s,t):
return combine2(s, t, lambda _s, _t: _s * _t)

# sub combine2 {
# my \$op = shift;
# return sub {
# my (\$s, \$t) = @_;
# return unless \$s && \$t;
# promise { combine2(\$op)->(tail(\$s), tail(\$t))});
# };
# }
def combine2(op):
def _foo(s, t):
if not (s and t):
return None
promise(lambda: combine2(op(tail(s), tail(t)))))

return _foo

# \$add2 = combine2(sub { \$_[0] + \$_[1] });
# \$mul2 = combine2(sub { \$_[0] * \$_[1] });
mul2 = combine2(lambda x,y: x*y)

# my \$catstrs = combine2(sub { "\$_[0]\$_[1]" })->(\$s, \$t);
catstrs = combine2(lambda x,y: "%s%s" % (x,y))(s,t)

# sub scale {
# my \$s = shift;
# return sub {
# my \$c = shift;
# return if \$c == 0;
# transform { \$_[0] * \$c } \$s;
# }
# }
def scale(s):
def _foo(c):
if c == 0:
return None
return transform(lambda x: x*c, s)
return _foo

# sub scale {
# my \$c = shift;
# return sub {
# my \$s = shift;
# transform { \$_[0] * \$c } \$s;
# }
# }
def scale(c):
def _foo(s):
return transform(lambda x: x*c, s)
return _foo

# sub slope {
# my (\$f, \$x) = @_;
# my \$e = 0.00000095367431640625;
# (\$f->(\$x+\$e) - \$f->(\$x-\$e)) / (2*\$e);
# }
def slope(f, x):
e = 0.00000095367431640625
return (f(x+e) - f(x-e)) / (2*e)

# sub slope {
# my \$f = shift;
# my \$e = 0.00000095367431640625;
# return sub {
# my \$x = shift;
# (\$f->(\$x+\$e) - \$f->(\$x-\$e)) / (2*\$e);
# };
# }
def slope(f):
e = 0.00000095367431640625
def _foo(x):
return (f(x+e) - f(x-e)) / (2*e)
return _foo

# sub slope {
# my \$f = shift;
# my \$e = 0.00000095367431640625;
# my \$d = sub {
# my (\$x) = shift;
# (\$f->(\$x+\$e) - \$f->(\$x-\$e)) / (2*\$e);
# };
# return @_ ? \$d->(shift) : \$d;
# }
def slope(f, _x=None):
e = 0.00000095367431640625
def d(x):
return (f(x+e) - f(x-e)) / (2*e)
return d(_x) if _x != None else d

# sub iterate_function {
# my (\$f, \$x) = @_;
# my \$s;
# \$s = node(\$x, promise { &transform(\$f, \$s) });
# }
def iterate_function(f, x):
s = node(x, promise(lambda: transform(f, s)))
return s

# sub iterate_function {
# my \$f = shift;
# return sub {
# my \$x = shift;
# my \$s;
# \$s = node(\$x, promise { &transform(\$f, \$s) });
# };
# }
def iterate_function(f):
def foo(x):
s = node(x, promise(lambda: transform(f, s)))
return s
return foo

# *upfrom = iterate_function(sub { \$_[0] + 1 });
upfrom = iterate_function(lambda x: x + 1)

# *pow2_from = iterate_function(sub { \$_[0] * 2 });
pow2_from = iterate_function(lambda x: x * 2)

# sub combine2 {
# my \$op = shift;
# return sub {
# my (\$s, \$t) = @_;
# return unless \$s && \$t;
# promise { combine2(\$op)->(tail(\$s), tail(\$t)) });
# };
# }
def combine2(op):
def _foo(s, t):
if not (s and t):
return None
promise(lambda: combine2(op(tail(s), tail(t)))))

return _foo

# sub combine2 {
# my \$op = shift;
# my \$r;
# \$r = sub {
# my (\$s, \$t) = @_;
# return unless \$s && \$t;
# promise { \$r->(tail(\$s), tail(\$t)) });
# };
# }
def combine2(op):
def r(s,t):
if not (s and t):
return None
promise(lambda: r(tail(s),tail(t))))
return r

### 7.2 Common Higher-Order Functions

# map { \$_ * 2 } (1..5); # returns 2, 4, 6, 8, 10
# grep { \$_ % 2 == 0 } (1..10); # returns 2, 4, 6, 8, 10
## while map exists in python the more usual idiom
## is to use list comprehensions/iterators
[x*2 for x in range(1,6)]
[x for x in range(1,11) if x % 2 == 0 ]

# sub cmap (&) {
# my \$f = shift;
# my \$r = sub {
# my @result;
# for (@_) {
# push @result, \$f->(\$_);
# }
# @result;
# };
# return \$r;
# }
# sub cgrep (&) {
# my \$f = shift;
# my \$r = sub {
# my @result;
# for (@_ ) {
# push @result, \$_ if \$f->(\$_ );
# }
# @result;
# };
# return \$r;
# }
## skipping the more obvious generator solution
def cmap(f):
def r(items):
result = []
for i in items:
result.append(f(i))
return result
return r
def cgrep(f):
def r(items):
result = []
for i in items:
if f(i):
result.append(i)
return result
return r

# \$double = cmap { \$_ * 2 };
# \$find_slashdot = cgrep { \$_->{referer} =~ /slashdot/i };
double = cmap(lambda x: x*2)
find_slashdot = cgrep(lambda x: "slashdot" in x["referer"].lower())

# sub cmap (&;@) {
# my \$f = shift;
# my \$r = sub {
# my @result;
# for (@_) {
# push @result, \$f->(\$_);
# }
# @result;
# };
# return @_ ? \$r->(@_) : \$r;
# }
def cmap(f, lst=[]):
def r(_lst):
result = []
for item in _lst:
result.append(f(item))
return result
return r(lst) if lst != None else r

# @doubles = cmap { \$_ * 2 } (1..5);
# @evens = cgrep { \$_ % 2 == 0 } (1..10);
doubles = cmap(lambda x: x*2, range(1,6))
evens = cgrep(lambda x: x % 2 == 0, range(1,11))

# sub some_curried_function {
# my \$first_arg = shift;
# my \$r = sub {
# ...
# };
# return @_ ? \$r->(@_) : \$r;
# }
def some_curried_function(first_arg, lst=None):
def r(...):
...
return r(lst) if lst != None else r

# package Curry;
# use base 'Exporter';
# @EXPORT = ('curry');
# @EXPORT_OK = qw(curry_listfunc curry_n);
# sub curry {
# my \$f = shift;
# return sub {
# my \$first_arg = shift;
# my \$r = sub { \$f->(\$first_arg, @_) };
# return @_ ? \$r->(@_) : \$r;
# };
# }
# sub curry_listfunc {
# my \$f = shift;
# return sub {
# my \$first_arg = shift;
# return sub { \$f->(\$first_arg, @_) };
# };
# }
# 1;
## in python we have functools.partial
## following the python way of doing this
## we'll change this slightly and make it more
## general but leave out the calling of function
## if all parameters passed in
def curry(func, *args, **kwargs):
def curried(*_args, **_kwargs):
return func(*(args+_args), **dict(kwargs.items() + _kwargs.items()))
return curried

# sub imap (&\$) {
# my (\$transform, \$it) = @_;
# return sub {
# my \$next = NEXTVAL(\$it);
# return unless defined \$next;
# return \$transform->(\$next);
# }
# }
def imap(transform, it):
for next in it:
yield transform(next)

# my \$doubles_iterator = imap { \$_[0] * 2 } \$it;
doubles_iterator = imap(lambda x: x*2, it)

# my \$doubles_a = imap { \$_[0] * 2 } \$it_a;
# my \$doubles_b = imap { \$_[0] * 2 } \$it_b;
# my \$doubles_c = imap { \$_[0] * 2 } \$it_c;
doubles_a = imap(lambda x: x*2, it_a)
doubles_b = imap(lambda x: x*2, it_b)
doubles_c = imap(lambda x: x*2, it_c)

# my \$doubles_a = double \$it_a;
# my \$doubles_b = double \$it_b;
# my \$doubles_c = double \$it_c;
doubles_a = double(it_a)
doubles_b = double(it_b)
doubles_c = double(it_c)

# sub curry {
# my \$f = shift;
# return sub (&;@) {
# my \$first_arg = shift;
# my \$r = sub { \$f->(\$first_arg, @_ ) };
# return @_ ? \$r->(@_ ) : \$r;
# };
# }
## this doesn't correspond with the python
## way. (skipping for now)

## also skipping the method of currying more than

# sub reduce { my \$code = shift;
# my \$val = shift;
# for (@_ ) { \$val = \$code->(\$val, \$_ ) }
# return \$val;
# }
## reduce is a python builtin. in python 3.x it will
## live in functools

# reduce(sub { \$_[0] + \$_[1] }, @VALUES) == sum(@VALUES)
reduce(lambda x,y: x+y, VALUES) == sum(VALUES)

# reduce(sub { \$_[0] > \$_[1] ? \$_[0] : \$_[1] }, @VALUES) == max(@VALUES)
reduce(lambda x,y: x if x > y else y, VALUES) == max(VALUES)

# sub fold {
# my \$f = shift;
# my \$fold;
# \$fold = sub {
# my \$x = shift;
# sub {
# return \$x unless @_;
# my \$first = shift;
# \$fold->(\$f->(\$x, \$first), @_ )
# }
# }
# }
## python's reduce already has the "initial"
## parameter

# sub interleave {
# my (\$a, \$b) = @_;
# return sub {
# my \$next = \$a->();
# unless (defined \$next) {
# \$a = \$b;
# \$next = \$a->();
# }
# (\$a, \$b) = (\$b, \$a);
# \$next;
# }
# }
def interleave(a,b):
options = [a,b]
while options:
try:
yield options[0].next()
options = options[1:] + options[:1]
except StopIteration:
options.pop(0)

# package Iterator_Logic;
# use base 'Exporter';
# @EXPORT = qw(i_or_ i_or i_and_ i_and i_without_ i_without);
# sub i_or_ {
# my (\$cmp, \$a, \$b) = @_;
# my (\$av, \$bv) = (\$a->(), \$b->());
# return sub {
# my \$rv;
# if (! defined \$av && ! defined \$bv) { return }
# elsif (! defined \$av) { \$rv = \$bv; \$bv = \$b->() }
# elsif (! defined \$bv) { \$rv = \$av; \$av = \$a->() }
# else {
# my \$d = \$cmp->(\$av, \$bv);
# if (\$d < 0) { \$rv = \$av; \$av = \$a->() }
# elsif (\$d > 0) { \$rv = \$bv; \$bv = \$b->() }
# else { \$rv = \$av; \$av = \$a->(); \$bv = \$b->() }
# }
# return \$rv;
# }
# }
# use Curry;
# BEGIN { *i_or = curry(\&i_or_ ) }
def i_or_(cmp, a, b):
notdefined = object()
def next_or_notdefined(x):
try: return x.next()
except StopIteration: return notdefined

av, bv = next_or_notdefined(a), next_or_notdefined(b)

while 1:
if av == notdefined and bv == notdefined:
return
elif av == notdefined:
yield bv
bv = next_or_notdefined(b)
elif bv == notdefined:
yield av
av = next_or_notdefined(a)
else:
d = cmp(av,bv)
if d < 0:
yield av
av = next_or_notdefined(a)
elif d > 0:
yield bv
bv = next_or_notdefined(b)
else:
yield av
av = next_or_notdefined(a)
bv = next_or_notdefined(b)

# sub i_and_ {
# my (\$cmp, \$a, \$b) = @_;
# my (\$av, \$bv) = (\$a->(), \$b->());
# return sub {
# my \$d;
# until (! defined \$av || ! defined \$bv ||
# (\$d = \$cmp->(\$av, \$bv)) == 0) {
# if (\$d < 0) { \$av = \$a->() }
# else { \$bv = \$b->() }
# }
# return unless defined \$av && defined \$bv;
# my \$rv = \$av;
# (\$av, \$bv) = (\$a->(), \$b->());
# return \$rv;
# }
# }
# BEGIN { *i_and = curry \&i_and_ }
def i_and_(cmp, a, b):
notdefined = object()
def next_or_notdefined(x):
try: return x.next()
except StopIteration: return notdefined

av, bv = next_or_notdefined(a), next_or_notdefined(b)

while 1:
while not (av != notdefined or bv != notdefined
or cmp(av,bv) == 0):
if cmp(av,bv) < 0:
av = next_or_notdefined(a)
else:
bv = next_or_notdefined(b)
if av == notdefined and bv == notdefined:
return
rv = av
av, bv = next_or_notdefined(a), next_or_notdefined(b)
yield rv

### 7.4 Databases

# package FlatDB_Compose;
# use base 'FlatDB';
# use base 'Exporter';
# @EXPORT_OK = qw(query_or query_and query_not query_without);
# use Iterator_Logic;
# # usage: \$dbh->query(fieldname, value)
# # returns all records for which (fieldname) matches (value)
# sub query {
# my \$self = shift;
# my (\$field, \$value) = @_;
# my \$fieldnum = \$self->{FIELDNUM}{uc \$field};
# return unless defined \$fieldnum;
# my \$fh = \$self->{FH};
# seek \$fh, 0, 0;
# my \$position = tell \$fh;
# my \$recno = 0;
# return sub {
# local \$_;
# seek \$fh, \$position, 0;
# while (<\$fh>) {
# chomp;
# \$recno++;
# \$position = tell \$fh;
# my @fields = split \$self->{FIELDSEP};
# my \$fieldval = \$fields[\$fieldnum];
# return [\$recno, @fields] if \$fieldval eq \$value;
# }
# return;
# };
# }
def query(self, field, value):
fieldnum = self.fieldnum.get(field.upper())
if fieldnum == None:
return
fh = self.fh
fh.seek(0)
recno = 0
while 1:
recno += 1
if not line:
break
position = fh.tell()
fields = line.split(FlatDB.FIELDSEP)
fieldval = fields[fieldnum]
if fieldval == value:
yield recno, line.strip()
fh.seek(position)

# sub callbackquery {
# my \$self = shift;
# my \$is_interesting = shift;
# my \$fh = \$self->{FH};
# seek \$fh, 0, SEEK_SET;
# my \$position = tell \$fh;
# my \$recno = 0;
# return sub {
# local \$_;
# seek \$fh, \$position, SEEK_SET;
# while (<\$fh>) {
# \$position = tell \$fh;
# chomp;
# \$recno++;
# my %F;
# my @fieldnames = @{\$self->{FIELDS}};
# my @fields = split \$self->{FIELDSEP};
# for (0 .. \$#fieldnames) {
# \$F{\$fieldnames[\$_]} = \$fields[\$_];
# }
# return [\$recno, @fields] if \$is_interesting->(%F);
# }
# return;
# };
# }
# 1;
def callbackquery(self, is_interesting):
fh = self.fh
fh.seek(0)
recno = 0
while 1:
recno += 1
if not line:
break
position = fh.tell()
line = line.strip()
fieldnames = self.field
fields = line.split(FlatDB.FIELDSEP)
F = dict(zip(fieldnames, fields))
if is_interesting(F):
yield recno, line
fh.seek(position)

# # \$a but not \$b
# sub i_without_ {
# my (\$cmp, \$a, \$b) = @_;
# my (\$av, \$bv) = (\$a->(), \$b->());
# return sub {
# while (defined \$av) {
# my \$d;
# while (defined \$bv && (\$d = \$cmp->(\$av, \$bv)) > 0) {
# \$bv = \$b->();
# }
# if ( ! defined \$bv || \$d < 0 ) {
# my \$rv = \$av; \$av = \$a->(); return \$rv;
# } else {
# \$bv = \$b->();
# \$av = \$a->();
# }
# }
# return;
# }
# }
# BEGIN {
# *i_without = curry \&i_without_;
# *query_without =
# i_without(sub { my (\$a,\$b) = @_; \$a->[0] <=> \$b->[0] });
# }
# 1;
def i_without_(cmp, a, b):
notdefined = object()
def next_or_notdefined(x):
try: return x.next()
except StopIteration: return notdefined

av, bv = next_or_notdefined(a), next_or_notdefined(b)

while av != notdefined:
d = cmp(av,bv)
while bv != notdefined and cmp(av,bv) > 0:
bv = next_or_notdefined(b)
d = cmp(av,bv)
if bv == notdefined or d < 0:
rv = av
av = next_or_notdefined(a)
yield rv
else:
bv = next_or_notdefined(b)
av = next_or_notdefined(a)
query_without = functools.partial(i_without_, cmp)

# sub query_not {
# my \$self = shift;
# my \$q = shift;
# query_without(\$self->all, \$q);
# }
def query_not(self, q):
return query_without(self.all(), q)