Looking at haskell I see some of my friends from python. Significant whitespace, list comprehensions, interators (sort of like laziness), tuples. And then it struck me that all of these features in python are derivative. Not that that is a bad thing. But I was surprised that I couldn't think of anything definitively new/unique to python. (Obviously the way these things are combined/balanced is unique)
Hey, internets, did python invent any language features/syntax?
The only thing that I can come up with is maybe the __blah__ (unders before and after) style of exposing syntax overriding.
Showing posts with label python. Show all posts
Showing posts with label python. Show all posts
Sunday, January 17, 2010
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 @_;
# }
# }
# sub extract_headers {
# 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;
# return $header_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
def extract_headers(tree):
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]
header_text = "".join(keeper_text)
return header_text
# 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)
# sub add2 {
# my ($s, $t) = @_;
# return unless $s && $t;
# node(head($s) + head($t),
# promise { add2(tail($s), tail($t)) });
# }
# sub mul2 {
# my ($s, $t) = @_;
# return unless $s && $t;
# node(head($s) * head($t),
# promise { mul2(tail($s), tail($t)) });
# }
def add2(s,t):
if not (t and s):
return None
return node(head(s) + head(t),
promise(lambda: add2(tail(s),tail(t))))
def mul2(s,t):
if not (s and t):
return None
return node(head(s)*head(t),
promise(lambda: mul2(tail(s),tail(t))))
# sub combine2 {
# my ($s, $t, $op) = @_;
# return unless $s && $t;
# node($op->(head($s), head($t)),
# promise { combine2(tail($s), tail($t), $op) });
# }
def combine2(s,t,op):
if not (s and t):
return None
return node(op(head(s),head(t)),
promise(lambda: combine2(tail(s),tail(t), op)))
# sub add2 { combine2(@_, sub { $_[0] + $_[1] }) }
# sub mul2 { combine2(@_, sub { $_[0] * $_[1] }) }
def add2(s,t):
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;
# node($op->(head($s), head($t)),
# promise { combine2($op)->(tail($s), tail($t))});
# };
# }
def combine2(op):
def _foo(s, t):
if not (s and t):
return None
return node(op(head(s),head(t)),
promise(lambda: combine2(op(tail(s), tail(t)))))
return _foo
# $add2 = combine2(sub { $_[0] + $_[1] });
# $mul2 = combine2(sub { $_[0] * $_[1] });
add2 = combine2(lambda x,y: x+y)
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;
# node($op->(head($s), head($t)),
# promise { combine2($op)->(tail($s), tail($t)) });
# };
# }
def combine2(op):
def _foo(s, t):
if not (s and t):
return None
return node(op(head(s),head(t)),
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;
# node($op->(head($s), head($t)),
# promise { $r->(tail($s), tail($t)) });
# };
# }
def combine2(op):
def r(s,t):
if not (s and t):
return None
return node(op(head(s),head(t)),
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
## one arg since we get that for free
# 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;
# <$fh>; # discard header line
# 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)
fh.readline() # discard schema line
recno = 0
while 1:
line = fh.readline()
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;
# <$fh>; # discard header line
# 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)
fh.readline() # discard schema line
recno = 0
while 1:
line = fh.readline()
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)
### left off the last bit about operator overloading since it seems
### orthogonal to how you'd do it in python
Wednesday, March 25, 2009
Higher Order Perl (Python Style) : Chapter 6 - Infinite Streams
TOC
### Chapter 6 - Infinite Streams
### 6.1 Linked Lists
# sub node {
# my ($h, $t) = @_;
# [$h, $t];
# }
# sub head {
# my ($ls) = @_;
# $ls->[0];
# }
# sub tail {
# my ($ls) = @_;
# $ls->[1];
# }
# sub set_head {
# my ($ls, $new_head) = @_;
# $ls->[0] = $new_head;
# }
# sub set_tail {
# my ($ls, $new_tail) = @_;
# $ls->[1] = $new_tail;
# }
def node(h,t):
return [h,t]
def head(ls):
return ls[0]
def tail(ls):
return ls[1]
def set_head(ls, new_head):
ls[0] = new_head
def set_tail(ls, new_tail):
ls[1] = new_tail
# $my_list = node($new_data, $my_list);
my_list = node(new_data, my_list)
# sub insert_after {
# my ($node, $new_data) = @_;
# my $new_node = node($new_data, tail($node));
# set_tail($node, $new_node);
# }
def insert_after(node, new_data):
new_node = node(new_data, tail(node))
set_tail(node, new_node)
### 6.2 Lazy Linked Lists
# package Stream;
# use base Exporter;
# @EXPORT_OK = qw(node head tail drop upto upfrom show promise
# filter transform merge list_to_stream cutsort
# iterate_function cut_loops);
# %EXPORT_TAGS = ('all' => \@EXPORT_OK);
# sub node {
# my ($h, $t) = @_;
# [$h, $t];
# }
# sub head {
# my ($s) = @_;
# $s->[0];
# }
# sub tail {
# my ($s) = @_;
# if (is_promise($s->[1])) {
# return $s->[1]->();
# }
# $s->[1];
# }
# sub is_promise {
# UNIVERSAL::isa($_[0], 'CODE');
# }
def node(h,t):
return [h,t]
def head(s):
return s[0]
def tail(s):
if is_promise(s[1]):
return s[1]()
return s[1]
def is_promise(s):
return callable(s)
# sub promise (&) { $_[0] }
# this is the silliest kind of syntactic sugar
# but this will avoid some scoping confusion and
# premature execution i was experiencing
# in later examples and makes it look more like the perl example
def promise(func):
return func
# sub upto_list {
# my ($m, $n) = @_;
# return if $m > $n;
# node($m, upto_list($m+1, $n));
# }
def upto_list(m, n):
if m > n:
return None
return node(m, upto_list(m+1, n))
# sub upto {
# my ($m, $n) = @_;
# return if $m > $n;
# node($m, promise { upto($m+1, $n) } );
# }
def upto(m, n):
if m > n:
return None
return node(m, promise(lambda: upto(m+1, n)))
# sub upfrom {
# my ($m) = @_;
# node($m, promise { upfrom($m+1) } );
# }
def upfrom(m):
return node(m, promise(lambda: upfrom(m+1)))
# sub upfrom_list {
# my ($m) = @_;
# node($m, upfrom_list($m+1) );
# }
def upfrom_list(m):
return node(m, upfrom_list(m+1))
# sub show {
# my $s = shift;
# while ($s) {
# print head($s), $";
# $s = tail($s);
# }
# print $/;
# }
def show(s):
while(s):
print head(s),
s = tail(s)
# sub show {
# my ($s, $n) = @_;
# while ($s && (! defined $n || $n-- > 0)) {
# print head($s), $";
# $s = tail($s);
# }
# print $/;
# }
# NOTE: i'm following the perlish code here
# but in real life i would use itertools
def show(s, n=None):
while s and (n == None or n > 0):
print head(s),
s = tail(s)
if n != None:
n -= 1
# sub drop {
# my $h = head($_[0]);
# $_[0] = tail($_[0]);
# return $h;
# }
# to do this in python we'd either
# need to make a stream class or
# return a pair (h,s)
# where s is the stream in it's new state
def drop(s):
h, tail = s
return h, tail # which really was a noop
# OR something like:
class Stream(object):
def __init__(self, contents):
self.contents = contents
def drop(self):
h = head(self.contents)
self.contents = tail(contents)
return h
# sub show {
# my ($s, $n) = @_;
# while ($s && (! defined $n || $n-- > 0)) {
# print drop($s), $";
# }
# print $/;
# }
### we don't really get any savings here so i'll skip this
# sub transform (&$) {
# my $f = shift;
# my $s = shift;
# return unless $s;
# node($f->(head($s)),
# promise { transform($f, tail($s)) });
# }
def transform(f, s):
if not s:
return None
return node(f(head(s)),
promise(lambda: transform(f, tail(s))))
# my $evens = transform { $_[0] * 2 } upfrom(1);
evens = transform(lambda x: x * 2, upfrom(1))
# sub filter (&$) {
# my $f = shift;
# my $s = shift;
# until (! $s || $f->(head($s))) {
# drop($s);
# }
# return if ! $s;
# node(head($s),
# promise { filter($f, tail($s)) });
# }
def filter(f, s):
while not (not s or f(head(s))):
s = tail(s)
if not s:
return None
return node(head(s),
promise(lambda: filter(f, tail(s))))
# sub iterate_function {
# my ($f, $x) = @_;
# node($x, promise { iterate_function($f, $f->($x)) });
# }
def iterate_function(f, x):
return node(x, promise(lambda: iterate_function(f, f(x))))
### 6.3 Recursive Streams
# sub carrots {
# node('carrot', promise { carrots() });
# }
# my $carrots = carrots();
def carrots():
return node("carrot", promise(carrots))
# my $carrots = node('carrot', promise { carrots() });
carrots = node("carrot", promise(carrots()))
# my $carrots = node('carrot', promise { $carrots });
carrots = node("carrot", promise(lambda: carrots))
# sub pow2_from {
# my $n = shift;
# node($n, promise {pow2_from($n*2)})
# }
# my $powers_of_2 = pow2_from(1);
def pow2_from(n):
return node(n, promise(lambda: pow2_from(n*2)))
# my $powers_of_2;
# $powers_of_2 =
# node(1, promise { transform {$_[0]*2} $powers_of_2 });
# def powers_of_2():
# return node(1, powers_of_2)
powers_of_2 = node(1, promise(lambda: transform(lambda x: x*2, powers_of_2)))
# sub tail {
# my ($s) = @_;
# if (is_promise($s->[1])) {
# $s->[1] = $s->[1]->();
# }
# $s->[1];
# }
def tail(s):
if is_promise(s[1]):
s[1] = s[1]()
return s[1]
### 6.4 The Hamming Problem
# sub is_hamming {
# my $n = shift;
# $n/=2 while $n%2 == 0;
# $n/=3 while $n%3 == 0;
# $n/=5 while $n%5 == 0;
# return $n == 1;
# }
# # Return the first $N hamming numbers
# sub hamming {
# my $N = shift;
# my @hamming;
# my $t = 1;
# until (@hamming == $N) {
# push @hamming, $t if is_hamming($t);
# $t++;
# }
# @hamming;
# }
def is_hamming(n):
while n % 2 == 0:
n /= 2
while n % 3 == 0:
n /= 3
while n % 5 == 0:
n /= 5
return n == 1
def hamming(N):
result = []
t = 1
while len(result) < N:
if is_hamming(t):
result.append(t)
t += 1
return result
# sub merge {
# my ($S, $T) = @_;
# return $T unless $S;
# return $S unless $T;
# my ($s, $t) = (head($S), head($T));
# if ($s > $t) {
# node($t, promise {merge( $S, tail($T))});
# } elsif ($s < $t) {
# node($s, promise {merge(tail($S), $T)});
# } else {
# node($s, promise {merge(tail($S), tail($T))});
# }
# }
def merge(S,T):
if not S:
return T
if not T:
return S
s, t = head(S), head(T)
if s > t:
return node(t, promise(lambda: merge(S, tail(T))))
elif s < t:
return node(s, promise(lambda: merge(tail(S), T)))
else:
return node(s, promise(lambda: merge(tail(S), tail(T))))
# sub scale {
# my ($s, $c) = @_;
# transform { $_[0]*$c } $s;
# }
def scale(s, c):
return transform(lambda x: x * c, s)
# my $hamming;
# $hamming = node(1,
# promise {
# merge(scale($hamming, 2),
# merge(scale($hamming, 3),
# scale($hamming, 5),
# ))
# }
# );
# show($hamming, 3000);
hamming = node(1,
promise(lambda: merge(scale(hamming, 2),
merge(scale(hamming, 3),
scale(hamming, 5),
))
))
### just for kicks here are two solutions from the tubes:
### - OO version : http://aspn.activestate.com/ASPN/Mail/Message/python-list/905315
### - iterator verion (my preference) : http://mail.python.org/pipermail/python-list/2005-January/303480.html
### There is also a couple variations of this in python's test suite: test_generators.py
### but i'd wager that the haskell solution of this is still the king
### 6.5 Regex String Generation
# package Regex;
# use Stream ':all';
# use base 'Exporter';
# @EXPORT_OK = qw(literal union concat star plus charclass show
# matches);
# sub literal {
# my $string = shift;
# node($string, undef);
# }
# show(literal("foo"));
# foo
def literal(s):
return node(s, None)
# sub mingle2 {
# my ($s, $t) = @_;
# return $t unless $s;
# return $s unless $t;
# node(head($s),
# node(head($t),
# promise { mingle2(tail($s),
# tail($t))
# }
# ));
# }
def mingle2(s, t):
if not s:
return t
if not t:
return s
return node(head(s),
node(head(t),
promise(lambda: mingle2(tail(s), tail(t)))))
# sub union {
# my ($h, @s) = grep $_, @_;
# return unless $h;
# return $h unless @s;
# node(head($h),
# promise {
# union(@s, tail($h));
# });
# }
def union(*streams):
streams = [_s for _s in streams if _s != None]
if len(streams) == 0:
return None
if len(streams) == 1:
return streams[0]
return node(head(streams[0]),
promise(lambda: union(*(streams[1:]+[tail(streams[0])]))))
# # generate infinite stream ($k:1, $k:2, $k:3, ...)
# sub constant {
# my $k = shift;
# my $i = shift || 1;
# my $s = node("$k:$i", promise { constant($k, $i+1) });
# }
# my $fish = constant('fish');
# show($fish, 3);
# fish:1 fish:2 fish:3
# my $soup = union($fish, constant('dog'), constant('carrot'));
# show($soup, 10);
# fish:1 dog:1 carrot:1 fish:2 dog:2 carrot:2 fish:3 dog:3 carrot:3 fish:4
def constant(k, i=1):
return node("%s:%s" % (k,i),
promise(lambda: constant(k, i+1)))
fish = constant("fish")
soup = union(fish, constant("dog"), constant("carrot"))
show(soup, 10)
# sub concat {
# my ($S, $T) = @_;
# return unless $S && $T;
# my ($s, $t) = (head($S), head($T));
# node("$s$t", promise {
# union(postcat(tail($S), $t),
# precat(tail($T), $s),
# concat(tail($S), tail($T)),
# )
# });
# }
# sub precat {
# my ($s, $c) = @_;
# transform {"$c$_[0]"} $s;
# }
# sub postcat {
# my ($s, $c) = @_;
# transform {"$_[0]$c"} $s;
# }
def concat(S,T):
if None in (S, T):
return None
s, t = head(S), head(T)
return node("%s%s" % (s,t),
promise(lambda: (union(postcat(tail(S), t),
precat(tail(T),s),
concat(tail(S),tail(T))))))
def precat(s,c):
return transform(lambda x: "%s%s" % (c,x), s)
def postcat(s,c):
return transform(lambda x: "%s%s" % (x,c), s)
# # Im /(a|b)(c|d)$/
# my $z = concat(union(literal("a"), literal("b")),
# union(literal("c"), literal("d")),
# );
# show($z);
z = (concat(union(literal("a"), literal("b")),
union(literal("c"), literal("d")),
))
show(z)
# sub star {
# my $s = shift;
# my $r;
# $r = node("", promise { concat($s, $r) });
# }
# def star(s):
# _s = s[0]
# return iterate_function(lambda x: x + _s, "")
def star(s):
r = node("", promise(lambda: concat(s, r)))
return r
# sub show {
# my ($s, $n) = @_;
# while ($s && (! defined $n || $n-- > 0)) {
# print qq{"}, drop($s), qq{"\n};
# }
# print "\n";
# }
def show(s, n=None):
while s and (n == None or n > 0):
print repr(head(s))
s = tail(s)
if n != None:
n -= 1
# # charclass('abc') = /[abc]$/
# sub charclass {
# my $class = shift;
# union(map literal($_), split(//, $class));
# }
def charclass(_class):
return union(*[literal(c) for c in _class])
# # plus($s) = /s+$/
# sub plus {
# my $s = shift;
# concat($s, star($s));
# }
def plus(s):
return concat(s, star(s))
# use Regex qw(concat star literal show);
# # I represent /ab*$/
# my $regex1 = concat( literal("a"),
# star(literal("b"))
# );
# show($regex1, 10);
regex1 = concat( literal("a"),
star(literal("b"))
)
show(regex1, 10)
# # I represent /(aa|b)*$/
# my $regex2 = star(union(literal("aa"),
# literal("b"),
# ));
# show($regex2, 16);
regex2 = star(union(literal("aa"),
literal("b"),
))
show(regex2, 16)
# # I represent /(ab+|c)*$/
# my $regex3 = star(union(concat( literal("a"),
# plus(literal("b"))),
# literal("c")
# ));
# show($regex3, 20);
regex3 = star(union(concat( literal("a"),
plus(literal("b"))),
literal("c")
))
show(regex3, 20)
# sub union {
# my (@s) = grep $_, @_;
# return unless @s;
# return $s[0] if @s == 1;
# my $si = index_of_shortest(@s);
# node(head($s[$si]),
# promise {
# union(map $_ == $si ? tail($s[$_]) : $s[$_],
# 0 .. $#s);
# });
# }
# curse python's lame lambdas!
def union(*streams):
streams = [_s for _s in streams if _s != None]
if len(streams) == 0:
return None
if len(streams) == 1:
return streams[0]
si = index_of_shortest(streams)
return node(head(streams[si]),
promise(lambda: union(*[_s if _i != si else tail(_s) for (_i, _s) in enumerate(streams)])))
# sub index_of_shortest {
# my @s = @_;
# my $minlen = length(head($s[0]));
# my $si = 0;
# for (1 .. $#s) {
# my $h = head($s[$_]);
# if (length($h) < $minlen) {
# $minlen = length($h);
# $si = $_;
# }
# }
# $si;
# }
def index_of_shortest(*streams):
minlin = len(head(streams[0]))
si = 0
for i in range(1,len(streams)):
h = head(streams[i])
if len(h) < minlin:
minlen = len(h)
si = i
return si
### ugg. i can't seem to get correct ordering to work. :(
# sub matches {
# my ($string, $regex) = @_;
# while ($regex) {
# my $s = drop($regex);
# return 1 if $s eq $string;
# return 0 if length($s) > length($string);
# }
# return 0;
# }
def matches(string, regex):
while regex:
s = head(regex)
regex = tail(regex)
if s == string:
return True
if len(s) > len(string):
return False
return False
# ugg. this fails when star is involved
# sub bal {
# my $contents = shift;
# my $bal;
# $bal = node("", promise {
# concat($bal,
# union($contents,
# transform {"($_[0])"} $bal,
# )
# )
# });
# }
def bal(contents):
_bal = node("",
promise(lambda: union(contents,
transform(lambda x: "(%s)" % x, _bal))))
return _bal
# sub cut_bylen {
# my ($a, $b) = @_;
# # Its OK to emit item $a if the next item in the stream is $b
# length($a) < length($b);
# }
def cut_bylen(a,b):
return len(a) < len(b)
# sub list_to_stream {
# my $node = pop;
# while (@_) {
# $node = node(pop, $node);
# }
# $node;
# }
def list_to_stream(nodes):
_nodes = nodes[:]
_node = _nodes.pop()
while _nodes:
_node = node(_nodes.pop(), _node)
return _node
# sub insert (\@$$);
# sub cutsort {
# my ($s, $cmp, $cut, @pending) = @_;
# my @emit;
# while ($s) {
# while (@pending && $cut->($pending[0], head($s))) {
# push @emit, shift @pending;
# }
# if (@emit) {
# return list_to_stream(@emit,
# promise { cutsort($s, $cmp, $cut, @pending) });
# } else {
# insert(@pending, head($s), $cmp);
# $s = tail($s);
# }
# }
# return list_to_stream(@pending, undef);
# }
def cutsort(s, _cmp, cut, _pending=[]):
pending = _pending[:]
emit = []
while s:
while pending and cut(pending[0],head(s)):
emit.append(pending.pop(0))
if emit:
return list_to_stream(emit,
promise(lambda: cutsort(s, _cmp, cut, pending)))
else:
insert(pending, head(s), _cmp)
s = tail(s)
return list_to_stream(pending+[None])
# my $sorted =
# cutsort($regex3,
# sub { $_[0] cmp $_[1] }, # comparator
# \&cut_bylen # cutting function
# );
sorted = cutsort(regex3,
lambda x,y: cmp(x,y),
cut_bylen,
)
# sub insert (\@$$) {
# my ($a, $e, $cmp) = @_;
# my ($lo, $hi) = (0, scalar(@$a));
# while ($lo < $hi) {
# my $med = int(($lo + $hi) / 2);
# my $d = $cmp->($a->[$med], $e);
# if ($d <= 0) {
# $lo = $med+1;
# } else {
# $hi = $med;
# }
# }
# splice(@$a, $lo, 0, $e);
# }
def insert(a, e, _cmp):
lo, hi = 0, len(a)
while lo < hi:
med = int((lo+hi)/2)
d = _cmp(a[med],e)
if d <= 0:
lo = med+1
else:
hi = med
splice(a, lo, 0, e)
##
## above not tested
##
# sub _devino {
# my $f = shift;
# my ($dev, $ino) = stat($f);
# return unless defined $dev;
# "$dev;$ino";
# }
def _devino(f):
stat_tuple = os.state(f)
dev, ino = stat_tuple.st_dev, stat_tuple.st_ino
if not dev:
return None
return "%s;%s" % (dev, ino)
##
## ugg... sorry got lazy again and skipped the rest of this section
##
### 6.6 The Newton-Raphson Method
# sub sqrt2 {
# my $g = 2; # Initial guess
# until (close_enough($g*$g, 2)) {
# $g = ($g*$g + 2) / (2*$g);
# }
# $g;
# }
def sqrt2():
g = 2
while not close_enough(g*g, 2):
g = float(g*g + 2) / (2*g)
return g
# sub close_enough {
# my ($a, $b) = @_;
# return abs($a - $b) < 1e-12;
# }
def close_enough(a,b):
return abs(a-b) < 1e-12
# sub sqrtn {
# my $n = shift;
# my $g = $n; # Initial guess
# until (close_enough($g*$g, $n)) {
# $g = ($g*$g + $n) / (2*$g);
# }
# $g;
# }
def sqrtn(n):
g = n
while not close_enough(g*g, n):
g = float(g*g + n) / (2*g)
return g
# use Stream 'iterate_function';
# sub sqrt_stream {
# my $n = shift;
# iterate_function (sub { my $g = shift;
# ($g*$g + $n) / (2*$g);
# },
# $n);
# }
# 1;
def sqrt_stream(n):
return iterate_function(lambda g: float(g*g + n)/(2*g),
n)
# 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 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)
# # Return a stream of numbers $x that make $f->($x) close to 0
# sub solve {
# my $f = shift;
# my $guess = shift || 1;
# iterate_function(sub { my $g = shift;
# $g - $f->($g)/slope($f, $g);
# },
# $guess);
# }
def solve(f, guess=1):
return iterate_function(lambda g: g - f(g)/slope(f,g),
guess)
# use Math::BigFloat;
# my $sqrt2 = solve(sub { $_[0] * $_[0] - 2 },
# Math::BigFloat->new(2));
# if want to use Decimal then need to retrofit a few functions:
import decimal
decimal.getcontext().prec = 64
def slope(f, x):
x = decimal.Decimal(x)
e = decimal.Decimal("0.00000095367431640625")
return (f(x+e) - f(x-e)) / (2*e)
def solve(f, guess=1):
return iterate_function(lambda g: g - f(g)/slope(f,g),
decimal.Decimal(guess))
sqrt2 = solve(lambda x: x*x - decimal.Decimal(2),
decimal.Decimal(2))
# sub cut_loops {
# my $s = shift;
# return unless $s;
# my @previous_values = @_;
# for (@previous_values) {
# if (head($s) == $_ ) {
# return;
# }
# }
# node(head($s),
# promise { cut_loops(tail($s), head($s), @previous_values) });
# }
def cut_loops(s, *args):
if s == None:
return None
previous_values = list(args)
for v in previous_values:
if head(s) == v:
return None
return node(head(s),
promise(lambda: cut_loops(tail(s), *([head(s)] + previous_values))))
# sub cut_loops {
# my ($tortoise, $hare) = @_;
# return unless $tortoise;
# # The hare and tortoise start at the same place
# $hare = $tortoise unless defined $hare;
# # The hare moves two steps every time the tortoise moves one
# $hare = tail(tail($hare));
# # If the hare and the tortoise are in the same place, cut the loop
# return if head($tortoise) == head($hare);
# return node(head($tortoise),
# promise { cut_loops(tail($tortoise), $hare) });
# }
def cut_loops(tortoise, hare=None):
if tortoise == None:
return None
# The hare and tortoise start at the same place
if hare == None:
hare = tortoise
# The hare moves two steps every time the tortoise moves one
hare = tail(tail(hare))
# If the hare and the tortoise are in the same place, cut the loop
if head(tortoise) == head(hare):
return None
return node(head(tortoise),
promise(lambda: cut_loops(tail(tortoise), hare)))
# sub cut_loops2 {
# my ($tortoise, $hare, $n) = @_;
# return unless $tortoise;
# $hare = $tortoise unless defined $hare;
# $hare = tail(tail($hare));
# return if head($tortoise) == head($hare)
# && $n++;
# return node(head($tortoise),
# promise { cut_loops(tail($tortoise), $hare, $n) });
# }
def cut_loops2(tortoise, hare=None, n=0):
if tortoise == None:
return None
if hare == None:
hare = tortoise
hare = tail(tail(hare))
if head(tortoise) == head(hare):
if n > 0:
return None
else:
n += 1
return node(head(tortoise),
promise(lambda: cut_loops2(tail(tortoise), hare, n)))
# sub owed {
# my ($P, $N, $pmt, $i) = @_;
# my $payment_factor = 0;
# for (0 .. $N-1) {
# $payment_factor += (1+$i) ** $_;
# }
# return $P * (1+$i)**$N - $pmt * $payment_factor;
# }
def owed(P,N,pmt,i):
payment_factor = 0
for x in range(0,N):
payment_factor += (1+i) ** x
return P * (1+i)**N - pmt * payment_factor
# sub owed {
# my ($P, $N, $pmt, $i) = @_;
# return $P * (1+$i)**$N - $pmt * ((1+$i)**$N - 1) / $i;
# }
def owed(P,N,pmt,i):
return P * (1+i)**N - pmt * ((1+i)**N - 1) / i
# sub owed_after_n_months {
# my $N = shift;
# owed(100_000, $N, 1_000, 0.005);
# }
# my $stream = cut_loops(solve(\&owed_after_n_months));
# my $n;
# $n = drop($stream) while $stream;
# print "You will be paid off in only $n months!\n";
def owed_after_n_months(N):
return owed(100000, N, 1000, 0.005)
stream = cut_loops(solve(owed_after_n_months))
n = head(stream)
while stream:
n = head(stream)
stream = tail(stream)
print "You will be paid off in only %s months!" % n
# sub affordable_mortgage {
# my $mortgage = shift;
# owed($mortgage, 30, 15_600, 0.0675);
# }
# my $stream = cut_loops(solve(\&affordable_mortgage));
# my $n;
# $n = drop($stream) while $stream;
# print "You can afford a \$$n mortgage.\n";
def affordable_mortgage(mortgage):
return owed(mortgage, 30, 15600, 0.0675)
stream = cut_loops(solve(affordable_mortgage))
n = head(stream)
while stream:
n = head(stream)
stream = tail(stream)
print "You can afford a $%s mortgage." % n
### 6.7 Power Series
# # Approximate sin(x) using the first n terms of the power series
# sub approx_sin {
# my $n = shift;
# my $x = shift;
# my ($denom, $c, $num, $total) = (1, 1, $x, 0);
# while ($n--) {
# $total += $num / $denom;
# $num *= $x*$x * -1;
# $denom *= ($c+1) * ($c+2);
# $c += 2;
# }
# $total;
# }
# 1;
def approx_sin(n, x):
denom, c, num, total = 1,1,x,0
while n:
n -= 1
total += num / float(denom)
num *= x*x * - 1
denom *= (c+1) * (c+2)
c += 2
return total
# package PowSeries;
# use base 'Exporter';
# @EXPORT_OK = qw(add2 mul2 partial_sums powers_of term_values
# evaluate derivative multiply recip divide
# $sin $cos $exp $log_ $tan);
# use Stream ':all';
# sub tabulate {
# my $f = shift;
# &transform($f, upfrom(0));
# }
def tabulate(f):
return transform(f, upfrom(0))
# my @fact = (1);
# sub factorial {
# my $n = shift;
# return $fact[$n] if defined $fact[$n];
# $fact[$n] = $n * factorial($n-1);
# }
# $sin = tabulate(sub { my $N = shift;
# return 0 if $N % 2 == 0;
# my $sign = int($N/2) % 2 ? -1 : 1;
# $sign/factorial($N)
# });
# $cos = tabulate(sub { my $N = shift;
# return 0 if $N % 2 != 0;
# my $sign = int($N/2) % 2 ? -1 : 1;
# $sign/factorial($N)
# });
fact = {0:1}
def factorial(n):
if fact.get(n):
return fact[n]
fact[n] = n * factorial(n-1)
return fact[n]
def sin_lambda(N):
if N % 2 == 0:
return 0
sign = 1
if (N/2) % 2 != 0:
-1
return sign / float(factorial(N))
sin = tabulate(sin_lambda)
def cos_lambda(N):
if N % 2 != 0:
return 0
sign = 1
if (N/2) % 2 != 0:
-1
return sign / float(factorial(N))
cos = tabulate(cos_lambda)
# sub add2 {
# my ($s, $t) = @_;
# return $s unless $t;
# return $t unless $s;
# node(head($s) + head($t),
# promise { add2(tail($s), tail($t)) });
# }
def add2(s,t):
if not t:
return s
if not s:
return t
return node(head(s) + head(t),
promise(lambda: add2(tail(s),tail(t))))
# sub mul2 {
# my ($s, $t) = @_;
# return unless $s && $t;
# node(head($s) * head($t),
# promise { mul2(tail($s), tail($t)) });
# }
def mul2(s,t):
if not (s and t):
return None
return node(head(s)*head(t),
promise(lambda: mul2(tail(s),tail(t))))
# sub partial_sums {
# my $s = shift;
# my $r;
# $r = node(head($s), promise { add2($r, tail($s)) });
# }
def partial_sums(s):
r = node(head(s), promise(lambda: add2(r, tail(s))))
return r
# sub powers_of {
# my $x = shift;
# iterate_function(sub {$_[0] * $x}, 1);
# }
def powers_of(x):
return iterate_function(lambda i: i*x, 1)
# sub term_values {
# my ($s, $x) = @_;
# mul2($s, powers_of($x));
# }
def term_values(s,x):
return mul2(s, powers_of(x))
# sub evaluate {
# my ($s, $x) = @_;
# partial_sums(term_values($s, $x));
# }
def evaluate(s,x):
return partial_sums(term_values(s,x))
# my $pi = 3.1415926535897932;
# show(evaluate($cos, $pi/6), 20);
pi = 3.1415926535897932
show(evaluate(cos, pi/6.0), 20)
### grrr..... each of the pieces i test
### above seems to be behaving correctly
### but for some reason the cos(pi/6) example
### is not coming out correctly. no idea :(
# # Get the n'th term from a stream
# sub nth {
# my $s = shift;
# my $n = shift;
# return $n == 0 ? head($s) : nth(tail($s), $n-1);
# }
# # Calculate the approximate cosine of x
# sub cosine {
# my $x = shift;
# nth(evaluate($cos, $x), 20);
# }
def nth(s,n):
if n == 0:
return head(s)
else:
return nth(tail(s), n-1)
def cosine(x):
return nth(evaluate(cos, x), 20)
# sub is_zero_when_x_is_pi {
# my $x = shift;
# my $c = cosine($x/6);
# $c * $c - 3/4;
# }
# show(solve(\&is_zero_when_x_is_pi), 20);
def is_zero_when_x_is_pi(x):
c = cosine(x/6.0)
return c * c - 3/4.0
show(solve(is_zero_when_x_is_pi), 20)
# sub derivative {
# my $s = shift;
# mul2(upfrom(1), tail($s));
# }
def derivative(s):
return mul2(upfrom(1), tail(s))
# show(derivative($sin), 20);
show(derivative(sin), 20)
# exp = tabulate(sub { my $N = shift; 1/factorial($N) });
exp = tabulate(lambda N: 1.0/factorial(N))
# $log_ = tabulate(sub { my $N = shift;
# $N==0 ? 0 : (-1)**$N/-$N });
log_ = tabulate(lambda N: N!=0 and (-1)**N/-N or 0)
# sub multiply {
# my ($S, $T) = @_;
# my ($s, $t) = (head($S), head($T));
# node($s*$t,
# promise { add2(scale(tail($T), $s),
# add2(scale(tail($S), $t),
# node(0,
# promise {multiply(tail($S), tail($T))}),
# ))
# }
# );
# }
def multiply(S,T):
s, t = head(S), head(T)
return node(s*t,
promise(add2(scale(tail(T),s),
add2(scale(tail(S),t),
node(0,
promise(multiply(tail(S), tail(T))))))))
# sub scale {
# my ($s, $c) = @_;
# return if $c == 0;
# return $s if $c == 1;
# transform { $_[0]*$c } $s;
# }
def scale(s, c):
if c == 0:
return None
if c == 1:
return s
return transform(lambda i: i*c, s)
# my $one = add2(multiply($cos, $cos), multiply($sin, $sin));
# show($one, 20);
one = add2(multiply(cos, cos), multiply(sin, sin))
show(one, 20)
### unfortunately i get:
### OverflowError: long int too large to convert to float
### perhaps come back later and figure this out
# sub sum {
# my @s = grep $_, @_;
# my $total = 0;
# $total += head($_ ) for @s;
# node($total,
# promise { sum(map tail($_ ), @s) }
# );
# }
def sum_(_s):
s = [s_ for s_ in _s if s_]
total = 0
for x in s:
total += head(x)
return node(total, promise(lambda: sum_([tail(x) for x in s])))
# sub multiply {
# my ($S, $T) = @_;
# my ($s, $t) = (head($S), head($T));
# node($s*$t,
# promise { sum(scale(tail($T), $s),
# scale(tail($S), $t),
# node(0,
# promise {multiply(tail($S), tail($T))}),
# )
# }
# );
# }
def multiply(S,T):
s,t = head(S), head(T)
return node(s*t,
promise(lambda: sum_(scale(tail(T),s), scale(tail(S),t), node(0, promise(lambda: multiply(tail(S), tail(T)))))))
# # Works only if head($s) = 1
# sub recip {
# my ($s) = shift;
# my $r;
# $r = node(1,
# promise { scale(multiply($r, tail($s)), -1) });
# }
def recip(s):
r = node(1,
promise(lambda: scale(multiply(r,tail(s)), -1)))
return r
# # Works only if head($t) = 1
# sub divide {
# my ($s, $t) = @_;
# multiply($s, recip($t));
# }
# $tan = divide($sin, $cos);
# show($tan, 10);
def divide(s,t):
return multiply(s, recip(t))
tan = divide(sin, cos)
show(tan, 10)
# my @fact = (Math::BigRat->new(1));
# sub factorial {
# my $n = shift;
# return $fact[$n] if defined $fact[$n];
# $fact[$n] = $n * factorial($n-1);
# }
# python 2.6 has "fractions" library
fact = [fraction.Fraction(1,1)]
def factorial(n):
if fact.get(n):
return fact[n]
fact[n] = n * factorial(n-1)
return fact[n]
Sunday, March 22, 2009
99 problems - python - 58
Generate-and-test paradigm
Apply the generate-and-test paradigm to construct all symmetric, completely balanced binary trees with a given number of nodes.
Apply the generate-and-test paradigm to construct all symmetric, completely balanced binary trees with a given number of nodes.
# Example:
# * sym-cbal-trees(5,Ts).
# Ts = [t(x, t(x, nil, t(x, nil, nil)), t(x, t(x, nil, nil), nil)), t(x, t(x, t(x, nil, nil), nil), t(x, nil, t(x, nil, nil)))]
def symmetric_completely_balanced_trees(node_count):
return [tree for tree in completely_balanced_tree(node_count) \
if symmetric_binary_tree(tree)]
Monday, March 9, 2009
Higher Order Perl (Python Style) : Chapter 5 - From Recursion To Iterators
TOC
### Chapter 5 - From Recursion To Iterators
### 5.1 The Partition Problem Revisited
# sub find_share {
# my ($target, $treasures) = @_;
# return [] if $target == 0;
# return if $target < 0 || @$treasures == 0;
# my ($first, @rest) = @$treasures;
# my $solution = find_share($target-$first, \@rest);
# return [$first, @$solution] if $solution;
# return find_share($target , \@rest);
# }
def find_share(target, treasures):
if target == 0:
return []
if target < 0 or len(treasures) == 0:
return
first, rest = treasures[0], treasures[1:]
solution = find_share(target-first, rest)
if solution != None:
return [first] + solution
return find_share(target, rest)
# sub partition {
# my ($target, $treasures) = @_;
# return [] if $target == 0;
# return () if $target < 0 || @$treasures == 0;
# my ($first, @rest) = @$treasures;
# my @solutions = partition($target-$first, \@rest);
# return ((map {[$first, @$_]} @solutions),
# partition($target, \@rest));
# }
def partition(target, treasures):
if target == 0:
return [[]]
if target < 0 or len(treasures) == 0:
return []
first, rest = treasures[0], treasures[1:]
solutions = partition(target-first, rest)
return [[first] + solution for solution in solutions] + partition(target, rest)
# sub make_partitioner {
# my ($n, $treasures) = @_;
# my @todo = [$n, $treasures, []];
# sub {
# while (@todo) {
# my $cur = pop @todo;
# my ($target, $pool, $share) = @$cur;
# if ($target == 0) { return $share }
# next if $target < 0 || @$pool == 0;
# my ($first, @rest) = @$pool;
# push @todo, [$target-$first, \@rest, [@$share, $first]],
# [$target , \@rest, $share ];
# }
# return undef;
# } # end of anonymous iterator function
# } # end of make_partitioner
def make_partitioner(n, treasures):
todo = [[n, treasures, []]]
while todo:
target, pool, share = todo.pop()
if target == 0:
yield share
continue
if target < 0 or len(pool) == 0:
continue
first, rest = pool[0], pool[1:]
todo.append([target-first, rest, share+[first]])
todo.append([target, rest, share])
# sub make_partitioner {
# my ($n, $treasures) = @_;
# my @todo = [$n, $treasures, []];
# sub {
# while (@todo) {
# my $cur = pop @todo;
# my ($target, $pool, $share) = @$cur;
# if ($target == 0) { return $share }
# next if $target < 0 || @$pool == 0;
# my ($first, @rest) = @$pool;
# push @todo, [$target, \@rest, $share ] if @rest;
# if ($target == $first) {
# return [@$share, $first];
# } elsif ($target > $first && @rest) {
# push @todo, [$target-$first, \@rest, [@$share, $first]],
# }
# }
# return undef;
# } # end of anonymous iterator function
# } # end of make_partitioner
def make_partitioner(n, treasures):
todo = [[n, treasures, []]]
while todo:
target, pool, share = todo.pop()
if target == 0:
yield share
continue
if target < 0 or len(pool) == 0:
continue
first, rest = pool[0], pool[1:]
if rest:
todo.append([target, rest, share])
if target == first:
yield share+[first]
elif (target > first and rest):
todo.append([target-first, rest, share+[first]])
### 5.2 How to Convert a Recursive Function to an Iterator
# sub rec {
# my ($n, $k) = @_;
# print $k x $n, "\n";
# for (1 .. $n-1) {
# rec($n-$_, $_);
# }
# }
def rec(n, k):
print str(k) * n
for i in range(1,n):
rec(n-i, i)
# sub partition {
# print "@_\n";
# my ($n, @parts) = @_;
# for (1 .. $n-1) {
# partition($n-$_, $_, @parts);
# }
# }
def partition(n, parts):
print [n] +parts
for i in range(1,n):
partition(n-i, [i]+parts)
# for (@words) { $seen{$_}++ }
# @repeats = grep $seen{$_} > 1, keys %seen;
seen = {}
for word in words:
seen.setdefault(word,[0])[0] += 1
repeats = [word for word in seen if seen[word][0] > 1]
# for (@words) { $seen{lc $_}++ }
# @repeats = grep $seen{$_} > 1, keys %seen;
seen = {}
for word in words:
seen.setdefault(word.lower(),[0])[0] += 1
repeats = [word for word in seen if seen[word][0] > 1]
# sub partition {
# print "@_\n" if decreasing_order(@_);
# my ($n, @parts) = @_;
# for (1 .. $n-1) {
# partition($n-$_, $_, @parts);
# }
# }
def partition(n, parts):
if decreasing_order([n] +parts):
print [n] + parts
for i in range(1,n):
partition(n-i, [i]+parts)
# sub partition {
# print "@_\n";
# my ($largest, @rest) = @_;
# my $min = $rest[0] || 1;
# my $max = int($largest/2);
# for ($min .. $max) {
# partition($largest-$_, $_, @rest);
# }
# }
def partition(largest, rest):
print [largest] + rest
min = (rest + [1])[0]
max = largest / 2
for i in range(min, max+1):
partition(largest-i, [i]+rest)
# sub make_partition {
# my $n = shift;
# my @agenda = ([$n, # $largest
# [], # \@rest
# 1, # $min
# int($n/2), # $max
# ]);
# return Iterator {
# while (@agenda) {
# my $item = pop @agenda;
# my ($largest, $rest, $min, $max) = @$item;
# for ($min .. $max) {
# push @agenda, [$largest - $_, # $largest
# [$_, @$rest], # \@rest
# $_, # $min
# int(($largest - $_)/2), # $max
# ];
# }
# return [$largest, @$rest];
# }
# return;
# };
# }
def make_partition(n):
agenda = [(n, # largest
[], # rest
1, # min
n/2) # max
]
while agenda:
(largest, rest, min, max) = agenda.pop()
for i in range(min, max+1):
agenda.append((largest - i, # largest
[i]+rest, # rest
i, # min
(largest-i)/2 # max
))
yield [largest]+rest
# sub partition {
# my ($largest, $rest, $min, $max) = @_;
# for ($min .. $max) {
# partition($largest-$_, [$_, @$rest], $_, int(($largest - $_)/2));
# }
# return [$largest, @$rest];
# }
def partition(largest, rest, min, max):
for i in range(min, max+1):
partition(largest-i, [i]+rest, i, (largest-i)/2)
return [largest] + rest
# sub make_partition {
# my $n = shift;
# my @agenda = [$n];
# return Iterator {
# while (@agenda) {
# my $item = pop @agenda;
# my ($largest, @rest) = @$item;
# my $min = $rest[0] || 1;
# my $max = int($largest/2);
# for ($min .. $max) {
# push @agenda, [$largest-$_, $_, @rest];
# }
# return $item;
# }
# return;
# };
# }
def make_partition(n):
agenda = [[n,[]]]
while agenda:
largest, rest = agenda.pop()
min = (rest + [1])[0]
max = largest / 2
for i in range(min, max+1):
agenda.append([largest-i, [i]+rest])
yield [largest] + rest
# sub make_partition {
# my $n = shift;
# my @agenda = [$n];
# return Iterator {
# return unless @agenda;
# my $item = pop @agenda;
# my ($largest, @rest) = @$item;
# my $min = $rest[0] || 1;
# my $max = int($largest/2);
# for ($min .. $max) {
# push @agenda, [$largest-$_, $_, @rest];
# }
# return $item;
# };
# }
### we *do* keep the while loop in the python version
### and it looks just like the previous solution
# # Compare two partitions for preferred order
# sub partitions {
# for my $i (0 .. $#$a) {
# my $cmp = $b->[$i] <=> $a->[$i];
# return $cmp if $cmp;
# }
# }
# lists and tuples will compare naturally
# in the correct way (unless i'm missing something here)
def partitions(a,b):
return cmp(a,b)
# sub make_partition {
# my $n = shift;
# my @agenda = [$n];
# return Iterator {
# return unless @agenda;
# my $item = pop @agenda;
# my ($largest, @rest) = @$item;
# my $min = $rest[0] || 1;
# my $max = int($largest/2);
# for ($min .. $max) {
# push @agenda, [$largest-$_, $_, @rest];
# }
# @agenda = sort partitions @agenda;
# return $item;
# };
# }
def make_partition(n):
agenda = [[n,[]]]
while agenda:
largest, rest = agenda.pop()
min = (rest + [1])[0]
max = largest / 2
for i in range(min, max+1):
agenda.append([largest-i, [i]+rest])
agenda.sort()
yield [largest] + rest
### 5.3 A Generic Search Iterator
# use Iterator_Utils 'Iterator';
# sub make_dfs_search {
# my ($root, $children) = @_;
# my @agenda = $root;
# return Iterator {
# return unless @agenda;
# my $node = pop @agenda;
# push @agenda, $children->($node);
# return $node;
# };
# }
def make_dfs_search(root, children):
agenda = [root]
while agenda:
node = agenda.pop()
agenda.extend(children(node))
yield node
# sub make_partition {
# my $n = shift;
# my $root = [$n];
# my $children = sub {
# my ($largest, @rest) = @{shift()};
# my $min = $rest[0] || 1;
# my $max = int($largest/2);
# map [$largest-$_, $_, @rest], ($min .. $max);
# };
# make_dfs_search($root, $children);
# }
def make_partition(n):
root = [n]
def children(largest, rest):
min = (rest + [1])[0]
max = largest / 2
return [(largest-i, [i]+rest) for i in range(min, max+1)]
return make_dfs_search(root, children)
# sub make_dfs_search {
# my ($root, $children, $is_interesting) = @_;
# my @agenda = $root;
# return Iterator {
# while (@agenda) {
# my $node = pop @agenda;
# push @agenda, $children->($node);
# return $node if !$is_interesting || $is_interesting->($node);
# }
# return;
# };
# }
def make_dfs_search(root, children, is_interesting=None):
agenda = [root]
while agenda:
node = agenda.pop()
agenda.extend(children(node))
if is_interesting and is_interesting(node):
yield node
# sub make_dfs_value_search {
# my ($root, $children, $is_interesting, $evaluate) = @_;
# $evaluate = memoize($evaluate);
# my @agenda = $root;
# return Iterator {
# while (@agenda) {
# my $best_node_so_far = 0;
# my $best_node_value = $evaluate->($agenda[0]);
# for (0 .. $#agenda) {
# my $val = $evaluate->($agenda[$_]);
# next unless $val > $best_node_value;
# $best_node_value = $val;
# $best_node_so_far = $_;
# }
# my $node = splice @agenda, $best_node_so_far, 1;
# push @agenda, $children->($node);
# return $node if !$is_interesting || $is_interesting->($node);
# }
# return;
# };
# }
def make_dfs_value_search(root, children, is_interesting=None, evaluate=None):
if not is_interesting:
is_interesting = (lambda x: True)
if not evaluate:
evaluate = (lambda x: x)
agenda = [root]
while agenda:
node = agenda.pop()
agenda.extend(children(node))
if is_interesting(node):
yield node
# sub make_dfs_search {
# my ($root, $children, $is_interesting) = @_;
# my @agenda = $root;
# return Iterator {
# while (@agenda) {
# my $node = pop @agenda;
# push @agenda, reverse $children->($node);
# return $node if !$is_interesting || $is_interesting->($node);
# }
# return;
# };
# }
def make_dfs_search(root, children, is_interesting=None):
agenda = [root]
while agenda:
node = agenda.pop()
agenda.extend(reversed(children(node)))
if is_interesting and is_interesting(node):
yield node
### 5.4 Other General Techniques for Eliminating Recursion
# sub gcd {
# my ($m, $n) = @_;
# if ($n == 0) {
# return $m;
# }
# return gcd($n, $m % $n);
# }
def gcd(m,n):
if n == 0:
return m
return gcd(n, m % n)
# sub gcd {
# my ($m, $n) = @_;
# until ($n == 0) {
# ($m, $n) = ($n, $m % $n);
# }
# return $m;
# }
def gcd(m,n):
while n != 0:
m, n = n, m % n
return m
# sub print_tree {
# my $t = shift;
# return unless $t; # Null tree
# print_tree($t->left);
# print $t->root, "\n";
# print_tree($t->right);
# }
def print_tree(t):
if not t:
return
print_tree(t.left)
print t.root
print_tree(t.right)
# sub print_tree {
# my $t = shift;
# while ($t) {
# print_tree($t->left);
# print $t->root, "\n";
# $t = $t->right;
# }
# }
def print_tree(t):
while t:
print_tree(t.left)
print t.root
t = t.right
# sub print_tree {
# my $t = shift;
# print_tree($t->left) if $t->left;
# print $t->root, "\n";
# print_tree($t->right) if $t->right;
# }
def print_tree(t):
if t.left:
print_tree(t.left)
print t.root
if t.right:
print_tree(t.right)
# sub print_tree {
# my $t = shift;
# do {
# print_tree($t->left) if $t->left;
# print $t->root, "\n";
# $t = $t->right;
# } while $t;
# }
def print_tree(t):
while t:
if t.left:
print_tree(t.left)
print t.root
t = t.right
# sub powerset_recurse ($;@) {
# my ( $set, $powerset, $keys, $values, $n, $i ) = @_;
# if ( @_ == 1 ) { # Initialize.
# my $null = { };
# $powerset = { $null, $null };
# $keys = [ keys %{ $set } ];
# $values = [ values %{ $set } ];
# $nmembers = keys %{ $set }; # This many rounds.
# $i = 0; # The current round.
# }
# # Ready?
# return $powerset if $i == $nmembers;
# # Remap.
# my @powerkeys = keys %{ $powerset };
# my @powervalues = values %{ $powerset };
# my $powern = @powerkeys;
# my $j;
# for ( $j = 0; $j < $powern; $j++ ) {
# my %subset = ( );
# # Copy the old set to the subset.
# @subset{keys %{ $powerset->{ $powerkeys [ $j ] } }} =
# values %{ $powerset->{ $powervalues[ $j ] } };
# # Add the new member to the subset.
# $subset{$keys->[ $i ]} = $values->[ $i ];
# # Add the new subset to the powerset.
# $powerset->{ \%subset } = \%subset;
# }
# # Recurse.
# powerset_recurse( $set, $powerset, $keys, $values, $nmembers, $i+1 );
# }
# we are stuck since python won't permit keys that aren't hashable
# so instead of dicts of dicts i'll use set() with tuples.
# we can easily go back to dicts from a set of tuples
# but i may be missing some subtly important feature of this
# algorithm. but in any case it works.
# also: this algorithm *seems* ridiculously unpythonic
# _set: [(key,val)] # list of
# powerset: [set([(key, val)])] # list of sets of tuple
def powerset_recurse(_set, powerset=None, i=0):
# set up init stuff
if powerset == None:
powerset = [set()]
if i == len(_set):
return powerset
powerset_copy = copy.deepcopy(powerset)
ith_item = _set[i]
for subset in powerset_copy:
subset.add(ith_item)
powerset += powerset_copy
return powerset_recurse(_set, powerset, i+1)
### uggg. so that works, and *seems* very close
### in principle to the original but I feel like
### i didn't try hard enough to match the original style
# sub powerset_recurse ($) {
# my ( $set ) = @_;
# my $null = { };
# my $powerset = { $null, $null };
# my $keys = [ keys %{ $set } ];
# my $values = [ values %{ $set } ];
# my $nmembers = keys %{ $set }; # This many rounds.
# my $i = 0; # The current round.
# until ($i == $nmembers) {
# # Remap.
# my @powerkeys = keys %{ $powerset };
# my @powervalues = values %{ $powerset };
# my $powern = @powerkeys;
# my $j;
# for ( $j = 0; $j < $powern; $j++ ) {
# my %subset = ( );
# # Copy the old set to the subset.
# @subset{keys %{ $powerset->{ $powerkeys [ $j ] } }} =
# values %{ $powerset->{ $powervalues[ $j ] } };
# # Add the new member to the subset.
# $subset{$keys->[ $i ]} = $values->[ $i ];
# # Add the new subset to the powerset.
# $powerset->{ \%subset } = \%subset;
# }
# $i++;
# }
# return $powerset;
# }
def powerset_recurse(_set, powerset=None, i=0):
# set up init stuff
if powerset == None:
powerset = [set()]
while i < len(_set):
powerset_copy = copy.deepcopy(powerset)
ith_item = _set[i]
for subset in powerset_copy:
subset.add(ith_item)
powerset += powerset_copy
i += 1
return powerset
# sub powerset_recurse ($) {
# my ( $set ) = @_;
# my $null = { };
# my $powerset = { $null, $null };
# my $keys = [ keys %{ $set } ];
# my $values = [ values %{ $set } ];
# my $nmembers = keys %{ $set }; # This many rounds.
# for my $i (0 .. $nmembers-1) {
# # Remap.
# my @powerkeys = keys %{ $powerset };
# my @powervalues = values %{ $powerset };
# my $powern = @powerkeys;
# my $j;
# for ( $j = 0; $j < $powern; $j++ ) {
# my %subset = ( );
# # Copy the old set to the subset.
# @subset{keys %{ $powerset->{ $powerkeys [ $j ] } }} =
# values %{ $powerset->{ $powervalues[ $j ] } };
# # Add the new member to the subset.
# $subset{$keys->[ $i ]} = $values->[ $i ];
# # Add the new subset to the powerset.
# $powerset->{ \%subset } = \%subset;
# }
# }
# return $powerset;
# }
def powerset_recurse(_set, powerset=None, i=0):
# set up init stuff
if powerset == None:
powerset = [set()]
for i in range(len(_set)):
powerset_copy = copy.deepcopy(powerset)
ith_item = _set[i]
for subset in powerset_copy:
subset.add(ith_item)
powerset += powerset_copy
return powerset
# sub powerset_recurse ($) {
# my ( $set ) = @_;
# my $null = { };
# my $powerset = { $null, $null };
# while (my ($key, $value) = each %$set) {
# # Remap.
# my @powerkeys = keys %{ $powerset };
# my @powervalues = values %{ $powerset };
# my $powern = @powerkeys;
# my $j;
# for ( $j = 0; $j < $powern; $j++ ) {
# my %subset = ( );
# # Copy the old set to the subset.
# @subset{keys %{ $powerset->{ $powerkeys [ $j ] } }} =
# values %{ $powerset->{ $powervalues[ $j ] } };
# # Add the new member to the subset.
# $subset{$key} = $value;
# # Add the new subset to the powerset.
# $powerset->{ \%subset } = \%subset;
# }
# }
# return $powerset;
# }
def powerset_recurse(_set):
powerset = [set()]
for ith_item in (_set):
powerset_copy = copy.deepcopy(powerset)
for subset in powerset_copy:
subset.add(ith_item)
powerset += powerset_copy
return powerset
# sub binary {
# my ($n) = @_;
# return $n if $n == 0 || $n == 1;
# my $k = int($n/2);
# my $b = $n % 2;
# my $E = binary($k);
# return $E . $b;
# }
def binary(n):
if n in (0,1):
return str(n)
k = n / 2
b = n % 2
return binary(k) + str(b)
# sub binary {
# my ($n, $RETVAL) = @_;
# $RETVAL = "" unless defined $RETVAL;
# my $k = int($n/2);
# my $b = $n % 2;
# $RETVAL = "$b$RETVAL";
# return $RETVAL if $n == 0 || $n == 1;
# binary($k, $RETVAL);
# }
def binary(n, retval=""):
k = n / 2
b = n % 2
retval = str(b)+retval
if n in (0,1):
return retval
return binary(k, retval)
# sub binary {
# my ($n, $RETVAL) = @_;
# $RETVAL = "";
# while (1) {
# my $k = int($n/2);
# my $b = $n % 2;
# $RETVAL = "$b$RETVAL";
# return $RETVAL if $n == 0 || $n == 1;
# $n = $k;
# }
# }
def binary(n, retval=""):
while 1:
k = n / 2
b = n % 2
retval = str(b)+retval
if n in (0,1):
return retval
n = k
# sub binary {
# my ($n, $RETVAL) = @_;
# $RETVAL = "";
# while (1) {
# my $b = $n % 2;
# $RETVAL = "$b$RETVAL";
# return $RETVAL if $n == 0 || $n == 1;
# $n = int($n/2);
# }
# }
def binary(n, retval=""):
while 1:
b = n % 2
retval = str(b)+retval
if n in (0,1):
return retval
n = n/2
# sub factorial {
# my ($n) = @_;
# return 1 if $n == 0;
# return factorial($n-1) * $n;
# }
def factorial(n):
if n == 0:
return 1
return factorial(n-1)*n
# sub factorial {
# my ($n, $product) = @_;
# $product = 1 unless defined $product;
# return $product if $n == 0;
# return factorial($n-1, $n * $product);
# }
def factorial(n, product=1):
if n == 0:
return product
return factorial(n-1, n*product)
# sub factorial {
# my ($n) = @_;
# my $product = 1;
# until ($n == 0) {
# $product *= $n;
# $n--;
# }
# return $product;
# }
def factorial(n):
product = 1
while n != 0:
product *= n
n -= 1
return product
# sub print_tree {
# my $t = shift;
# do {
# print_tree($t->left) if $t->left;
# print $t->root, "\n";
# $t = $t->right;
# } while $t;
# }
def print_tree(t):
while t:
if t.left:
print_tree(t.left)
print t.root
t = t.right
# sub print_tree {
# my $t = shift;
# my @STACK;
# do {
# push(@STACK, $t), $t = $t->left if $t->left;
# RETURN:
# print $t->root, "\n";
# $t = $t->right;
# } while $t;
# return unless @STACK;
# $t = pop @STACK;
# goto RETURN;
# }
### this and the next couple examples
### use GOTOs. not much i can do about that.
### if there is a way to simulate gotos in python
### i'd be interested to hear it.
# sub fib {
# my $n = shift;
# if ($n < 2) { return $n }
# fib($n-2) + fib($n-1);
# }
def fib(n):
if n < 2:
return n
return fib(n-2) + fib(n-1)
# sub fib {
# my $n = shift;
# if ($n < 2) {
# return $n;
# } else {
# my $s1 = fib($n-2);
# my $s2 = fib($n-1);
# return $s1 + $s2;
# }
# }
def fib(n):
if n < 2:
return n
else:
s1 = fib(n-2)
s2 = fib(n-1)
return s1 + s2
# sub fib {
# my $n = shift;
# while (1) {
# if ($n < 2) {
# return $n;
# } else {
# my $s1 = fib($n-2);
# my $s2 = fib($n-1);
# return $s1 + $s2;
# }
# }
# }
def fib(n):
while 1:
if n < 2:
return n
else:
s1 = fib(n-2)
s2 = fib(n-1)
return s1 + s2
# sub fib {
# my $n = shift;
# my ($s1, $s2, $return);
# while (1) {
# if ($n < 2) {
# return $n;
# } else {
# if ($BRANCH == 0) {
# $return = fib($n-2);
# } elsif ($BRANCH == 1) {
# $s1 = $return;
# $return = fib($n-1);
# } elsif ($BRANCH == 2) {
# $s2 = $return;
# $return = $s1 + $s2;
# }
# }
# }
# }
def fib(n):
BRANCH = 0
while 1:
if n < 2:
return n
else:
if BRANCH == 0:
_return = fib(n-2)
elif BRANCH == 1:
s1 = _return
_retrun = fib(n-2)
elif BRANCH == 2:
s2 = _return
_return = s1 + s2
return _return
# sub fib {
# my $n = shift;
# my ($s1, $s2, $return);
# my $BRANCH = 0;
# while (1) {
# if ($n < 2) {
# return $n;
# } else {
# if ($BRANCH == 0) {
# $return = fib($n-2);
# } elsif ($BRANCH == 1) {
# $s1 = $return;
# $return = fib($n-1);
# } elsif ($BRANCH == 2) {
# $s2 = $return;
# $return = $s1 + $s2;
# }
# }
# }
# }
def fib(n):
BRANCH = 0
while 1:
if n < 2:
return n
else:
if BRANCH == 0:
_return = fib(n-2)
elif BRANCH == 1:
s1 = _return
_return = fib(n-1)
elif BRANCH == 2:
s2 = _return
_return = s1 + s2
return _return
# sub fib {
# my $n = shift;
# my ($s1, $s2, $return);
# my $BRANCH = 0;
# while (1) {
# if ($n < 2) {
# $return = $n;
# } else {
# if ($BRANCH == 0) {
# $return = fib($n-2);
# } elsif ($BRANCH == 1) {
# $s1 = $return;
# $return = fib($n-1);
# } elsif ($BRANCH == 2) {
# $return = $s1 + $s2;
# }
# }
# }
# }
def fib(n):
BRANCH = 0
while 1:
if n < 2:
_return = n
else:
if BRANCH == 0:
_return = fib(n-2)
elif BRANCH == 1:
s1 = _return
_return = fib(n-1)
elif BRANCH == 2:
_return = s1 + s2
return _return
# sub fib {
# my $n = shift;
# my ($s1, $s2, $return);
# my $BRANCH = 0;
# my @STACK;
# while (1) {
# if ($n < 2) {
# $return = $n;
# } else {
# if ($BRANCH == 0) {
# push @STACK, [ $BRANCH, $s1, $s2, $n ];
# $n -= 2;
# $BRANCH = 0;
# next;
# } elsif ($BRANCH == 1) {
# $s1 = $return;
# push @STACK, [ $BRANCH, $s1, $s2, $n ];
# $n -= 1;
# $BRANCH = 0;
# next;
# } elsif ($BRANCH == 2) {
# $s2 = $return;
# $return = $s1 + $s2;
# }
# }
# }
# }
def fib(n):
BRANCH = 0
STACK = []
while 1:
if n < 2:
_return = n
else:
if BRANCH == 0:
STACK.append([BRANCH, s1, s2, n])
n -= 2
BRANCH = 0
continue
elif BRANCH == 1:
s1 = _return
STACK.append([BRANCH, s1, s2, n])
n -= 1
BRANCH = 0
continue
elif BRANCH == 2:
s2 = _return
_return = s1 + s2
return _return
# sub fib {
# my $n = shift;
# my ($s1, $s2, $return);
# my $BRANCH = 0;
# my @STACK;
# while (1) {
# if ($n < 2) {
# $return = $n;
# } else {
# if ($BRANCH == 0) {
# push @STACK, [ $BRANCH, $s1, $s2, $n ];
# $n -= 2;
# $BRANCH = 0;
# next;
# } elsif ($BRANCH == 1) {
# $s1 = $return;
# push @STACK, [ $BRANCH, $s1, $s2, $n ];
# $n -= 1;
# $BRANCH = 0;
# next;
# } elsif ($BRANCH == 2) {
# $s2 = $return;
# $return = $s1 + $s2;
# }
# }
# return $return unless @STACK;
# ($BRANCH, $s1, $s2, $n) = @{pop @STACK};
# $BRANCH++;
# }
def fib(n):
BRANCH = 0
STACK = []
while 1:
if n < 2:
_return = n
else:
if BRANCH == 0:
STACK.append([BRANCH, s1, s2, n])
n -= 2
BRANCH = 0
continue
elif BRANCH == 1:
s1 = _return
STACK.append([BRANCH, s1, s2, n])
n -= 1
BRANCH = 0
continue
elif BRANCH == 2:
s2 = _return
_return = s1 + s2
if not STACK:
return _return
(BRANCH, s1, s2, n) = STACK.pop()
BRANCH += 1
# sub fib {
# my $n = shift;
# my ($s1, $s2, $return);
# my $BRANCH = 0;
# my @STACK;
# while (1) {
# if ($n < 2) {
# $return = $n;
# } else {
# if ($BRANCH == 0) {
# push @STACK, [ $BRANCH, 0, $s2, $n ];
# $n -= 2;
# next;
# } elsif ($BRANCH == 1) {
# push @STACK, [ $BRANCH, $return, $s2, $n ];
# $n -= 1;
# $BRANCH = 0;
# next;
# } elsif ($BRANCH == 2) {
# $s2 = $return;
# $return = $s1 + $s2;
# }
# }
# return $return unless @STACK;
# ($BRANCH, $s1, $s2, $n) = @{pop @STACK};
# $BRANCH++;
# }
def fib(n):
BRANCH = 0
STACK = []
while 1:
if n < 2:
_return = n
else:
if BRANCH == 0:
STACK.append([BRANCH, 0, s2, n])
n -= 2
BRANCH = 0
continue
elif BRANCH == 1:
s1 = _return
STACK.append([BRANCH, _return, s2, n])
n -= 1
BRANCH = 0
continue
elif BRANCH == 2:
s2 = _return
_return = s1 + s2
if not STACK:
return _return
(BRANCH, s1, s2, n) = STACK.pop()
BRANCH += 1
# sub fib {
# my $n = shift;
# my ($s1, $return);
# my $BRANCH = 0;
# my @STACK;
# while (1) {
# if ($n < 2) {
# $return = $n;
# } else {
# if ($BRANCH == 0) {
# push @STACK, [ $BRANCH, 0, $n ];
# $n -= 2;
# next;
# } elsif ($BRANCH == 1) {
# push @STACK, [ $BRANCH, $return, $n ];
# $n -= 1;
# $BRANCH = 0;
# next;
# } elsif ($BRANCH == 2) {
# $return += $s1;
# }
# }
# return $return unless @STACK;
# ($BRANCH, $s1, $n) = @{pop @STACK};
# $BRANCH++;
# }
# }
def fib(n):
BRANCH = 0
STACK = []
while 1:
if n < 2:
_return = n
else:
if BRANCH == 0:
STACK.append([BRANCH, 0, n])
n -= 2
continue
elif BRANCH == 1:
STACK.append([BRANCH, _return, n])
n -= 1
BRANCH = 0
continue
elif BRANCH == 2:
_return += s1
if not STACK:
return _return
(BRANCH, s1, s2, n) = STACK.pop()
BRANCH += 1
# sub fib {
# my $n = shift;
# my ($s1, $return);
# my $BRANCH = 0;
# my @STACK;
# while (1) {
# if ($n < 2) {
# $return = $n;
# } else {
# if ($BRANCH == 0) {
# push (@STACK, [ $BRANCH, 0, $n ]), $n -= 1 while $n >= 2;
# $return = $n;
# } elsif ($BRANCH == 1) {
# push @STACK, [ $BRANCH, $return, $n ];
# $n -= 2;
# $BRANCH = 0;
# next;
# } elsif ($BRANCH == 2) {
# $return += $s1;
# }
# }
# return $return unless @STACK;
# ($BRANCH, $s1, $n) = @{pop @STACK};
# $BRANCH++;
# }
def fib(n):
BRANCH = 0
STACK = []
while 1:
if n < 2:
_return = n
else:
if BRANCH == 0:
STACK.append([BRANCH, 0, n])
while n >= 2:
n =- 1
_return = n
elif BRANCH == 1:
STACK.append([BRANCH, _return, n])
n -= 2
BRANCH = 0
continue
elif BRANCH == 2:
_return += s1
if not STACK:
return _return
(BRANCH, s1, n) = STACK.pop()
BRANCH += 1
# sub fib {
# my $n = shift;
# my ($s1, $return);
# my $BRANCH = 0;
# my @STACK;
# while (1) {
# if ($n < 2) {
# $return = $n;
# } else {
# if ($BRANCH == 0) {
# push (@STACK, [ 1, 0, $n ]), $n -= 1 while $n >= 2;
# $return = $n;
# } elsif ($BRANCH == 1) {
# push @STACK, [ 2, $return, $n ];
# $n -= 2;
# $BRANCH = 0;
# next;
# } elsif ($BRANCH == 2) {
# $return += $s1;
# }
# }
# return $return unless @STACK;
# ($BRANCH, $s1, $n) = @{pop @STACK};
# }
# }
# NOTE: I got lazy/confused by the end of this chapter so
# so these last few "fib" functions are not tested
# But it was an interesting discussion on "unfolding"
# recursion.
def fib(n):
BRANCH = 0
STACK = []
while 1:
if n < 2:
_return = n
else:
if BRANCH == 0:
while n >= 2:
STACK.append([1, 0, n])
n =- 1
_return = n
elif BRANCH == 1:
STACK.append([2, _return, n])
n -= 2
BRANCH = 0
continue
elif BRANCH == 2:
_return += s1
if not STACK:
return _return
(BRANCH, s1, n) = STACK.pop()
Subscribe to:
Posts (Atom)
