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


# 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
    print


# 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
    print


# # 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]

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.

# 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)]

100 Pushups: "week 6" milestone - 70

Holy crap. I finally got to 70. So the adventure continues on the hilariously optimistic "6 week" program to do 100 pushups.

The big question now is whether I can get to 100 before a year has elapsed. I think there is a chance. But honestly I'll just be happy to get there. And to think I was going to skip tonight since I felt a little under the weather.

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

My Dangerous New Obsession

I think if I had to blame anyone, I'd start with Alan Kay. I recently read the following quote by him:

I think it is safe to say that most of the Squeak community is dedicated to making this Smalltalk more useful and accessible, and not devoted to making something so much better as to render Smalltalk obsolete (a fate I would dearly love to see happen).

Alan Kay wants smalltalk to go away? Well, if I'm going to use the man's language I should also have the decency to try to improve upon it and replace it.

So that was the start of a tiny little snow ball. And the snow ball grew. And now I find myself keeping notebooks full of ideas for creating a new programming language.

And that is my obsession. I've got it in my head that I could create a new language. And that this is somehow a good use of my time. So I'm constantly comparing and contrasting the various features that different languages have. Looking for a good idea to steal or a wart to avoid. I've been shopping around for language parsers and VMs to use.

And you know what? It's fun as hell. I actually don't have any illusions that I'm going to set the world on fire or that anyone but me will ever use my language. Or, let's be serious, that there is much likelihood that I will get past the vaporware stage. But I really feel like I'm seeing the landscape of languages with new eyes. Sort of like when you take a class on drawing and your brain starts learning how to do the "switch". And you can almost magically just draw things. I feel like my eyes are really seeing languages and language features for the first time.

So what is my language like? Not much. I've actually been avoiding trying to commit to any specific syntax. Which is probably going to make it lisp like if I'm not careful. (Not that there's anything wrong with that). When I start committing to various features it's been coming out something like a pythonized haskell (or a haskellized python) with strong nods to smalltalk minimalism. In a word its sort of an incoherent jumble. But I keep circling around and trying new things.

And like I said it's really fun. And I'm learning a lot. (And I've become addicted to starting sentences with "and").

I wonder if this is a common or rare affliction. I've never met anyone who said that they were trying to create their own language. Perhaps others are too smart to go down that road in the first place or too ashamed to admit they did and failed.

In any case, be prepared for the next big thing. Any decade now....

Higher Order Perl (Python Style) : Chapter 4 - Iterators

TOC

### CHAPTER 4 Iterators


### 4.1 introduction

# @lines = open('filename'); # alternate universe interface
lines = open("filename") # a less alternate universe interface


# open(FILEHANDLE, 'filename');
# while () {
#   last if /Plutonium/;
# }
# close FILEHANDLE;
# # do something with $_;
fh = open("filename")
for line in fh:
    if "Plutonium" in line:
        break
fh.close()
# do something with line




# # alternate universe interface
# @lines = open('filename');
# for (@lines) {
#   last if /Plutonium/;
# }
# # do something with $_;
lines = open("filename").readlines()
for line in lines:
    if "Plutonium" in line:
        break
fh.close()
# do something with line


# @lines = open("yes |"); # alternate universe interface
lines = os.popen("yes").readlines() # alternate universes interface



# sub parse_section {
#   my $fh = shift;
#   my $title = parse_section_title($fh);
#   my %variables = parse_variables($fh);
#   return [$title, \%variables];
# }
def parse_section(fh):
    title = parse_section_title(fh)
    variables = parse_variables(fh)
    return title, variables


# sub parse_section {
#   my @lines = @_;
#   my $title = parse_section_title(@lines);
#   my %variables = parse_variables(@lines);
#   return [$title, \%variables];
# }
# In the python case we *could* easily
# pop values from the list (but really you 
# could in perl as well)
def parse_section(lines):
    title = parse_section_title(lines)
    variables = parse_variables(lines)
    return title, variables




# opendir D, "/tmp";
# @entries = readdir D;
# In python we get a list instead of a iterator
entries = os.listdir("/tmp")


# opendir D, "/tmp";
# while (my $entry = readdir D) {
#   # Do something with $entry
# }
# Python doesn't have "scalar" mode type behavior changes
for entry in os.listdir("/tmp"):
  # Do something with $entry


# while (my $file = glob("/tmp/*.[ch]")) {
#   # Do something with $file
# }
# glob in python is also not an iterator
for _file in glob.glob("/tmp/*.[ch]"):
    # Do something with $file

# while (my $key = each %hash) {
#   # Do something with $key
# }
# depending on version of python 
# hash may automagically be an iterator
# (maybe all versions...)
for key in hash.iterkeys():
    # Do something with key




# @matches = ("12:34:56" =~ m/(\d+)/g);
matches = re.findall("(\d+)", "12:34:56")

# while ("12:34:56" = ̃ m/(\d+)/g) {
#   # do something with $1
# }
for m in re.finditer("(\d+)", "12:34:56"):
    # do something with m (where m is a "match" object)


### 4.2 Homemade Iterators

# sub dir_walk {
#   my ($dir, $filefunc, $dirfunc, $user) = @_;
#   my $iterator = make_iterator($dir);
#   while (my $filename = NEXTVAL($iterator)) {
#     if (-f $filename) { $filefunc->($filename, $user) }
#     else              {  $dirfunc->($filename, $user) }
#   }
# }
# In python os.walk returns an iterator as is
def dir_walk(dir, filefunc, dirfunc, user):
    iterator = make_iterator(dir)
    for filename in iterator:
        if os.path.isfile(filename):
            filefunc(filename, user)
        else:
            dirfunc(filename, user)


# sub upto {
#   my ($m, $n) = @_;
#   return sub {
#     return $m <= $n ? $m++ : undef;
#   };
# }
# my $it = upto(3, 5);
def upto(m,n):
    _i = [m]
    def foo():
        val = _i[0]
        _i[0] += 1
        if val > n:
            return None
        return val

    return foo

it = upto(3,5)
## of course in python it's more natural to do the following:
# def upto(m,n):
#     for x in range(m,n+1):
#         yield x


# my $nextval = $it->();
nextval = it()


# while (defined(my $val = $it->())) {
#   # now do something with $val, such as:
#   print "$val\n";
# }
# this doesn't translate in a pretty way to python
# since we can't have statements in a while 
# context
val = it()
while val != None:
    # now do something with val, such as:
    print val
    val = it()
# but of course we'd just use:
for val in it:
    print val



# for my $val (1 .. 10000000) {
#    # now do something with $val
# }
for val in range(1, 10000000):
    # now do something with val

# package Iterator_Utils;
# use base Exporter;
# @EXPORT_OK = qw(NEXTVAL Iterator
#                 append imap igrep
#                 iterate_function filehandle_iterator list_iterator);
# %EXPORT_TAGS = ('all' => \@EXPORT_OK);
# sub NEXTVAL { $_[0]->() }

# my $nextval = NEXTVAL($it);

# while (defined(my $val = NEXTVAL($it))) {
#   # now do something with $val
# }

# No need to do these machinations since this is already built into
# python except we'd do this with "for"
for val in it:
    # not do something with val


# sub upto {
#   my ($m, $n) = @_;
#   return Iterator {
#     return $m <= $n ? $m++ : undef;
#   };
# }
# sub Iterator (&) { return $_[0] }
# in python we just do this with a yield
def upto(m, n):
    i = m
    while i <= n:
        yield i
        i += 1


# # iterator version
# sub dir_walk {
#   my @queue = shift;
#   return Iterator {
#     while (@queue) {
#       my $file = shift @queue;
#       if (-d $file) {
#         opendir my $dh, $file or next;
#         my @newfiles = grep {$_ ne "." && $_ ne ".."} readdir $dh;
#         push @queue, map "$file/$_", @newfiles;
#       }
#       return $file;
#     } else {
#       return;
#     }
#   };
# }
def dir_walk(root):
    queue = [root]
    while queue:
        _file = queue.pop(0)
        if os.path.isdir(_file):
            for newfile in os.listdir(_file):
                queue.append(os.path.join(_file, newfile))
        yield _file


                
                                
# sub dir_walk {
#   my ($top, $code) = @_;
#   my $DIR;
#   $code->($top);
#   if (-d $top) {
#     my $file;
#     unless (opendir $DIR, $top) {
#       warn "Couldn’t open directory $top: $!; skipping.\n";
#       return;
#     }
#     while ($file = readdir $DIR) {
#       next if $file eq '.'|| $file eq '..'
#       dir_walk("$top/$file", $code);
#     }
#   }
# }
def dir_walk(top, code):
    code(top)
    if os.path.isdir(top):
        try:
            for _file in os.listdir(top):
                dir_walk(os.path.join(top,_file), code)
        except StandardError, why:
            print "Couldn't open directory %s: %s" % (top, why)
            return


### 4.3 Examples

# sub interesting_files {
#   my $is_interesting = shift;
#   my @queue = @_;
#   return Iterator {
#     while (@queue) {
#       my $file = shift @queue;
#       if (-d $file) {
#         opendir my $dh, $file or next;
#         my @newfiles = grep {$_ ne "." && $_ ne ".."} readdir $dh;
#         push @queue, map "$file/$_", @newfiles;
#       }
#       return $file if $is_interesting->($file);
#     }
#     return;
#   };
# }
def interesting_files(is_interesting, *top_dirs):
    queue = list(top_dirs)
    
    while queue:
        _file = queue.pop(0)
        if os.path.isdir(_file):
            for newfile in os.listdir(_file):
                queue.append(os.path.join(_file, newfile))
        if is_interesting(_file):
            yield _file        


# # Files are deemed to be interesting if they mention octopuses
# sub contains_octopuses {
#   my $file = shift;
#   return unless -T $file && open my($fh), "<", $file;
#   while (<$fh>) {
#     return 1 if /octopus/i;
#   }
#   return;
# }
# my $octopus_file =
#   interesting_files(\&contains_octopuses, 'uploads', 'downloads');
# while ($file = NEXTVAL($octopus_file)) {
#   # do something with the file
# }
# if (NEXTVAL($next_octopus)) {
#   # yes, there is an interesting file
# } else {
#   # no, there isn’t.
# }
# undef $next_octopus;
def contains_octopuses(_file):
    if not os.path.isfile(_file):
        return False
    for line in file(_file):
        if "octopus" in line:
            return True
    return False
octopus_file = interesting_files(contains_octopuses, "uploads", "downloads")
for _octopus_file in octopus_file:
    # do something with the file
try:
    next_octopus.next()
    # yes, there is an interesting file
except StopIteration:
    # no there isn't
del next_octopus
    


# sub permute {
#     my @items = @{ $_[0] };
#     my @perms = @{ $_[1] };
#     unless (@items) {
#         print "@perms\n";
#     } else {
#         my(@newitems,@newperms,$i);
#         foreach $i (0 .. $#items) {
#             @newitems = @items;
#             @newperms = @perms;
#             unshift(@newperms, splice(@newitems, $i, 1));
#             permute([@newitems], [@newperms]);
#         }
#     }
# }
# # sample call:
# permute([qw(red yellow blue green)], []);
# I suspect I don't have this quite right
# it produces the permuations but doesn't
# have the problem of waiting for the end to
# start showing the permutations
def permute(items, perms):
    if not items:
        print perms
    else:
        for i in range(len(items)):
            newitems = items[:]
            newitem = newitems.pop(i)
            newperms = [newperm+[newitem] for newperm in perms] or [[newitem]]
            permute(newitems, newperms)
# sample call
permute(["red", "yello", "blue", "green"], [])



# my $it = permute('A'..'D');
# while (my @p = NEXTVAL($it)) {
#   print "@p\n";
# }
it = permute(["A","B","C","D"])
for p in it:
    print p



# sub permute {
#   my @items = @_;
#   my @pattern = (0) x @items;
#   return Iterator {
#     return unless @pattern;
#     my @result = pattern_to_permutation(\@pattern, \@items);
#     @pattern = increment_pattern(@pattern);
#     return @result;
#   };
# }
def permute(items):
    pattern = [0] * len(items)
    
    while pattern:
        result = pattern_to_permutation(pattern, items)
        pattern = increment_pattern(pattern)
        yield result


# sub pattern_to_permutation {
#   my $pattern = shift;
#   my @items = @{shift()};
#   my @r;
#   for (@$pattern) {
#     push @r, splice(@items, $_, 1);
#   }
#   @r;
# }
def pattern_to_permutation(pattern, items):
    items = items[:]
    r = []
    for _x in pattern:
        r.append(items.pop(_x))
    return r 



# sub increment_odometer {
#   my @odometer = @_;
#   my $wheel = $#odometer;    # start at rightmost wheel
#   until ($odometer[$wheel] < 9 || $wheel < 0) {
#     $odometer[$wheel] = 0;
#     $wheel--; # next wheel to the left
#   }
#   if ($wheel < 0) {
#     return;   # fell off the left end; no more sequences
#   } else {
#     $odometer[$wheel]++;  # this wheel now turns one notch
#     return @odometer;
#   }
# }
def increment_odometer(odometer):
    wheel = len(odometer) - 1
    while not (odometer[wheel] < 9 or wheel < 0):
        odometer[wheel] = 0
        wheel -= 1
    if wheel < 0:
        return
    else:
        odometer[wheel] += 1
        return odometer



# sub increment_pattern {
#   my @odometer = @_;
#   my $wheel = $#odometer;    # start at rightmost wheel
#   until ($odometer[$wheel] < $#odometer-$wheel || $wheel < 0) {
#     $odometer[$wheel] = 0;
#     $wheel--; # next wheel to the left
#   }
#   if ($wheel < 0) {
#     return;   # fell off the left end; no more sequences
#   } else {
#     $odometer[$wheel]++; # this wheel now turns one notch
#     return @odometer;
#   }
# }
def increment_pattern(odometer):
    wheel = len(odometer) - 1
    while not (odometer[wheel] < (len(odometer)-1-wheel) or wheel < 0):
        odometer[wheel] = 0
        wheel -= 1
    if wheel < 0:
        return
    else:
        odometer[wheel] += 1
        return odometer


# sub n_to_pat {
#   my @odometer;
#   my ($n, $length) = @_;
#   for my $i (1 .. $length) {
#     unshift @odometer, $n % $i;
#     $n = int($n/$i);
#   }
#   return $n ? () : @odometer;
# }
def n_to_pat(n, length):
    odometer = []
    for i in range(1, length+1):
        odometer.insert(0, n % i)
        n = n / i
    return not n and odometer or []


# sub permute {
#   my @items = @_;
#   my $n = 0;
#   return Iterator {
#     my @pattern = n_to_pat($n, scalar(@items));
#     my @result = pattern_to_permutation(\@pattern, \@items);
#     $n++;
#     return @result;
#   };
# }
def permute(items):
    n = 0
    while 1:
        pattern = n_to_pat(n, len(items))
        if not pattern:
            break
        result = pattern_to_permutation(pattern, items)
        yield result
        n += 1


# sub iterate_function {
#   my $n = 0;
#   my $f = shift;
#   return Iterator {
#     return $f->($n++);
#   };
# }
def iterate_function(f):
    n = 0
    while 1:
        yield f(n)
        n += 1


# sub permute {
#   my @items = @_;
#   my $n = 0;
#   return Iterator {
#     $n++, return @items if $n==0;
#     my $i;
#     my $p = $n;
#     for ($i=1; $i<=@items && $p%$i==0; $i++) {
#       $p /= $i;
#     }
#     my $d = $p % $i;
#     my $j = @items - $i;
#     return if $j < 0;
#     @items[$j+1..$#items] = reverse @items[$j+1..$#items];
#     @items[$j,$j+$d] = @items[$j+$d,$j];
#     $n++;
#     return @items;
#   };
# }
 def permute(_items):
    n = 0
    items = _items[:]

    if n == 0:
        yield items

    n += 1
    while 1:
        # make a copy so list(permute(my_list)) returns n copies of same item
        # otherwise can remove
        items = items[:] 
        i = 1
        p = n
        while i <= len(items)+1 and p % i == 0:
            p /= i
            i += 1
        d = p % i
        j = len(items) - i 

        if j < 0:
            return

        items[j+1:len(items)] = reversed(items[j+1:len(items)])
        x,y = items[j+d], items[j]
        items[j] = x
        items[j+d] = y 
        n += 1

        yield items



# sub make_genes {
#   my $pat = shift;
#   my @tokens = split /[()]/, $pat;
#   for (my $i = 1; $i < @tokens; $i += 2) {
#     $tokens[$i] = [0, split(//, $tokens[$i])];
#   }
#   my $FINISHED = 0;
#   return Iterator {
#     return if $FINISHED;
#     my $finished_incrementing = 0;
#     my $result = "";
#     for my $token (@tokens) {
#       if (ref $token eq "") {    # plain string
#         $result .= $token;
#       } else {                   # wildcard
#         my ($n, @c) = @$token;
#         $result .= $c[$n];
#         unless ($finished_incrementing) {
#           if ($n == $#c) { $token->[0] = 0 }
#           else { $token->[0]++; $finished_incrementing = 1 }
#         }
#       }
#     }
#     $FINISHED = 1 unless $finished_incrementing;
#     return $result;
#   }
# }
def make_genes(pat):
    tokens = re.split("[()]",pat)

    for i in range(len(tokens))[1::2]:
        tokens[i] = [0] + list(tokens[i])

    FINISHED = False
    while not FINISHED:
        finished_incrementing = False
        result = ""
        for token in tokens:
            if token.__class__ is str:
                result += token
            else:
                n, c = token[0], token[1:]
                result += c[n]
                if not finished_incrementing:
                    if n == len(c) - 1:
                        token[0] = 0
                    else:
                        token[0] += 1
                        finished_incrementing = True
        if not finished_incrementing:
            FINISHED = True
        yield result




# %n_expand = qw(N ACGT 
#                B CGT D AGT H ACT V ACG
#                K GT M AC R AG S CG W AT Y CT);
# sub make_dna_sequences {
#   my $pat = shift;
#   for my $abbrev (keys %n_expand) {
#     $pat =~ s/$abbrev/($n_expand{$abbrev})/g;
#   }
#   return make_genes($pat);
# }
n_expand = {"N" : "ACGT",
            "B" : "CGT", "D" : "AGT", "H" : "ACT", "V" : "ACG",
            "K" : "GT",  "M" : "AC",  "R" : "AG",  "S" : "CG",  "W" : "AT", "Y" : "CT"}
def make_dna_sequences(pat):
    for abbrev in n_expand:
        pat = re.sub(abbrev, n_expand[abbrev], pat)
    
    return make_genes(pat)



# sub filehandle_iterator {
#   my $fh = shift;
#   return Iterator { <$fh> };
# }

# my $it = filehandle_iterator(*STDIN);
# while (defined(my $line = NEXTVAL($it))) {
#   # do something with $line
# }
### python already does this by default
for line in file("foo"):
    # do something with line


# LASTNAME:FIRSTNAME:CITY:STATE:OWES
# Adler:David:New York:NY:157.00
# Ashton:Elaine:Boston:MA:0.00
# Dominus:Mark:Philadelphia:PA:0.00
# Orwant:Jon:Cambridge:MA:26.30
# Schwern:Michael:New York:NY:149658.23
# Wall:Larry:Mountain View:CA:-372.14


# package FlatDB;
# my $FIELDSEP = qr/:/;
# sub new {
#   my $class = shift;
#   my $file = shift;
#   open my $fh, "<", $file or return;
#   chomp(my $schema = <$fh>);

#   my @field = split $FIELDSEP, $schema;
#   my %fieldnum = map { uc $field[$_] => $_ } (0..$#field);
#   bless { FH => $fh, FIELDS => \@field, FIELDNUM => \%fieldnum,
#           FIELDSEP => $FIELDSEP } => $class;
# }
class FlatDB(object):
    FIELDSEP = ":"

    def __init__(self, _file):
        self._file = _file
        self.fh = file(self._file)
        self.schema = self.fh.readline().strip()
        self.field = self.schema.split(FlatDB.FIELDSEP)
        self.fieldnum = dict(zip([x.upper() for x in self.field], range(len(self.field))))
  
# # usage: $dbh->query(fieldname, value)
# # returns all records for which (fieldname) matches (value)
# use Fcntl ':seek';
# 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, SEEK_SET;
#   <$fh>;                # discard schema line
#   return Iterator {
#     local $_;
#     while (<$fh>) {
#       chomp;
#       my @fields = split $self->{FIELDSEP}, $_, -1;
#       my $fieldval = $fields[$fieldnum];
#       return $_ 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
        for line in fh:
            fields = line.split(FlatDB.FIELDSEP)
            fieldval = fields[fieldnum]
            if fieldval == value:
                yield line.strip()



# use FlatDB;
# my $dbh = FlatDB->new('db.txt') or die $!;
# my $q = $dbh->query('STATE', 'NY');
# while (my $rec = NEXTVAL($q)) {
#   print $rec;
# }
dbh = FlatDB("db.txt")
q = dbh.query("STATE", "NY")
for rec in q:
    print rec




# my $q = $dbh->callbackquery(sub { my %F=@_; $F{OWES} > 10 });
# my $q = $dbh->callbackquery(sub { my %F=@_; $F{FIRSTNAME} =~ /ˆM/ });

# use Fcntl ':seek';
# sub callbackquery {
#   my $self = shift;
#   my $is_interesting = shift;
#   my $fh = $self->{FH};
#   seek $fh, 0, SEEK_SET;
#   <$fh>;                # discard header line
#   return Iterator {
#     local $_;
#     while (<$fh>) {
#       chomp;
#        my %F;
#        my @fieldnames = @{$self->{FIELDS}};
#        my @fields = split $self->{FIELDSEP};
#        for (0 .. $#fieldnames) {
#          $F{$fieldnames[$_]} = $fields[$_];
#        }
#        return $_ if $is_interesting->(%F);
#     }
#     return;
#   }
# }

q = dbh.callbackquery(lambda F: F["OWES"] > 10)
q = dbh.callbackquery(lambda F: F["FIRSTNAME"].startswith("M") )

def callbackquery(self, is_interesting):
    fh = self.fh
    fh.seek(0)
    fh.readline() # discard schema line
    for line in fh:
        line = line.strip()
        fieldnames = self.field
        fields = line.split(FlatDB.FIELDSEP)
        F = dict(zip(fieldnames, fields))
        if is_interesting(F):
            yield line


# use FlatDB;
# my $dbh = FlatDB->new('db.txt') or die $!;
# my $q1 = $dbh->query('STATE', 'MA');
# my $q2 = $dbh->query('STATE', 'NY');
# for (1..2) {
#   print NEXTVAL($q1), NEXTVAL($q2);
# }
dbh = FlatDB("db.txt")
q1 = dbh.query("STATE","MA")
q2 = dbh.query("STATE","NY")
for x in range(1,3):
    print q1.next(), q2.next()


# # usage: $dbh->query(fieldname, value)
# # returns all records for which (fieldname) matches (value)
# use Fcntl ':seek';
# 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, SEEK_SET;
#   <$fh>;                # discard header line
#   my $position = tell $fh;
#   return Iterator {
#     local $_;
#     seek $fh, $position, SEEK_SET;
#     while (<$fh>) {
#       chomp;
#       $position = tell $fh;
#       my @fields = split $self->{FIELDSEP};
#       my $fieldval = $fields[$fieldnum];
#       return $_ if $fieldval eq $value;
#     }
#     return;
#   };
# }
# # callbackquery with bug fix
# use Fcntl ':seek';
# 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;
#   return Iterator {
#     local $_;
#     seek $fh, $position, SEEK_SET;
#     while (<$fh>) {
#       $position = tell $fh;
#       my %F;
#       my @fieldnames = @{$self->{FIELDS}};
#       my @fields = split $self->{FIELDSEP};
#       for (0 .. $#fieldnames) {
#         $F{$fieldnames[$_]} = $fields[$_];
#       }
#       return $_ if $is_interesting->(%F);

#     }
#     return;
#   };
# }
# 1;

class FlatDB(object):
    FIELDSEP = ":"

    def __init__(self, _file):
        self._file = _file
        self.fh = file(self._file)
        self.schema = self.fh.readline().strip()
        self.field = self.schema.split(FlatDB.FIELDSEP)
        self.fieldnum = dict(zip([x.upper() for x in self.field], range(len(self.field))))

    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
        while 1:
            line = fh.readline()
            if not line:
                break
            position = fh.tell()
            fields = line.split(FlatDB.FIELDSEP)
            fieldval = fields[fieldnum]
            if fieldval == value:
                yield line.strip()
            fh.seek(position)

    def callbackquery(self, is_interesting):
        fh = self.fh
        fh.seek(0)
        fh.readline() # discard schema line
        while 1:
            line = fh.readline()
            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 line
            fh.seek(position)




# package FlatDB::Iterator;
# my $FIELDSEP = qr/\s+/;
# sub new {
#   my $class = shift;
#   my $it = shift;
#   my @field = @_;
#   my %fieldnum = map { uc $field[$_] => $_ } (0..$#field);
#   bless { FH => $it, FIELDS => \@field, FIELDNUM => \%fieldnum,
class IterFlatDB(object):
    FIELDSEP = "\s+"

    def __init__(self, it, *field):
        self.it = it
        self.field = field
        self.fieldnum = dict(zip([x.upper() for x in self.field], range(len(self.field))))



# FlatDB::Iterator->new(
#   $iterator,
#   qw(address rfc931 username datetime tz method page protocol
#      status bytes referrer agent)
# );
IterFlatDB(iterator, 
           "address rfc931 username datetime tz method page protocol status bytes referrer agent".split())





# # 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 $it = $self->{FH};
#   # seek $fh, 0, SEEK_SET;
#   # <$fh>;                # discard header line
#   return Iterator {
#     local $_;
#     while (defined ($_ = NEXTVAL($it))) {
#       my @fields = split $self->{FIELDSEP};
#       my $fieldval = $fields[$fieldnum];
#       return $_ if $fieldval eq $value;
#     }
#     return;
#   };
# }
def query(self, field, value):
    fieldnum = self.fieldnum.get(field.upper())
    if fieldnum == None:
        return

    for record in self.it:
        fields = re.split(IterFlatDB.FIELDSEP, record)
        fieldval = fields[fieldnum]
        if fieldval == value:
            yield record




# my $qit =
#   FlatDB::Iterator->new($it, @FIELDNAMES)->query($field, $value);
qit = IterFlatDB(it, FIELDNAMES).query(field, value)



# sub readbackwards {
#   my $file = shift;
#   open my($fh), "|-", "tac", $file
#     or return;
#   return Iterator { return scalar(<$fh>) };
# }
def readbackwards(_file):
    return os.popen("tac %s" % _file)


# my @fields = qw(address rfc931 username datetime tz method
#                 page protocol status bytes referrer agent);
# my $logfile = readbackwards("/usr/local/apache/logs/access-log")
# my $db = FlatDB::Iterator->new($logfile, @fields);
# my $q = $db->callbackquery(sub {my %F=@_; $F{PAGE}=~ m{/book/$}});
# while (1) {
#   for (1..10) {
#     print NEXTVAL($q);
#   }
#   print "q to quit; CR to continue\n";
#   chomp(my $resp = );
#   last if $resp =~ /q/i;
# }
fields = "address rfc931 username datetime tz method page protocol status bytes referrer agent"
logfile = readbackwards("/var/log/apache2/access.log")
db = IterFlatDB(logfile, fields.split())
q = db.callbackquery(lambda F: re.search("/book/$", f["PAGE" ]))

while 1:
    for line in itertools.islice(q, 10):
        print line
    print "q to quit; CR to continue"
    if raw_input() == 'q':
        break
        





# my $seed = 1;
# sub Rand {
#   $seed = (27*$seed+11111) & 0x7fff;
#   return $seed;
# }
seed = 1
def Rand():
    global seed
    seed = (27*seed+11111) & 0x7fff
    return seed


# sub SRand {
#   $seed = shift;
# }
def SRand(_seed):
    global seed
    seed = _seed


# SRand($$);
SRand(os.getpid())


# use CGI::Push;
# my $seed = shift || $$ ;
# srand($seed);
# open LOG, "> $logfile" or die ... ;
# print LOG "Random seed: $seed\n";
# do_push(...);
if len(sys.argv > 1):
    seed = int(sys.argv[1])
else: 
    seed = os.getpid()
srand(seed)
LOG = open(logfile, "w")
LOG.write("Random seed: " + str(seed))
do_push(...)


# use Foo;
# while (<>) {
#   my $random = Rand();
#   # do something with $random
#   foo();
# }
import Foo
for line in sys.stdin:
    random = Rand()
    # do something with random
    Foo.foo()




# sub make_rand {
#   my $seed = shift || (time & 0x7fff);
#   return Iterator {
#     $seed = (29*$seed+11111) & 0x7fff;
#     return $seed;
#   }
# }
def make_rand(seed=None):
    if seed == None:
        seed = int(time.time()) & 0x7fff
    while 1:
        seed = (29*seed+11111) & 0x7fff
        yield seed



# use Foo;
# my $rng = make_rand();
# while (<>) {
#   my $random = NEXTVAL($rng);
#   # do something with $random
#   foo();
# }
import Foo
rng = make_rand()
for line in sys.stdin:
    random = rng.next()
    # do something with randome
    Foo.foo()



### 4.4 Filters and Transforms

# sub imap {
#   my ($transform, $it) = @_;
#   return Iterator {
#     my $next = NEXTVAL($it);
#     return unless defined $next;
#     return $transform->($next);
#   }
# }

# itertools.imap does this already
def imap(transform, it):
    for next in it:
        yield transform(next)


# my $rng = imap(sub { $_[0] / 37268 }, make_rand());
rng = imap(lambda x: float(x)/37268, make_rand())


# sub imap (&$) {
#   my ($transform, $it) = @_;
#   return Iterator {
#     my $next = NEXTVAL($it);
#     return unless defined $next;
#     return $transform->($next);
#   }
# }

# my $rng = imap { $_[0] / 37268 } make_rand();

# sub imap (&$) {
#   my ($transform, $it) = @_;
#   return Iterator {
#      local $_ = NEXTVAL($it);
#      return unless defined $_;
#      return $transform->();
#   }
# }

# these are irrelevant changes for python



# sub igrep (&$) {
#   my ($is_interesting, $it) = @_;
#   return Iterator {
#     local $_;
#     while (defined ($_ = NEXTVAL($it))) {
#       return $_ if $is_interesting->();
#     }
#     return;
#   }
# }
def igrep(is_interesting, it):
    for x in it:
        if is_interesting(x):
            yield x


# # instead of         my $next_octopus =
# #    interesting_files(\&contains_octopuses, 'uploads', 'downloads' ;
#                                                                    )
# my $next_octopus = igrep { contains_octopuses($_) }
#                        dir_walk('uploads', 'downloads');
# while ($file = NEXTVAL($next_octopus)) {
#   # do something with the file
# }
for _file in igrep(contains_octopuses, dir_walk("uploads", "downloads")):
    # do something with the file



# sub list_iterator {
#   my @items = @_;
#   return Iterator {
#     return shift @items;
#   };
# }
def list_iterator(*args):
    for x in args:
        yield x
# or just
iter(args)



# sub append {
#   my @its = @_;
#   return Iterator {
#     while (@its) {
#     my $val = NEXTVAL($its[0]);
#     return $val if defined $val;
#     shift @its;  # Discard exhausted iterator
#   }
#   return;
# };
def append(its):
    for it in its:
        for x in it:
            yield x
# or just
itertools.chain(*its)



### 4.5 The Semipredicate Problem

# this whole section is irrelevant due to how 
# python uses iterators/generators 
# so i skipped it.  it someone sees something
# in here that deserves a python translation
# let me know

### 4.6 Alternative Interfaces to Iterators


# sub equal_arrays (\@\@) {
#   my ($x, $y) = @_;
#   return unless @$x == @$y;     # arrays are the same length?
#   for my $i (0 .. $#$x) {
#     return unless $x->[$i] eq $y->[$i];   # mismatched elements
#   }
#   return 1;                     # arrays are equal
# }
def equal_arrays(x,y):
    if len(x) != len(y):
        return False
    for i in range(len(x)):
        if x[i] != y[i]:
            return False
    return True
# but this is unnecessary since we can already do
x == y # in place



# sub equal_arrays (\@\@) {
#   my ($x, $y) = @_
#   return unless @$x == @$y;
#   my $xy = each_array(@_ );
#   while (my ($xe, $ye) = NEXTVAL($xy)) {
#     return unless $xe eq $ye;
#   }
#   return 1;
# }
def equal_arrays(x,y):
    if len(x) != len(y):
        return False
    
    xy = each_array(x,y)
    for xe,ye in xy:
        if xe != ye:
            return False
    return True
    

# sub each_array {
#   my @arrays = @_;
#   my $cur_elt = 0;
#   my $max_size = 0;
#   # Get the length of the longest input array
#   for (@arrays) {
#     $max_size = @$_ if @$_ > $max_size;
#   }
#   return Iterator {
#     $cur_elt = 0, return () if $cur_elt >= $max_size;
#     my $i = $cur_elt++;
#     return map $_->[$i], @arrays;
#   };
# }
def each_array(*arrays):
    max_size = max(*[len(ar) for ar in arrays])
    
    def get_item(ar, i):
        if i < len(ar):
            return ar[i]
        return None

    for i in range(max_size):
        yield [get_item(ar, i) for ar in arrays]
# you could also probably do something clever with itertools.izip() 



# my $buttons = each_array(\@labels, \@values);
# ...
# while (my ($label, $value) = NEXTVAL($buttons)) {
#   print HTML qq{ $label
\n};
# }
buttons = each_array(labels, values)
for label, value in buttons:
    HTML.write(" %(label)s
\n" % locals())



# sub each_array {
#   my @arrays    = @_;
#   my $stop_type = ref $arrays[0] ? 'maximum' : shift @arrays;
#   my $stop_size = @{$arrays[0]};
#   my $cur_elt   = 0;
#   # Get the length of the longest (or shortest) input array
#   if ($stop_type eq 'maximum') {
#     for (@arrays) {
#       $stop_size = @$_ if @$_ > $stop_size;
#     }
#   } elsif ($stop_type eq 'minimum') {
#     for (@arrays) {
#       $stop_size = @$_ if @$_ < $stop_size;
#     }
#   } else {
#     croak "each_array: unknown stopping behavior '$stop_type'";
#   }
#   return Iterator {
#     return ()  if $cur_elt >= $stop_size;
#     my $i = $cur_elt++;
#     return map $_->[$i], @arrays;
#   };
# }
def each_array(arrays, stop_type="maximum"):
    assert stop_type in ("minimum", "maximum")
    
    if stop_type == "minimum":
        stop_size = min(*[len(ar) for ar in arrays])
    else:
        stop_size = max(*[len(ar) for ar in arrays])
    
    def get_item(ar, i):
        if i < len(ar):
            return ar[i]
        return None

    for i in range(stop_size):
        yield [get_item(ar, i) for ar in arrays]



# sub eachlike (&$) {
#   my ($transform, $it) = @_;
#   return Iterator {
#     local $_ = NEXTVAL($it);
#     return unless defined $_;
#     my $value = $transform->();
#     return wantarray ? ($_, $value) : $value;
#   }
# }
# not sure if wantarray really maps to python
# style



# package CIA;
# sub TIESCALAR {
#   my $package = shift;
#   my $self = {};
#   bless $self => $package;
# }
# sub STORE { }
# sub FETCH { "<>" }

# tie $secret, 'CIA';

# $secret = 'atomic ray';

# print "The secret weapon is '$secret'.\n"

# the secret weapon is '<>'.

# I can't think of any reasonable way to do
# this in python.  In part it seems like something
# you could handle with descriptor and in part
# with "with".  I'm just going to ignore TIE-ing
# for now


### 4.7 An Extended Example: Web Spiders


# use HTML::LinkExtor;
# use LWP::Simple;
# sub traverse {
#   my @queue = @_;
#   my %seen;
#   return Iterator {
#     while (@queue) {
#       my $url = shift @queue;
#       $url =~ s/#.*$//;
#       next if $seen{$url}++;
#       my ($content_type) = head($url);
#       if ($content_type =~ m{ˆtext/html\b}) {
#         my $html = get($url);
#         push @queue, get_links($url, $html);
#       }
#       return $url;
#     }
#     return;     # exhausted
#   }
# }
import urllib2    
def traverse(_queue):
    queue = _queue[:]
    seen = {}
    while queue:
        url = queue.pop(0)
        url = url.split("#")[0]
        seen.setdefault(url,0)
        if seen[url] > 0:
            continue
        seen[url] += 1
        try:
            page = urllib2.urlopen(url)
        except urllib2.HTTPError:
            print "http error for:", url
            continue
        content_type = page.headers.getheader("content-type")
        if re.search(r"^text/html\b", content_type):
            html = page.read()
            queue.extend(get_links(url, html))
        yield url
            

# sub get_links {
#   my ($base, $html) = @_;
#   my @links;
#   my $more_links = sub {
#     my ($tag, %attrs) = @_;
#     push @links, values %attrs;
#   };
#   HTML::LinkExtor->new($more_links, $base)->parse($html);
#   return @links;
# }
# Off the top of my head I don't know a python library
# that provides this exact functionality, so we 
# fake it.
def get_links(base, html):
    links = []

    parsed = urlparse.urlparse(base)

    for anchor in BeautifulSoup.BeautifulSoup(html)('a'):
        link = anchor.get("href")
        if not link:
            continue

        if link.startswith("./"):
            link = link[2:]

        if link.startswith("http"):
            links.append(link)
        elif link.startswith("/"):
            links.append(parsed[0]+"://"+parsed[1]+link)
        else:
            links.append(parsed[0]+"://"+parsed[1]+parsed[2]+link)

    return links



# # Version with 'interesting links' callback
# sub traverse {
#   my $interesting_links = sub { @_ };
#   $interesting_links = shift if ref $_[0] eq 'CODE';
#   ...
#         push @queue, $interesting_links->(get_links($url, $html));
#   ...
# }
def traverse(queue, interesting_links=None):
    ...
    queue.extend(interesting_links(get_links(url, html)))
    ...



# my $top = 'http://perl.plover.com/';
# my $interesting = sub { grep /ˆ\Q$top/o, @_ };
# my $urls = traverse($interesting, $top);
top = "http://perl.plover.com"
interesting = lambda x: top in x
urls = traverse(interesting, top)



# use File::Basename;
# while (my $url = NEXTVAL($urls)) {
#   my $file = $url;
#   $file =~ s/ˆ\Q$top//o;
#   my $dir = dirname($file);
#   system('mkdir', '-p', $dir) == 0 or next;
#   open F, ">", $file or next;
#   print F get($url);
# }
for url in urls:
    _file = url.replace(url, "")
    _dir = os.path.dirname(_file)
    if os.system("mkdir -p %s" % _dir) != 0:
        continue
    try:
        F = open(_file, "w")
    else:
        continue
    F.write(urllib2.urlopen(url).read())




# while (my $url = NEXTVAL($urls)) {
#   print "Bad link to: $url" unless head($url);
# }
for url in urls:
    try:
        urllib2.urlopen(url)
    except:
        print "Bad link to: %s" % url



# sub traverse {
#       ...
#       my (%head, $html);
#       @head{qw(TYPE LENGTH LAST_MODIFIED EXPIRES SERVER)} = head($url);
#       if ($head{TYPE} = ̃ m{ˆtext/html\b}) {
#         $html = get($url);
#         push @queue, $interesting_links->(get_links($url,$html));
#       }
#       return wantarray ? ($url, \%head, $html) : $url;
#       ...
# }
# I don't think this is a straight forward way to duplicate
# "wantarray" type functionality in python.  In any case
# it would be more uniform to *always* retrn the tuple


# sub traverse {
#   my $interesting_links = sub { shift; @_ };
#   $interesting_links = shift if ref $_[0] eq 'CODE';
#   my @queue = map [$_, 'supplied by user'], @_;
#   my %seen;
#   return Iterator {
#     while (@queue) {
#       my ($url, $referrer) = @{shift @queue};
#       $url =~ s/#.*$//;
#       next if $seen{$url}++;
#       my (%head, $html);
#       @head{qw(TYPE LENGTH LAST_MODIFIED EXPIRES SERVER)} = head($url);
#       if ($head{TYPE} =~ m{ˆtext/html\b}) {
#         my $html = get($url);
#         push @queue,
#           map [$_, $url],
#             $interesting_links->($url, get_links($url, $html));
#       }
#       return wantarray ? ($url, \%head, $referrer, $html) : $url;
#     }
#     return;     #exhausted
#   }
# }
import urllib2    
def traverse(queue, interesting_links=None):
    queue = [(x, "supplied by user") for x in queue]

    if interesting_links == None:
        def interesting_links(this_url, other_urls):
            return other_urls

    seen = {}

    while queue:
        url, referrer = queue.pop(0)
        url = url.split("#")[0]
        seen.setdefault(url,0)
        if seen[url] > 0:
            continue
        seen[url] += 1
        try:
            page = urllib2.urlopen(url)
        except urllib2.HTTPError:
            print "http error for:", url
            yield url, None, referrer, None
            continue
        content_type = page.headers.getheader("content-type")
        if re.search(r"^text/html\b", content_type):
            html = page.read()
            queue.extend([(x, url) for x in interesting_links(url, get_links(url, html))])
        yield url, page.headers, referrer, html
            


# my $top = 'http://perl.plover.com/'
# my $interesting = sub { shift; grep /ˆ\Q$top/o, @_ };
# my $urls = traverse($interesting, $top);
# while (my ($url, $head, $referrer) = NEXTVAL($urls)) {
#   next if $head->{TYPE};
#   print "Page '$referrer' has a bad link to '$url'\n";
# }
top = "http://perl.plover.com"
interesting = (lambda x,y: [_y for _y in y if top in _y])
urls = traverse([top], interesting)
for url, head, referrer, html in urls:
    if not html:
        continue
    print "Page '%s' has a bad link to '%s'" % (referrer, url)



# my $top = 'http://perl.plover.com/';
# my $interesting = sub { shift; grep /ˆ\Q$top/o, @_ };
# my $urls = igrep_l { not $_[1]{TYPE} } traverse($interesting, $top);
# while (my ($url, $head, $referrer) = NEXTVAL($urls)) {
#   print "Page '$referrer' has a bad link to '$url'\n";
# }
top = "http://perl.plover.com"
interesting = (lambda x,y: [_y for _y in y if top in _y])
urls = igrep_l((lambda url, head, referrer, html: not html), traverse([top], interesting))
for url, head, referrer, html in urls:
    if not html:
        continue
    print "Page '%s' has a bad link to '%s'" % (referrer, url)




# sub igrep_l (&$) {
#   my ($is_interesting, $it) = @_;
#   return Iterator {
#     while (my @vals = NEXTVAL($it)) {
#       return @vals if $is_interesting->(@vals);
#     }
#     return;
#   }
# }
def igrep_l(is_interesting, it):
    for vals in it:
        if is_interesting(*vals):
            yield vals
        

# while (my ($url, $head, $referrer) = NEXTVAL($urls)) {
#   print "Page '$referrer' has a bad link to '$url'\n";
#   print "Edit now? ";
#   my $resp = <>;
#   if ($resp =~ /ˆy/i) {
#     system $ENV{EDITOR}, url_to_filename($referrer);
#   } elsif ($resp =~ /∧ q/i) {
#     last;
#   }
# }
for url, head, referrer, html in urls:
    print "Page '%(referrer)s' has a bad line to '%(url)s'" % locals()
    print "Edit now?"
    resp = raw_input():
    if resp == 'y':
        os.system(os.environ["EDITOR"] + " " + url_to_filename(referrer))
    elif resp == 'q':
        break





# sub traverse {
#   my $interesting_link;
#   $interesting_link = shift if ref $_[0] eq 'CODE';
#   my @queue = map [$_, 'supplied by user'], @_;
#   my %seen;
#   my $q_it = igrep { ! $seen{$_->[0]}++ }
#                imap { $_->[0] =~ s/#.*$//; $_}
#                  Iterator { return shift(@queue) };
#   if ($interesting_link) {
#     $q_it = igrep {$interesting_link->(@$_)} $q_it;
#   }
#   return imap {
#       my ($url, $referrer) = @$_;
#       my (%head, $html);
#       @head{qw(TYPE LENGTH LAST_MODIFIED EXPIRES SERVER)} = head($url);
#       if ($head{TYPE} =~ m{ˆtext/html\b}) {
#         $html = get($url);
#         push @queue,
#           map [$_, $url],
#             get_links($url, $html);
#       }
#       return wantarray ? ($url, \%head, $referrer, $html) : $url;
#   } $q_it;
# }
# this is not an exact match but is close enough for our
# purposes.  what ever that purpose could be.
def traverse(queue, interesting_link=None):
    seen = {}
    queue = [(x, "supplied by user") for x in queue]

    def iterate_queue():
        while queue:
            yield queue.pop(0)

    def not_seen_yet(url):
        seen.setdefault(url,0)
        seen[url] += 1
        if seen[url] > 1:
            return False
        return True

    q_it = iterate_queue()
    q_it = ((url[0].split("#")[0], url[1]) for url in q_it)
    q_it = (url for url in q_it if not_seen_yet(url[0]))

    if interesting_link != None:
        q_it = igrep(interesting_link, q_it)

    def process_url((url, referrer)): 
        print "process_url:", url, referrer
        try:
            page = urllib2.urlopen(url)
        except urllib2.HTTPError:
            print "http error for:", url
            return url, None, referrer, None

        content_type = page.headers.getheader("content-type")
        if re.search(r"^text/html\b", content_type):
            html = page.read()
            queue.extend([(x, url) for x in get_links(url, html)])
        return url, page.headers, referrer, html
            
    return imap(process_url, q_it)
        


# sub make_robot_filter {
#   my $agent = shift;
#   my %seen_site;
#   my $rules = WWW::RobotRules->new($agent);
#   return sub {
#     my $url = url(shift());
#     return 1 unless $url->scheme eq 'http';
#     unless ($seen_site{$url->netloc}++) {
#       my $robots = $url->clone;
#       $robots->path('/robots.txt');
#       $robots->frag(undef);
#       $rules->parse($robots, get($robots));
#     }
#     $rules->allowed($url)
#   };
# }
def make_robot_filter(agent):
    seen_site = {}

    rules = {} #robotparser.RobotFileParser()

    def _filter(url):
        u = urlparse.urlparse(url) 
        if u.scheme != "http":
            return True

        if u.netloc not in rules:
            rules[u.netloc] = robotparser.RobotFileParser()
            rules[u.netloc].set_url(u.scheme+"://"+u.netloc+"/robots.txt")
            rules[u.netloc].read()

        return rules[u.netloc].can_fetch(agent, url)

    return _filter

Smalltalk for a Year - Status Report 1

As I've mentioned, I'm working on smalltalk as my learn a language a year language. So where am I after a month?

My initial idea was to ease into things using etoys as a gateway drug. But after a week or so I decided that, while it's oddly fascinating and kinda fun, it's not really smalltalk per se. So while I'll probably dabble a little bit, I've decided that I need to work with more mainstream smalltalk learning.

In that vein, I'm reading Squeak By Example and am about 1/3 of the way through. It's a very nice no nonsense introduction to smalltalk the language and squeak the environment.

After that I'm thinking I'll either look at the Squeak Development Example for Squeak 3.9 tutorial or work on a Seaside Tutorial. I'm sort of leaning towards the latter, but I'm sure I'll eventually do both, but for some reason I'm more drawn to the web development aspect of things these days. And how cool are you if you use continuations? (Pretty cool, I'd wager)

I have to confess that already in the first month I've had to fight off the the urge just to ditch this project. I'm a little embarrassed to admit that I'm not immediately overwhelmed with a love for smalltalk. And logically that's not really so unexpected. Learning a language is *hard*. And in the initial phases you basically see everything with your blub colored glasses and in the new language you see blub features but they are distorted and some blub features are completely missing or almost too awkward to be usable. You may dimly see some features that are interesting but they are obscured by an alien syntax and semantics.

And that's where I am now with smalltalk. There are somethings that seem interesting (elegant metaclass programming features, turtles all the way down, highly integrated development environment, etc) but I've never used these features "in anger". So at best they just seem kinda interesting. On the other hand the lack of modules feels archaic, the default user interface look-and-feel seems oddly clunky, the lack of list access syntax (e.g. foo[3:5]) makes me sad, and I miss emacs.

So I'm in the no man's land right now. I see things faintly off in the distance that seem interesting but everything in my reach is (seemingly) inferior and awkward.

I guess it helps me to lay it out like this. I'm surprised (even though I should know myself better by now) at how easily I could just abandon things and jump over to haskell for a while. Oooh, and then lisp is kinda cool, and then, oh yeah, I heard javascript is the NBL, I better look at that for a few minutes today.

I wonder if it's harder to fall in love with another language when your day job is python. But I'm a little afraid that python has become my blub and I must fight the tendencies of a blub programmer to be blind to non-blubby goodness.

Ok, enough dithering. I'm putting my blinders on again and focusing on smalltalk. I actually hope (and somewhat expect) that I will get over the oddness hurdle and really love smalltalk.

But it's not love at first sight. It's more like cautious optimism at first sight.