OK, it took me about a year and a half. And they weren't pretty. But I finished it.
Sort of anti-climactic somehow after all this time. But kinda cool to have gotten there.
2 questions:
- do I bother maintaining this level? (once a week refresher?)
- what should I work on next? (chin ups probably)
Wednesday, November 4, 2009
Thursday, October 1, 2009
100 pushups milestone - 80
OK, so I'm 80% of the way there (100 pushups).
Just checked my records and I've been doing this for 1 year and 3 months. That would be funny if it weren't so tragic. How can it be taking so long? Oh well, keep on trucking.
I better get a damn spiffy prize when I finish this.
Just checked my records and I've been doing this for 1 year and 3 months. That would be funny if it weren't so tragic. How can it be taking so long? Oh well, keep on trucking.
I better get a damn spiffy prize when I finish this.
Monday, July 20, 2009
Git 101 tutorial
http://en.oreilly.com/oscon2009/public/schedule/detail/7953
This was a great tutorial. It was as good of a brain dump as you could hope for in a half day session. A good mix of theory and hands on examples. This got me excited to get back to the office and push to get this adopted as soon as possible. (It's already "in the air". It just needs a nudge to get us converted over to it)
Well done!
This was a great tutorial. It was as good of a brain dump as you could hope for in a half day session. A good mix of theory and hands on examples. This got me excited to get back to the office and push to get this adopted as soon as possible. (It's already "in the air". It just needs a nudge to get us converted over to it)
Well done!
Still Looking for the Swan in Squeak's Ugly Duckling
http://en.oreilly.com/oscon2009/public/schedule/detail/8158
So this is not exactly the tutorial I was expecting. But it's also quite possible my expectations were a little skewed.
Unfortunately Avi Bryant wasn't able to make the conference so Randal Schwartz stepped in. And no disrespect to Randal but if I had known this substitution had occurred, I would have picked a different tutorial simply because I had seen his presentation last year and was interested in a different perspective.
Partly I feel like I was expecting too much from this tutorial and part of me feels like I got something different than described.
When I read the description in the link above I don't get the sense of a remedial no-background talk. But like I said Randal took this over at the last minute for Avi so I have no complaints with him.
I think I focused a little too much on the last paragraph of the description whereas I should realize that that is what usually gets covered least at the end (or not at all):
"But we’ll also address the practical concerns that keep people away from Squeak: how to get rid of the pastel colors and bitmapped fonts so that you can stand to look at it; how to get your source code into version control so you can collaborate with others; how to find documentation and examples; how to integrate with the OS and with C libraries; how to manage deployment."
I am relatively comfortable with the ideas of smalltalk and reading it's code, just not completely sold on the language and environment. So what I was mostly looking for was the addressing of "practical concerns that keep people away from Squeak":
But really it was a well done tutorial, just not what I was expecting. But I think
this was just a combination of over ambitious expectations and last minute teacher changes.
Here is the smalltalk course I would love to have:
So this is not exactly the tutorial I was expecting. But it's also quite possible my expectations were a little skewed.
Unfortunately Avi Bryant wasn't able to make the conference so Randal Schwartz stepped in. And no disrespect to Randal but if I had known this substitution had occurred, I would have picked a different tutorial simply because I had seen his presentation last year and was interested in a different perspective.
Partly I feel like I was expecting too much from this tutorial and part of me feels like I got something different than described.
When I read the description in the link above I don't get the sense of a remedial no-background talk. But like I said Randal took this over at the last minute for Avi so I have no complaints with him.
I think I focused a little too much on the last paragraph of the description whereas I should realize that that is what usually gets covered least at the end (or not at all):
"But we’ll also address the practical concerns that keep people away from Squeak: how to get rid of the pastel colors and bitmapped fonts so that you can stand to look at it; how to get your source code into version control so you can collaborate with others; how to find documentation and examples; how to integrate with the OS and with C libraries; how to manage deployment."
I am relatively comfortable with the ideas of smalltalk and reading it's code, just not completely sold on the language and environment. So what I was mostly looking for was the addressing of "practical concerns that keep people away from Squeak":
- how to get rid of the pastel colors and bitmapped fonts so that you can stand to look at it;
- just a mention that this is possible. I would have really liked a detailed course on how to customize the ugly duckling away
- how to get your source code into version control so you can collaborate with others;
- there was a pretty good description of version control and options for doing this
- how to find documentation and examples;
- this was well done and is a core part of the wonder of smalltalk
- how to integrate with the OS and with C libraries;
- I don't think there was any mention of this (unless I really zoned out)
- how to manage deployment.
- I don't recall anything like this
But really it was a well done tutorial, just not what I was expecting. But I think
this was just a combination of over ambitious expectations and last minute teacher changes.
Here is the smalltalk course I would love to have:
- develop a real world useful app while I watch. e.g. take some unix sysadmin tasks and automate them and create a reporting system etc. ie, show me that squeak can kick python's ass at something where python excels
- show me how to recover when my image crashes or I've accidentally broken things
- show me how to customize my way from the default image to one of the premade developer images. then explain to me why these aren't already the defaults
- show me how to convince my bosses that I should do a trial project in smalltalk. :)
Sunday, July 12, 2009
Happy Birthday - My mission to get to 100 pushups is now one year old!
So after a year of the 100 pushup plan, where am I? 75.
Now if you are familiar with the 6 weeks to 100 pushup plan you might detect a slight disconnect between the plan and my success. Just an eentsy bit off...
On the one hand: holy crap I can do 75 pushups. And also: wow, look at the determination and will power.
On the other hand: what is wrong with me? Why can't I finish this sucker? And: why am I wasting my time, focus on this?
So there you go. I'm part super man and part loser. I knew that before I started.
OK. If I haven't gotten to 100 before another year passes I seriously have to reevaluate this whole thing.
(Any tips from the pros out there how to get the last 25?)
Now if you are familiar with the 6 weeks to 100 pushup plan you might detect a slight disconnect between the plan and my success. Just an eentsy bit off...
On the one hand: holy crap I can do 75 pushups. And also: wow, look at the determination and will power.
On the other hand: what is wrong with me? Why can't I finish this sucker? And: why am I wasting my time, focus on this?
So there you go. I'm part super man and part loser. I knew that before I started.
OK. If I haven't gotten to 100 before another year passes I seriously have to reevaluate this whole thing.
(Any tips from the pros out there how to get the last 25?)
Friday, May 22, 2009
One New Language a Year: (was) Smalltalk
OK, so I had this crazy plan of doing the "one new language a year" thing. I really like the idea of this. Get out of your comfort zone, prevent settling for a "blub" language, learn new techniques. So I choose smalltalk and thought this would fit the bill. I was really excited to work with turtles all the way down. "Real" object oriented programming. Etc.
And here it is May and I'm just not doing so well. Best laid schemes and all that. In fact I've decided to abandon it for, get this, emacslisp. Only time will tell if this was a good decision or just my normal fickleness.
Part of this decision is just pure pragmatism. My learning windows for this plan are of necessity going to be early in the morning before breakfast or late at night after the family's in bed. I've tried both slots for a month or more and both put me to sleep. You can't learn much while you are asleep so no matter the plan/desire I have to be doing something that engages my attention.
OK, I said it. Smalltalk puts me to sleep. And I feel bad for saying it. I really want to be the guy who likes smalltalk and wields it with authority. But there is just so much I don't enjoy about it and while I'm sure there are some cool things to learn from it, it just doesn't entice me. At least not at 6 am. We'll see if emacslisp can do better.
Smalltalk is like this quirky, fairly attractive girl who on paper seems like a good match for you ("Wow, you like continuations? Me too!") but for whatever reason just doesn't ignite that spark. In addition, she has lots of eccentricities that if she was "the one" would be charming/braggable. But if you are indifferent to her they just come off as irritations/oddities.
I also wonder if watching this video put the final nail in the coffin: "what killed smalltalk" (also). Just hearing about smalltalk being dead (I'm not defending this thesis) sort of activated my pragmatism module which some how grabbed the reins of my brain and executed veto power.
The thing that bugs me is that I don't see myself as a practical dude. In fact, I find the thought of being practical a little bit horrifying. I'm always doing things just because they are interesting, not because I'm trying to be more efficient, etc. And here I am making a practical decision. Ugg.
I wonder what the rules are about abandoning your "one new language a year" language halfway through the year. Is there some governing body I should contact? Do I need to ask permission first?
For what it's worth, smalltalk is not permanently abandoned; it is just pushed down on the list. If I stick with the language a year program I will almost certainly head back to smalltalk at some point. We'll see what happens next time around.
Does working with python as your primary language makes it harder to learn new languages? Every language that I've learned so far has been a productivity boost or has some other sweetener (my language history: basic -> pascal -> c -> c++ -> java -> perl -> python). emacslisp is a booster just because it is the only option in emacs (I will be looking into pymacs though). haskell looks like it might be a next step in the awesomeness hierarchy. But smalltalk doesn't *seem* (in my limited experience) like a significantly more productive tool past python. smalltalk feels like a language from which many great ideas have been lifted. And the ones that haven't yet are either in the process of being stolen (pypy - turtles all the way down) or aren't worth the trouble (image files, etc).
What's funny is that I've talked to others who have had the same initial fascination with smalltalk and then given up on it due various pain points or lack or practicality.
I guess in the end part of it is that smalltalk doesn't seem to solve a problem that I'm having in a vastly superior way and (surprisingly to me) isn't more fun. On paper it seems it should be. And I actually feel guilty for not liking smalltalk. I've failed the gods of language geekdom.
Any way, on to the new hotness of, er, emacslisp.
So why emacslisp? At the start of the year I was trying to decide between smalltalk and haskell. I was in sort of an object-y mood at the time so smalltalk won out. I'm not defaulting to haskell at this time primarily because I want to give it the full year (and it just feels like it has to be a calendar year starting in January). emacslisp works because I know it will be useful. It will make a real difference to my productivity immediately (I mostly live in emacs) and I like lispy languages (though I've only dabbled and/or used them for a semester in an ai class). *And* I don't feel too bad about giving it only half a year.
My goal with emasclisp is to get to the point where I can program in it as easily as I think (how it is for python with me now). I want to be able to whip out useful helper functions like this and be able to write my own modes and/or hack on existing emacs packages.
Any way, smalltalk, it's not you it's me. When I get my head right maybe we'll meet again and give it another shot. I wish you all the best. (but please don't call - I'm not sure emacslisp would understand us "just being friends").
Wednesday, April 8, 2009
Higher Order Perl (Python Style) : Chapter 7 - Higher Order Functions And Currying
TOC
### 7.1 Currying
# @tagged_texts = walk_html($tree, sub { ['MAYBE', $_[0]] },
# \&promote_if_h1tag);
# sub promote_if_h1tag {
# my $element = shift;
# if ($element->{_tag} eq 'h1') {
# return ['KEEPER', join '', map {$_->[1]} @_];
# } else {
# return @_;
# }
# }
# sub extract_headers {
# my $tree = shift;
# my @tagged_texts = walk_html($tree, sub { ['MAYBE', $_[0]] },
# \&promote_if_h1tag);
# my @keepers = grep { $_->[0] eq 'KEEPER' } @tagged_texts;
# my @keeper_text = map { $_->[1] } @keepers;
# my $header_text = join '', @keeper_text;
# return $header_text;
# }
def extender(accum, item):
accum.extend(item)
tagged_texts = walk_html(tree, lambda x: [["MAYBE", x]],
promote_if_h1tag,
extender)
def promote_if_h1tag(element, results):
if element["_tag"] == "h1":
return [["KEEPER", "".join([ _x[1] for _x in results])]]
else:
return results
def extract_headers(tree):
tagged_texts = walk_html(tree, lambda x: [["MAYBE", x]],
promote_if_h1tag,
extender)
keepers = [x for x in tagged_texts if x[0] == "KEEPER"]
keeper_text = [x[1] for x in keepers]
header_text = "".join(keeper_text)
return header_text
# sub promote_if {
# my $is_interesting = shift;
# my $element = shift;
# if ($is_interesting->($element->{_tag}) {
# return ['keeper', join '', map {$_->[1]} @_];
# } else {
# return @_;
# }
# }
# my @tagged_texts = walk_html($tree,
# sub { ['maybe', $_[0]] },
# sub { promote_if(
# sub { $_[0] eq 'h1' },
# $_[0])
# });
def promote_if(is_interesting, element, results):
if is_interesting(element["_tag"]):
return [["KEEPER", "".join([ _x[1] for _x in results])]]
else:
return results
tagged_texts = walk_html(tree, lambda x: [["MAYBE", x]],
lambda y,z: (promote_if((lambda _y: _y == "h1"), y,z)),
extender)
# sub promote_if {
# my $is_interesting = shift;
# return sub {
# my $element = shift;
# if ($is_interesting->($element->{_tag}) {
# return ['keeper', join '', map {$_->[1]} @_];
# } else {
# return @_;
# }
# }
# }
def promote_if(is_interesting):
def _foo(element, results):
if is_interesting(element["_tag"]):
return [["KEEPER", "".join([ _x[1] for _x in results])]]
else:
return results
return _foo
# my @tagged_texts = walk_html($tree,
# sub { ['maybe', $_[0]] },
# promote_if(sub { $_[0] eq 'h1' }),
# );
tagged_texts = walk_html(tree, lambda x: [["MAYBE", x]],
promote_if(lambda y: y == "h1"),
extender)
# sub add2 {
# my ($s, $t) = @_;
# return unless $s && $t;
# node(head($s) + head($t),
# promise { add2(tail($s), tail($t)) });
# }
# sub mul2 {
# my ($s, $t) = @_;
# return unless $s && $t;
# node(head($s) * head($t),
# promise { mul2(tail($s), tail($t)) });
# }
def add2(s,t):
if not (t and s):
return None
return node(head(s) + head(t),
promise(lambda: add2(tail(s),tail(t))))
def mul2(s,t):
if not (s and t):
return None
return node(head(s)*head(t),
promise(lambda: mul2(tail(s),tail(t))))
# sub combine2 {
# my ($s, $t, $op) = @_;
# return unless $s && $t;
# node($op->(head($s), head($t)),
# promise { combine2(tail($s), tail($t), $op) });
# }
def combine2(s,t,op):
if not (s and t):
return None
return node(op(head(s),head(t)),
promise(lambda: combine2(tail(s),tail(t), op)))
# sub add2 { combine2(@_, sub { $_[0] + $_[1] }) }
# sub mul2 { combine2(@_, sub { $_[0] * $_[1] }) }
def add2(s,t):
return combine2(s, t, lambda _s, _t: _s + _t)
def mul2(s,t):
return combine2(s, t, lambda _s, _t: _s * _t)
# sub combine2 {
# my $op = shift;
# return sub {
# my ($s, $t) = @_;
# return unless $s && $t;
# node($op->(head($s), head($t)),
# promise { combine2($op)->(tail($s), tail($t))});
# };
# }
def combine2(op):
def _foo(s, t):
if not (s and t):
return None
return node(op(head(s),head(t)),
promise(lambda: combine2(op(tail(s), tail(t)))))
return _foo
# $add2 = combine2(sub { $_[0] + $_[1] });
# $mul2 = combine2(sub { $_[0] * $_[1] });
add2 = combine2(lambda x,y: x+y)
mul2 = combine2(lambda x,y: x*y)
# my $catstrs = combine2(sub { "$_[0]$_[1]" })->($s, $t);
catstrs = combine2(lambda x,y: "%s%s" % (x,y))(s,t)
# sub scale {
# my $s = shift;
# return sub {
# my $c = shift;
# return if $c == 0;
# transform { $_[0] * $c } $s;
# }
# }
def scale(s):
def _foo(c):
if c == 0:
return None
return transform(lambda x: x*c, s)
return _foo
# sub scale {
# my $c = shift;
# return sub {
# my $s = shift;
# transform { $_[0] * $c } $s;
# }
# }
def scale(c):
def _foo(s):
return transform(lambda x: x*c, s)
return _foo
# sub slope {
# my ($f, $x) = @_;
# my $e = 0.00000095367431640625;
# ($f->($x+$e) - $f->($x-$e)) / (2*$e);
# }
def slope(f, x):
e = 0.00000095367431640625
return (f(x+e) - f(x-e)) / (2*e)
# sub slope {
# my $f = shift;
# my $e = 0.00000095367431640625;
# return sub {
# my $x = shift;
# ($f->($x+$e) - $f->($x-$e)) / (2*$e);
# };
# }
def slope(f):
e = 0.00000095367431640625
def _foo(x):
return (f(x+e) - f(x-e)) / (2*e)
return _foo
# sub slope {
# my $f = shift;
# my $e = 0.00000095367431640625;
# my $d = sub {
# my ($x) = shift;
# ($f->($x+$e) - $f->($x-$e)) / (2*$e);
# };
# return @_ ? $d->(shift) : $d;
# }
def slope(f, _x=None):
e = 0.00000095367431640625
def d(x):
return (f(x+e) - f(x-e)) / (2*e)
return d(_x) if _x != None else d
# sub iterate_function {
# my ($f, $x) = @_;
# my $s;
# $s = node($x, promise { &transform($f, $s) });
# }
def iterate_function(f, x):
s = node(x, promise(lambda: transform(f, s)))
return s
# sub iterate_function {
# my $f = shift;
# return sub {
# my $x = shift;
# my $s;
# $s = node($x, promise { &transform($f, $s) });
# };
# }
def iterate_function(f):
def foo(x):
s = node(x, promise(lambda: transform(f, s)))
return s
return foo
# *upfrom = iterate_function(sub { $_[0] + 1 });
upfrom = iterate_function(lambda x: x + 1)
# *pow2_from = iterate_function(sub { $_[0] * 2 });
pow2_from = iterate_function(lambda x: x * 2)
# sub combine2 {
# my $op = shift;
# return sub {
# my ($s, $t) = @_;
# return unless $s && $t;
# node($op->(head($s), head($t)),
# promise { combine2($op)->(tail($s), tail($t)) });
# };
# }
def combine2(op):
def _foo(s, t):
if not (s and t):
return None
return node(op(head(s),head(t)),
promise(lambda: combine2(op(tail(s), tail(t)))))
return _foo
# sub combine2 {
# my $op = shift;
# my $r;
# $r = sub {
# my ($s, $t) = @_;
# return unless $s && $t;
# node($op->(head($s), head($t)),
# promise { $r->(tail($s), tail($t)) });
# };
# }
def combine2(op):
def r(s,t):
if not (s and t):
return None
return node(op(head(s),head(t)),
promise(lambda: r(tail(s),tail(t))))
return r
### 7.2 Common Higher-Order Functions
# map { $_ * 2 } (1..5); # returns 2, 4, 6, 8, 10
# grep { $_ % 2 == 0 } (1..10); # returns 2, 4, 6, 8, 10
## while map exists in python the more usual idiom
## is to use list comprehensions/iterators
[x*2 for x in range(1,6)]
[x for x in range(1,11) if x % 2 == 0 ]
# sub cmap (&) {
# my $f = shift;
# my $r = sub {
# my @result;
# for (@_) {
# push @result, $f->($_);
# }
# @result;
# };
# return $r;
# }
# sub cgrep (&) {
# my $f = shift;
# my $r = sub {
# my @result;
# for (@_ ) {
# push @result, $_ if $f->($_ );
# }
# @result;
# };
# return $r;
# }
## skipping the more obvious generator solution
def cmap(f):
def r(items):
result = []
for i in items:
result.append(f(i))
return result
return r
def cgrep(f):
def r(items):
result = []
for i in items:
if f(i):
result.append(i)
return result
return r
# $double = cmap { $_ * 2 };
# $find_slashdot = cgrep { $_->{referer} =~ /slashdot/i };
double = cmap(lambda x: x*2)
find_slashdot = cgrep(lambda x: "slashdot" in x["referer"].lower())
# sub cmap (&;@) {
# my $f = shift;
# my $r = sub {
# my @result;
# for (@_) {
# push @result, $f->($_);
# }
# @result;
# };
# return @_ ? $r->(@_) : $r;
# }
def cmap(f, lst=[]):
def r(_lst):
result = []
for item in _lst:
result.append(f(item))
return result
return r(lst) if lst != None else r
# @doubles = cmap { $_ * 2 } (1..5);
# @evens = cgrep { $_ % 2 == 0 } (1..10);
doubles = cmap(lambda x: x*2, range(1,6))
evens = cgrep(lambda x: x % 2 == 0, range(1,11))
# sub some_curried_function {
# my $first_arg = shift;
# my $r = sub {
# ...
# };
# return @_ ? $r->(@_) : $r;
# }
def some_curried_function(first_arg, lst=None):
def r(...):
...
return r(lst) if lst != None else r
# package Curry;
# use base 'Exporter';
# @EXPORT = ('curry');
# @EXPORT_OK = qw(curry_listfunc curry_n);
# sub curry {
# my $f = shift;
# return sub {
# my $first_arg = shift;
# my $r = sub { $f->($first_arg, @_) };
# return @_ ? $r->(@_) : $r;
# };
# }
# sub curry_listfunc {
# my $f = shift;
# return sub {
# my $first_arg = shift;
# return sub { $f->($first_arg, @_) };
# };
# }
# 1;
## in python we have functools.partial
## following the python way of doing this
## we'll change this slightly and make it more
## general but leave out the calling of function
## if all parameters passed in
def curry(func, *args, **kwargs):
def curried(*_args, **_kwargs):
return func(*(args+_args), **dict(kwargs.items() + _kwargs.items()))
return curried
# sub imap (&$) {
# my ($transform, $it) = @_;
# return sub {
# my $next = NEXTVAL($it);
# return unless defined $next;
# return $transform->($next);
# }
# }
def imap(transform, it):
for next in it:
yield transform(next)
# my $doubles_iterator = imap { $_[0] * 2 } $it;
doubles_iterator = imap(lambda x: x*2, it)
# my $doubles_a = imap { $_[0] * 2 } $it_a;
# my $doubles_b = imap { $_[0] * 2 } $it_b;
# my $doubles_c = imap { $_[0] * 2 } $it_c;
doubles_a = imap(lambda x: x*2, it_a)
doubles_b = imap(lambda x: x*2, it_b)
doubles_c = imap(lambda x: x*2, it_c)
# my $doubles_a = double $it_a;
# my $doubles_b = double $it_b;
# my $doubles_c = double $it_c;
doubles_a = double(it_a)
doubles_b = double(it_b)
doubles_c = double(it_c)
# sub curry {
# my $f = shift;
# return sub (&;@) {
# my $first_arg = shift;
# my $r = sub { $f->($first_arg, @_ ) };
# return @_ ? $r->(@_ ) : $r;
# };
# }
## this doesn't correspond with the python
## way. (skipping for now)
## also skipping the method of currying more than
## one arg since we get that for free
# sub reduce { my $code = shift;
# my $val = shift;
# for (@_ ) { $val = $code->($val, $_ ) }
# return $val;
# }
## reduce is a python builtin. in python 3.x it will
## live in functools
# reduce(sub { $_[0] + $_[1] }, @VALUES) == sum(@VALUES)
reduce(lambda x,y: x+y, VALUES) == sum(VALUES)
# reduce(sub { $_[0] > $_[1] ? $_[0] : $_[1] }, @VALUES) == max(@VALUES)
reduce(lambda x,y: x if x > y else y, VALUES) == max(VALUES)
# sub fold {
# my $f = shift;
# my $fold;
# $fold = sub {
# my $x = shift;
# sub {
# return $x unless @_;
# my $first = shift;
# $fold->($f->($x, $first), @_ )
# }
# }
# }
## python's reduce already has the "initial"
## parameter
# sub interleave {
# my ($a, $b) = @_;
# return sub {
# my $next = $a->();
# unless (defined $next) {
# $a = $b;
# $next = $a->();
# }
# ($a, $b) = ($b, $a);
# $next;
# }
# }
def interleave(a,b):
options = [a,b]
while options:
try:
yield options[0].next()
options = options[1:] + options[:1]
except StopIteration:
options.pop(0)
# package Iterator_Logic;
# use base 'Exporter';
# @EXPORT = qw(i_or_ i_or i_and_ i_and i_without_ i_without);
# sub i_or_ {
# my ($cmp, $a, $b) = @_;
# my ($av, $bv) = ($a->(), $b->());
# return sub {
# my $rv;
# if (! defined $av && ! defined $bv) { return }
# elsif (! defined $av) { $rv = $bv; $bv = $b->() }
# elsif (! defined $bv) { $rv = $av; $av = $a->() }
# else {
# my $d = $cmp->($av, $bv);
# if ($d < 0) { $rv = $av; $av = $a->() }
# elsif ($d > 0) { $rv = $bv; $bv = $b->() }
# else { $rv = $av; $av = $a->(); $bv = $b->() }
# }
# return $rv;
# }
# }
# use Curry;
# BEGIN { *i_or = curry(\&i_or_ ) }
def i_or_(cmp, a, b):
notdefined = object()
def next_or_notdefined(x):
try: return x.next()
except StopIteration: return notdefined
av, bv = next_or_notdefined(a), next_or_notdefined(b)
while 1:
if av == notdefined and bv == notdefined:
return
elif av == notdefined:
yield bv
bv = next_or_notdefined(b)
elif bv == notdefined:
yield av
av = next_or_notdefined(a)
else:
d = cmp(av,bv)
if d < 0:
yield av
av = next_or_notdefined(a)
elif d > 0:
yield bv
bv = next_or_notdefined(b)
else:
yield av
av = next_or_notdefined(a)
bv = next_or_notdefined(b)
# sub i_and_ {
# my ($cmp, $a, $b) = @_;
# my ($av, $bv) = ($a->(), $b->());
# return sub {
# my $d;
# until (! defined $av || ! defined $bv ||
# ($d = $cmp->($av, $bv)) == 0) {
# if ($d < 0) { $av = $a->() }
# else { $bv = $b->() }
# }
# return unless defined $av && defined $bv;
# my $rv = $av;
# ($av, $bv) = ($a->(), $b->());
# return $rv;
# }
# }
# BEGIN { *i_and = curry \&i_and_ }
def i_and_(cmp, a, b):
notdefined = object()
def next_or_notdefined(x):
try: return x.next()
except StopIteration: return notdefined
av, bv = next_or_notdefined(a), next_or_notdefined(b)
while 1:
while not (av != notdefined or bv != notdefined
or cmp(av,bv) == 0):
if cmp(av,bv) < 0:
av = next_or_notdefined(a)
else:
bv = next_or_notdefined(b)
if av == notdefined and bv == notdefined:
return
rv = av
av, bv = next_or_notdefined(a), next_or_notdefined(b)
yield rv
### 7.4 Databases
# package FlatDB_Compose;
# use base 'FlatDB';
# use base 'Exporter';
# @EXPORT_OK = qw(query_or query_and query_not query_without);
# use Iterator_Logic;
# # usage: $dbh->query(fieldname, value)
# # returns all records for which (fieldname) matches (value)
# sub query {
# my $self = shift;
# my ($field, $value) = @_;
# my $fieldnum = $self->{FIELDNUM}{uc $field};
# return unless defined $fieldnum;
# my $fh = $self->{FH};
# seek $fh, 0, 0;
# <$fh>; # discard header line
# my $position = tell $fh;
# my $recno = 0;
# return sub {
# local $_;
# seek $fh, $position, 0;
# while (<$fh>) {
# chomp;
# $recno++;
# $position = tell $fh;
# my @fields = split $self->{FIELDSEP};
# my $fieldval = $fields[$fieldnum];
# return [$recno, @fields] if $fieldval eq $value;
# }
# return;
# };
# }
def query(self, field, value):
fieldnum = self.fieldnum.get(field.upper())
if fieldnum == None:
return
fh = self.fh
fh.seek(0)
fh.readline() # discard schema line
recno = 0
while 1:
line = fh.readline()
recno += 1
if not line:
break
position = fh.tell()
fields = line.split(FlatDB.FIELDSEP)
fieldval = fields[fieldnum]
if fieldval == value:
yield recno, line.strip()
fh.seek(position)
# sub callbackquery {
# my $self = shift;
# my $is_interesting = shift;
# my $fh = $self->{FH};
# seek $fh, 0, SEEK_SET;
# <$fh>; # discard header line
# my $position = tell $fh;
# my $recno = 0;
# return sub {
# local $_;
# seek $fh, $position, SEEK_SET;
# while (<$fh>) {
# $position = tell $fh;
# chomp;
# $recno++;
# my %F;
# my @fieldnames = @{$self->{FIELDS}};
# my @fields = split $self->{FIELDSEP};
# for (0 .. $#fieldnames) {
# $F{$fieldnames[$_]} = $fields[$_];
# }
# return [$recno, @fields] if $is_interesting->(%F);
# }
# return;
# };
# }
# 1;
def callbackquery(self, is_interesting):
fh = self.fh
fh.seek(0)
fh.readline() # discard schema line
recno = 0
while 1:
line = fh.readline()
recno += 1
if not line:
break
position = fh.tell()
line = line.strip()
fieldnames = self.field
fields = line.split(FlatDB.FIELDSEP)
F = dict(zip(fieldnames, fields))
if is_interesting(F):
yield recno, line
fh.seek(position)
# # $a but not $b
# sub i_without_ {
# my ($cmp, $a, $b) = @_;
# my ($av, $bv) = ($a->(), $b->());
# return sub {
# while (defined $av) {
# my $d;
# while (defined $bv && ($d = $cmp->($av, $bv)) > 0) {
# $bv = $b->();
# }
# if ( ! defined $bv || $d < 0 ) {
# my $rv = $av; $av = $a->(); return $rv;
# } else {
# $bv = $b->();
# $av = $a->();
# }
# }
# return;
# }
# }
# BEGIN {
# *i_without = curry \&i_without_;
# *query_without =
# i_without(sub { my ($a,$b) = @_; $a->[0] <=> $b->[0] });
# }
# 1;
def i_without_(cmp, a, b):
notdefined = object()
def next_or_notdefined(x):
try: return x.next()
except StopIteration: return notdefined
av, bv = next_or_notdefined(a), next_or_notdefined(b)
while av != notdefined:
d = cmp(av,bv)
while bv != notdefined and cmp(av,bv) > 0:
bv = next_or_notdefined(b)
d = cmp(av,bv)
if bv == notdefined or d < 0:
rv = av
av = next_or_notdefined(a)
yield rv
else:
bv = next_or_notdefined(b)
av = next_or_notdefined(a)
query_without = functools.partial(i_without_, cmp)
# sub query_not {
# my $self = shift;
# my $q = shift;
# query_without($self->all, $q);
# }
def query_not(self, q):
return query_without(self.all(), q)
### left off the last bit about operator overloading since it seems
### orthogonal to how you'd do it in python
Saturday, April 4, 2009
Smalltalk for a Year - Status Report 2
So my goal was to do monthly updates on my smalltalk progress during this year. For January I was going strong. Learning my way around, getting comfortable with syntax deciding what would be the best way to spend my energies, getting over the newness/alien-ness.
And then sometime in February I started losing momentum. And then into March a complete and utter stop. I even forgot I had this goal of learning smalltalk. So March became the month of figuring out why things had gone so badly and trying to pick myself up again.
There were a combination of factors that contributed to my akrasia (hey, it's a word!). Partly this was due to me being a little under the weather and trying to be the kind of person who actually listens to their body and goes to sleep when they are tired. In the middle of this I got bogged down in a seaside tutorial. At some point the code I typed in to follow along with the example wasn't working the way it should. I kept debugging this and that but looking at the same problem day after day when you are tired and new to a language is a bit of a lethal combination.
And then at some point hibernate on my window's laptop came up as a blue screen of death and I forgot to reopen the tutorial and my squeak image to remind me to take a look. At this point my amnesia was pretty much total.
Another thing I realized is that learning smalltalk *and* a web framework at the same time is a lot to take in. Especially if you don't really believe that you are going to use the web framework day to day.
I'm actually really interested in seaside. It seems fascinating. I'm a little distressed that I've developed a streak of practicality that makes it hard to focus on things that aren't directly useful to me. That's just not the geek way.
In any case March was the month of getting back on the horse. So here is my plan now. There are four things I'm going to work on in one order or another that I believe will be able to keep my attention.
OK, let's get that momentum going again.
And then sometime in February I started losing momentum. And then into March a complete and utter stop. I even forgot I had this goal of learning smalltalk. So March became the month of figuring out why things had gone so badly and trying to pick myself up again.
There were a combination of factors that contributed to my akrasia (hey, it's a word!). Partly this was due to me being a little under the weather and trying to be the kind of person who actually listens to their body and goes to sleep when they are tired. In the middle of this I got bogged down in a seaside tutorial. At some point the code I typed in to follow along with the example wasn't working the way it should. I kept debugging this and that but looking at the same problem day after day when you are tired and new to a language is a bit of a lethal combination.
And then at some point hibernate on my window's laptop came up as a blue screen of death and I forgot to reopen the tutorial and my squeak image to remind me to take a look. At this point my amnesia was pretty much total.
Another thing I realized is that learning smalltalk *and* a web framework at the same time is a lot to take in. Especially if you don't really believe that you are going to use the web framework day to day.
I'm actually really interested in seaside. It seems fascinating. I'm a little distressed that I've developed a streak of practicality that makes it hard to focus on things that aren't directly useful to me. That's just not the geek way.
In any case March was the month of getting back on the horse. So here is my plan now. There are four things I'm going to work on in one order or another that I believe will be able to keep my attention.
- convert Collective Intelligence code to smalltalk. I've already read this through once and did all the examples in python. i find that converting examples to a new language really makes it hard to skip over parts that you don't really understand.
- read Functional Pattern System for Object-Oriented Design and implement in smalltalk. I've been really interested in the streams data model and how it solves the hamming problem. I've been surprised not to see an easily found solution in smalltalk. i'm hoping to be able to develop a solution by reading this book.
- investigate SPY. I'm keenly interested in pypy and virtual machines. also i never really seem to make progress on learning a language until i start peeling back the curtains to see how things work under the covers
- read thru squeak soup code. I really like using the python version of this and this is a sort of problem I'm interested in and feel it would be useful to understand how it is solved.
OK, let's get that momentum going again.
Wednesday, March 25, 2009
Higher Order Perl (Python Style) : Chapter 6 - Infinite Streams
TOC
### Chapter 6 - Infinite Streams
### 6.1 Linked Lists
# sub node {
# my ($h, $t) = @_;
# [$h, $t];
# }
# sub head {
# my ($ls) = @_;
# $ls->[0];
# }
# sub tail {
# my ($ls) = @_;
# $ls->[1];
# }
# sub set_head {
# my ($ls, $new_head) = @_;
# $ls->[0] = $new_head;
# }
# sub set_tail {
# my ($ls, $new_tail) = @_;
# $ls->[1] = $new_tail;
# }
def node(h,t):
return [h,t]
def head(ls):
return ls[0]
def tail(ls):
return ls[1]
def set_head(ls, new_head):
ls[0] = new_head
def set_tail(ls, new_tail):
ls[1] = new_tail
# $my_list = node($new_data, $my_list);
my_list = node(new_data, my_list)
# sub insert_after {
# my ($node, $new_data) = @_;
# my $new_node = node($new_data, tail($node));
# set_tail($node, $new_node);
# }
def insert_after(node, new_data):
new_node = node(new_data, tail(node))
set_tail(node, new_node)
### 6.2 Lazy Linked Lists
# package Stream;
# use base Exporter;
# @EXPORT_OK = qw(node head tail drop upto upfrom show promise
# filter transform merge list_to_stream cutsort
# iterate_function cut_loops);
# %EXPORT_TAGS = ('all' => \@EXPORT_OK);
# sub node {
# my ($h, $t) = @_;
# [$h, $t];
# }
# sub head {
# my ($s) = @_;
# $s->[0];
# }
# sub tail {
# my ($s) = @_;
# if (is_promise($s->[1])) {
# return $s->[1]->();
# }
# $s->[1];
# }
# sub is_promise {
# UNIVERSAL::isa($_[0], 'CODE');
# }
def node(h,t):
return [h,t]
def head(s):
return s[0]
def tail(s):
if is_promise(s[1]):
return s[1]()
return s[1]
def is_promise(s):
return callable(s)
# sub promise (&) { $_[0] }
# this is the silliest kind of syntactic sugar
# but this will avoid some scoping confusion and
# premature execution i was experiencing
# in later examples and makes it look more like the perl example
def promise(func):
return func
# sub upto_list {
# my ($m, $n) = @_;
# return if $m > $n;
# node($m, upto_list($m+1, $n));
# }
def upto_list(m, n):
if m > n:
return None
return node(m, upto_list(m+1, n))
# sub upto {
# my ($m, $n) = @_;
# return if $m > $n;
# node($m, promise { upto($m+1, $n) } );
# }
def upto(m, n):
if m > n:
return None
return node(m, promise(lambda: upto(m+1, n)))
# sub upfrom {
# my ($m) = @_;
# node($m, promise { upfrom($m+1) } );
# }
def upfrom(m):
return node(m, promise(lambda: upfrom(m+1)))
# sub upfrom_list {
# my ($m) = @_;
# node($m, upfrom_list($m+1) );
# }
def upfrom_list(m):
return node(m, upfrom_list(m+1))
# sub show {
# my $s = shift;
# while ($s) {
# print head($s), $";
# $s = tail($s);
# }
# print $/;
# }
def show(s):
while(s):
print head(s),
s = tail(s)
# sub show {
# my ($s, $n) = @_;
# while ($s && (! defined $n || $n-- > 0)) {
# print head($s), $";
# $s = tail($s);
# }
# print $/;
# }
# NOTE: i'm following the perlish code here
# but in real life i would use itertools
def show(s, n=None):
while s and (n == None or n > 0):
print head(s),
s = tail(s)
if n != None:
n -= 1
# sub drop {
# my $h = head($_[0]);
# $_[0] = tail($_[0]);
# return $h;
# }
# to do this in python we'd either
# need to make a stream class or
# return a pair (h,s)
# where s is the stream in it's new state
def drop(s):
h, tail = s
return h, tail # which really was a noop
# OR something like:
class Stream(object):
def __init__(self, contents):
self.contents = contents
def drop(self):
h = head(self.contents)
self.contents = tail(contents)
return h
# sub show {
# my ($s, $n) = @_;
# while ($s && (! defined $n || $n-- > 0)) {
# print drop($s), $";
# }
# print $/;
# }
### we don't really get any savings here so i'll skip this
# sub transform (&$) {
# my $f = shift;
# my $s = shift;
# return unless $s;
# node($f->(head($s)),
# promise { transform($f, tail($s)) });
# }
def transform(f, s):
if not s:
return None
return node(f(head(s)),
promise(lambda: transform(f, tail(s))))
# my $evens = transform { $_[0] * 2 } upfrom(1);
evens = transform(lambda x: x * 2, upfrom(1))
# sub filter (&$) {
# my $f = shift;
# my $s = shift;
# until (! $s || $f->(head($s))) {
# drop($s);
# }
# return if ! $s;
# node(head($s),
# promise { filter($f, tail($s)) });
# }
def filter(f, s):
while not (not s or f(head(s))):
s = tail(s)
if not s:
return None
return node(head(s),
promise(lambda: filter(f, tail(s))))
# sub iterate_function {
# my ($f, $x) = @_;
# node($x, promise { iterate_function($f, $f->($x)) });
# }
def iterate_function(f, x):
return node(x, promise(lambda: iterate_function(f, f(x))))
### 6.3 Recursive Streams
# sub carrots {
# node('carrot', promise { carrots() });
# }
# my $carrots = carrots();
def carrots():
return node("carrot", promise(carrots))
# my $carrots = node('carrot', promise { carrots() });
carrots = node("carrot", promise(carrots()))
# my $carrots = node('carrot', promise { $carrots });
carrots = node("carrot", promise(lambda: carrots))
# sub pow2_from {
# my $n = shift;
# node($n, promise {pow2_from($n*2)})
# }
# my $powers_of_2 = pow2_from(1);
def pow2_from(n):
return node(n, promise(lambda: pow2_from(n*2)))
# my $powers_of_2;
# $powers_of_2 =
# node(1, promise { transform {$_[0]*2} $powers_of_2 });
# def powers_of_2():
# return node(1, powers_of_2)
powers_of_2 = node(1, promise(lambda: transform(lambda x: x*2, powers_of_2)))
# sub tail {
# my ($s) = @_;
# if (is_promise($s->[1])) {
# $s->[1] = $s->[1]->();
# }
# $s->[1];
# }
def tail(s):
if is_promise(s[1]):
s[1] = s[1]()
return s[1]
### 6.4 The Hamming Problem
# sub is_hamming {
# my $n = shift;
# $n/=2 while $n%2 == 0;
# $n/=3 while $n%3 == 0;
# $n/=5 while $n%5 == 0;
# return $n == 1;
# }
# # Return the first $N hamming numbers
# sub hamming {
# my $N = shift;
# my @hamming;
# my $t = 1;
# until (@hamming == $N) {
# push @hamming, $t if is_hamming($t);
# $t++;
# }
# @hamming;
# }
def is_hamming(n):
while n % 2 == 0:
n /= 2
while n % 3 == 0:
n /= 3
while n % 5 == 0:
n /= 5
return n == 1
def hamming(N):
result = []
t = 1
while len(result) < N:
if is_hamming(t):
result.append(t)
t += 1
return result
# sub merge {
# my ($S, $T) = @_;
# return $T unless $S;
# return $S unless $T;
# my ($s, $t) = (head($S), head($T));
# if ($s > $t) {
# node($t, promise {merge( $S, tail($T))});
# } elsif ($s < $t) {
# node($s, promise {merge(tail($S), $T)});
# } else {
# node($s, promise {merge(tail($S), tail($T))});
# }
# }
def merge(S,T):
if not S:
return T
if not T:
return S
s, t = head(S), head(T)
if s > t:
return node(t, promise(lambda: merge(S, tail(T))))
elif s < t:
return node(s, promise(lambda: merge(tail(S), T)))
else:
return node(s, promise(lambda: merge(tail(S), tail(T))))
# sub scale {
# my ($s, $c) = @_;
# transform { $_[0]*$c } $s;
# }
def scale(s, c):
return transform(lambda x: x * c, s)
# my $hamming;
# $hamming = node(1,
# promise {
# merge(scale($hamming, 2),
# merge(scale($hamming, 3),
# scale($hamming, 5),
# ))
# }
# );
# show($hamming, 3000);
hamming = node(1,
promise(lambda: merge(scale(hamming, 2),
merge(scale(hamming, 3),
scale(hamming, 5),
))
))
### just for kicks here are two solutions from the tubes:
### - OO version : http://aspn.activestate.com/ASPN/Mail/Message/python-list/905315
### - iterator verion (my preference) : http://mail.python.org/pipermail/python-list/2005-January/303480.html
### There is also a couple variations of this in python's test suite: test_generators.py
### but i'd wager that the haskell solution of this is still the king
### 6.5 Regex String Generation
# package Regex;
# use Stream ':all';
# use base 'Exporter';
# @EXPORT_OK = qw(literal union concat star plus charclass show
# matches);
# sub literal {
# my $string = shift;
# node($string, undef);
# }
# show(literal("foo"));
# foo
def literal(s):
return node(s, None)
# sub mingle2 {
# my ($s, $t) = @_;
# return $t unless $s;
# return $s unless $t;
# node(head($s),
# node(head($t),
# promise { mingle2(tail($s),
# tail($t))
# }
# ));
# }
def mingle2(s, t):
if not s:
return t
if not t:
return s
return node(head(s),
node(head(t),
promise(lambda: mingle2(tail(s), tail(t)))))
# sub union {
# my ($h, @s) = grep $_, @_;
# return unless $h;
# return $h unless @s;
# node(head($h),
# promise {
# union(@s, tail($h));
# });
# }
def union(*streams):
streams = [_s for _s in streams if _s != None]
if len(streams) == 0:
return None
if len(streams) == 1:
return streams[0]
return node(head(streams[0]),
promise(lambda: union(*(streams[1:]+[tail(streams[0])]))))
# # generate infinite stream ($k:1, $k:2, $k:3, ...)
# sub constant {
# my $k = shift;
# my $i = shift || 1;
# my $s = node("$k:$i", promise { constant($k, $i+1) });
# }
# my $fish = constant('fish');
# show($fish, 3);
# fish:1 fish:2 fish:3
# my $soup = union($fish, constant('dog'), constant('carrot'));
# show($soup, 10);
# fish:1 dog:1 carrot:1 fish:2 dog:2 carrot:2 fish:3 dog:3 carrot:3 fish:4
def constant(k, i=1):
return node("%s:%s" % (k,i),
promise(lambda: constant(k, i+1)))
fish = constant("fish")
soup = union(fish, constant("dog"), constant("carrot"))
show(soup, 10)
# sub concat {
# my ($S, $T) = @_;
# return unless $S && $T;
# my ($s, $t) = (head($S), head($T));
# node("$s$t", promise {
# union(postcat(tail($S), $t),
# precat(tail($T), $s),
# concat(tail($S), tail($T)),
# )
# });
# }
# sub precat {
# my ($s, $c) = @_;
# transform {"$c$_[0]"} $s;
# }
# sub postcat {
# my ($s, $c) = @_;
# transform {"$_[0]$c"} $s;
# }
def concat(S,T):
if None in (S, T):
return None
s, t = head(S), head(T)
return node("%s%s" % (s,t),
promise(lambda: (union(postcat(tail(S), t),
precat(tail(T),s),
concat(tail(S),tail(T))))))
def precat(s,c):
return transform(lambda x: "%s%s" % (c,x), s)
def postcat(s,c):
return transform(lambda x: "%s%s" % (x,c), s)
# # Im /(a|b)(c|d)$/
# my $z = concat(union(literal("a"), literal("b")),
# union(literal("c"), literal("d")),
# );
# show($z);
z = (concat(union(literal("a"), literal("b")),
union(literal("c"), literal("d")),
))
show(z)
# sub star {
# my $s = shift;
# my $r;
# $r = node("", promise { concat($s, $r) });
# }
# def star(s):
# _s = s[0]
# return iterate_function(lambda x: x + _s, "")
def star(s):
r = node("", promise(lambda: concat(s, r)))
return r
# sub show {
# my ($s, $n) = @_;
# while ($s && (! defined $n || $n-- > 0)) {
# print qq{"}, drop($s), qq{"\n};
# }
# print "\n";
# }
def show(s, n=None):
while s and (n == None or n > 0):
print repr(head(s))
s = tail(s)
if n != None:
n -= 1
# # charclass('abc') = /[abc]$/
# sub charclass {
# my $class = shift;
# union(map literal($_), split(//, $class));
# }
def charclass(_class):
return union(*[literal(c) for c in _class])
# # plus($s) = /s+$/
# sub plus {
# my $s = shift;
# concat($s, star($s));
# }
def plus(s):
return concat(s, star(s))
# use Regex qw(concat star literal show);
# # I represent /ab*$/
# my $regex1 = concat( literal("a"),
# star(literal("b"))
# );
# show($regex1, 10);
regex1 = concat( literal("a"),
star(literal("b"))
)
show(regex1, 10)
# # I represent /(aa|b)*$/
# my $regex2 = star(union(literal("aa"),
# literal("b"),
# ));
# show($regex2, 16);
regex2 = star(union(literal("aa"),
literal("b"),
))
show(regex2, 16)
# # I represent /(ab+|c)*$/
# my $regex3 = star(union(concat( literal("a"),
# plus(literal("b"))),
# literal("c")
# ));
# show($regex3, 20);
regex3 = star(union(concat( literal("a"),
plus(literal("b"))),
literal("c")
))
show(regex3, 20)
# sub union {
# my (@s) = grep $_, @_;
# return unless @s;
# return $s[0] if @s == 1;
# my $si = index_of_shortest(@s);
# node(head($s[$si]),
# promise {
# union(map $_ == $si ? tail($s[$_]) : $s[$_],
# 0 .. $#s);
# });
# }
# curse python's lame lambdas!
def union(*streams):
streams = [_s for _s in streams if _s != None]
if len(streams) == 0:
return None
if len(streams) == 1:
return streams[0]
si = index_of_shortest(streams)
return node(head(streams[si]),
promise(lambda: union(*[_s if _i != si else tail(_s) for (_i, _s) in enumerate(streams)])))
# sub index_of_shortest {
# my @s = @_;
# my $minlen = length(head($s[0]));
# my $si = 0;
# for (1 .. $#s) {
# my $h = head($s[$_]);
# if (length($h) < $minlen) {
# $minlen = length($h);
# $si = $_;
# }
# }
# $si;
# }
def index_of_shortest(*streams):
minlin = len(head(streams[0]))
si = 0
for i in range(1,len(streams)):
h = head(streams[i])
if len(h) < minlin:
minlen = len(h)
si = i
return si
### ugg. i can't seem to get correct ordering to work. :(
# sub matches {
# my ($string, $regex) = @_;
# while ($regex) {
# my $s = drop($regex);
# return 1 if $s eq $string;
# return 0 if length($s) > length($string);
# }
# return 0;
# }
def matches(string, regex):
while regex:
s = head(regex)
regex = tail(regex)
if s == string:
return True
if len(s) > len(string):
return False
return False
# ugg. this fails when star is involved
# sub bal {
# my $contents = shift;
# my $bal;
# $bal = node("", promise {
# concat($bal,
# union($contents,
# transform {"($_[0])"} $bal,
# )
# )
# });
# }
def bal(contents):
_bal = node("",
promise(lambda: union(contents,
transform(lambda x: "(%s)" % x, _bal))))
return _bal
# sub cut_bylen {
# my ($a, $b) = @_;
# # Its OK to emit item $a if the next item in the stream is $b
# length($a) < length($b);
# }
def cut_bylen(a,b):
return len(a) < len(b)
# sub list_to_stream {
# my $node = pop;
# while (@_) {
# $node = node(pop, $node);
# }
# $node;
# }
def list_to_stream(nodes):
_nodes = nodes[:]
_node = _nodes.pop()
while _nodes:
_node = node(_nodes.pop(), _node)
return _node
# sub insert (\@$$);
# sub cutsort {
# my ($s, $cmp, $cut, @pending) = @_;
# my @emit;
# while ($s) {
# while (@pending && $cut->($pending[0], head($s))) {
# push @emit, shift @pending;
# }
# if (@emit) {
# return list_to_stream(@emit,
# promise { cutsort($s, $cmp, $cut, @pending) });
# } else {
# insert(@pending, head($s), $cmp);
# $s = tail($s);
# }
# }
# return list_to_stream(@pending, undef);
# }
def cutsort(s, _cmp, cut, _pending=[]):
pending = _pending[:]
emit = []
while s:
while pending and cut(pending[0],head(s)):
emit.append(pending.pop(0))
if emit:
return list_to_stream(emit,
promise(lambda: cutsort(s, _cmp, cut, pending)))
else:
insert(pending, head(s), _cmp)
s = tail(s)
return list_to_stream(pending+[None])
# my $sorted =
# cutsort($regex3,
# sub { $_[0] cmp $_[1] }, # comparator
# \&cut_bylen # cutting function
# );
sorted = cutsort(regex3,
lambda x,y: cmp(x,y),
cut_bylen,
)
# sub insert (\@$$) {
# my ($a, $e, $cmp) = @_;
# my ($lo, $hi) = (0, scalar(@$a));
# while ($lo < $hi) {
# my $med = int(($lo + $hi) / 2);
# my $d = $cmp->($a->[$med], $e);
# if ($d <= 0) {
# $lo = $med+1;
# } else {
# $hi = $med;
# }
# }
# splice(@$a, $lo, 0, $e);
# }
def insert(a, e, _cmp):
lo, hi = 0, len(a)
while lo < hi:
med = int((lo+hi)/2)
d = _cmp(a[med],e)
if d <= 0:
lo = med+1
else:
hi = med
splice(a, lo, 0, e)
##
## above not tested
##
# sub _devino {
# my $f = shift;
# my ($dev, $ino) = stat($f);
# return unless defined $dev;
# "$dev;$ino";
# }
def _devino(f):
stat_tuple = os.state(f)
dev, ino = stat_tuple.st_dev, stat_tuple.st_ino
if not dev:
return None
return "%s;%s" % (dev, ino)
##
## ugg... sorry got lazy again and skipped the rest of this section
##
### 6.6 The Newton-Raphson Method
# sub sqrt2 {
# my $g = 2; # Initial guess
# until (close_enough($g*$g, 2)) {
# $g = ($g*$g + 2) / (2*$g);
# }
# $g;
# }
def sqrt2():
g = 2
while not close_enough(g*g, 2):
g = float(g*g + 2) / (2*g)
return g
# sub close_enough {
# my ($a, $b) = @_;
# return abs($a - $b) < 1e-12;
# }
def close_enough(a,b):
return abs(a-b) < 1e-12
# sub sqrtn {
# my $n = shift;
# my $g = $n; # Initial guess
# until (close_enough($g*$g, $n)) {
# $g = ($g*$g + $n) / (2*$g);
# }
# $g;
# }
def sqrtn(n):
g = n
while not close_enough(g*g, n):
g = float(g*g + n) / (2*g)
return g
# use Stream 'iterate_function';
# sub sqrt_stream {
# my $n = shift;
# iterate_function (sub { my $g = shift;
# ($g*$g + $n) / (2*$g);
# },
# $n);
# }
# 1;
def sqrt_stream(n):
return iterate_function(lambda g: float(g*g + n)/(2*g),
n)
# sub iterate_function {
# my ($f, $x) = @_;
# my $s;
# $s = node($x, promise { &transform($f, $s) });
# }
def iterate_function(f, x):
s = node(x, promise(lambda: transform(f, s)))
return s
# sub slope {
# my ($f, $x) = @_;
# my $e = 0.00000095367431640625;
# ($f->($x+$e) - $f->($x-$e)) / (2*$e);
# }
def slope(f, x):
e = 0.00000095367431640625
return (f(x+e) - f(x-e)) / (2*e)
# # Return a stream of numbers $x that make $f->($x) close to 0
# sub solve {
# my $f = shift;
# my $guess = shift || 1;
# iterate_function(sub { my $g = shift;
# $g - $f->($g)/slope($f, $g);
# },
# $guess);
# }
def solve(f, guess=1):
return iterate_function(lambda g: g - f(g)/slope(f,g),
guess)
# use Math::BigFloat;
# my $sqrt2 = solve(sub { $_[0] * $_[0] - 2 },
# Math::BigFloat->new(2));
# if want to use Decimal then need to retrofit a few functions:
import decimal
decimal.getcontext().prec = 64
def slope(f, x):
x = decimal.Decimal(x)
e = decimal.Decimal("0.00000095367431640625")
return (f(x+e) - f(x-e)) / (2*e)
def solve(f, guess=1):
return iterate_function(lambda g: g - f(g)/slope(f,g),
decimal.Decimal(guess))
sqrt2 = solve(lambda x: x*x - decimal.Decimal(2),
decimal.Decimal(2))
# sub cut_loops {
# my $s = shift;
# return unless $s;
# my @previous_values = @_;
# for (@previous_values) {
# if (head($s) == $_ ) {
# return;
# }
# }
# node(head($s),
# promise { cut_loops(tail($s), head($s), @previous_values) });
# }
def cut_loops(s, *args):
if s == None:
return None
previous_values = list(args)
for v in previous_values:
if head(s) == v:
return None
return node(head(s),
promise(lambda: cut_loops(tail(s), *([head(s)] + previous_values))))
# sub cut_loops {
# my ($tortoise, $hare) = @_;
# return unless $tortoise;
# # The hare and tortoise start at the same place
# $hare = $tortoise unless defined $hare;
# # The hare moves two steps every time the tortoise moves one
# $hare = tail(tail($hare));
# # If the hare and the tortoise are in the same place, cut the loop
# return if head($tortoise) == head($hare);
# return node(head($tortoise),
# promise { cut_loops(tail($tortoise), $hare) });
# }
def cut_loops(tortoise, hare=None):
if tortoise == None:
return None
# The hare and tortoise start at the same place
if hare == None:
hare = tortoise
# The hare moves two steps every time the tortoise moves one
hare = tail(tail(hare))
# If the hare and the tortoise are in the same place, cut the loop
if head(tortoise) == head(hare):
return None
return node(head(tortoise),
promise(lambda: cut_loops(tail(tortoise), hare)))
# sub cut_loops2 {
# my ($tortoise, $hare, $n) = @_;
# return unless $tortoise;
# $hare = $tortoise unless defined $hare;
# $hare = tail(tail($hare));
# return if head($tortoise) == head($hare)
# && $n++;
# return node(head($tortoise),
# promise { cut_loops(tail($tortoise), $hare, $n) });
# }
def cut_loops2(tortoise, hare=None, n=0):
if tortoise == None:
return None
if hare == None:
hare = tortoise
hare = tail(tail(hare))
if head(tortoise) == head(hare):
if n > 0:
return None
else:
n += 1
return node(head(tortoise),
promise(lambda: cut_loops2(tail(tortoise), hare, n)))
# sub owed {
# my ($P, $N, $pmt, $i) = @_;
# my $payment_factor = 0;
# for (0 .. $N-1) {
# $payment_factor += (1+$i) ** $_;
# }
# return $P * (1+$i)**$N - $pmt * $payment_factor;
# }
def owed(P,N,pmt,i):
payment_factor = 0
for x in range(0,N):
payment_factor += (1+i) ** x
return P * (1+i)**N - pmt * payment_factor
# sub owed {
# my ($P, $N, $pmt, $i) = @_;
# return $P * (1+$i)**$N - $pmt * ((1+$i)**$N - 1) / $i;
# }
def owed(P,N,pmt,i):
return P * (1+i)**N - pmt * ((1+i)**N - 1) / i
# sub owed_after_n_months {
# my $N = shift;
# owed(100_000, $N, 1_000, 0.005);
# }
# my $stream = cut_loops(solve(\&owed_after_n_months));
# my $n;
# $n = drop($stream) while $stream;
# print "You will be paid off in only $n months!\n";
def owed_after_n_months(N):
return owed(100000, N, 1000, 0.005)
stream = cut_loops(solve(owed_after_n_months))
n = head(stream)
while stream:
n = head(stream)
stream = tail(stream)
print "You will be paid off in only %s months!" % n
# sub affordable_mortgage {
# my $mortgage = shift;
# owed($mortgage, 30, 15_600, 0.0675);
# }
# my $stream = cut_loops(solve(\&affordable_mortgage));
# my $n;
# $n = drop($stream) while $stream;
# print "You can afford a \$$n mortgage.\n";
def affordable_mortgage(mortgage):
return owed(mortgage, 30, 15600, 0.0675)
stream = cut_loops(solve(affordable_mortgage))
n = head(stream)
while stream:
n = head(stream)
stream = tail(stream)
print "You can afford a $%s mortgage." % n
### 6.7 Power Series
# # Approximate sin(x) using the first n terms of the power series
# sub approx_sin {
# my $n = shift;
# my $x = shift;
# my ($denom, $c, $num, $total) = (1, 1, $x, 0);
# while ($n--) {
# $total += $num / $denom;
# $num *= $x*$x * -1;
# $denom *= ($c+1) * ($c+2);
# $c += 2;
# }
# $total;
# }
# 1;
def approx_sin(n, x):
denom, c, num, total = 1,1,x,0
while n:
n -= 1
total += num / float(denom)
num *= x*x * - 1
denom *= (c+1) * (c+2)
c += 2
return total
# package PowSeries;
# use base 'Exporter';
# @EXPORT_OK = qw(add2 mul2 partial_sums powers_of term_values
# evaluate derivative multiply recip divide
# $sin $cos $exp $log_ $tan);
# use Stream ':all';
# sub tabulate {
# my $f = shift;
# &transform($f, upfrom(0));
# }
def tabulate(f):
return transform(f, upfrom(0))
# my @fact = (1);
# sub factorial {
# my $n = shift;
# return $fact[$n] if defined $fact[$n];
# $fact[$n] = $n * factorial($n-1);
# }
# $sin = tabulate(sub { my $N = shift;
# return 0 if $N % 2 == 0;
# my $sign = int($N/2) % 2 ? -1 : 1;
# $sign/factorial($N)
# });
# $cos = tabulate(sub { my $N = shift;
# return 0 if $N % 2 != 0;
# my $sign = int($N/2) % 2 ? -1 : 1;
# $sign/factorial($N)
# });
fact = {0:1}
def factorial(n):
if fact.get(n):
return fact[n]
fact[n] = n * factorial(n-1)
return fact[n]
def sin_lambda(N):
if N % 2 == 0:
return 0
sign = 1
if (N/2) % 2 != 0:
-1
return sign / float(factorial(N))
sin = tabulate(sin_lambda)
def cos_lambda(N):
if N % 2 != 0:
return 0
sign = 1
if (N/2) % 2 != 0:
-1
return sign / float(factorial(N))
cos = tabulate(cos_lambda)
# sub add2 {
# my ($s, $t) = @_;
# return $s unless $t;
# return $t unless $s;
# node(head($s) + head($t),
# promise { add2(tail($s), tail($t)) });
# }
def add2(s,t):
if not t:
return s
if not s:
return t
return node(head(s) + head(t),
promise(lambda: add2(tail(s),tail(t))))
# sub mul2 {
# my ($s, $t) = @_;
# return unless $s && $t;
# node(head($s) * head($t),
# promise { mul2(tail($s), tail($t)) });
# }
def mul2(s,t):
if not (s and t):
return None
return node(head(s)*head(t),
promise(lambda: mul2(tail(s),tail(t))))
# sub partial_sums {
# my $s = shift;
# my $r;
# $r = node(head($s), promise { add2($r, tail($s)) });
# }
def partial_sums(s):
r = node(head(s), promise(lambda: add2(r, tail(s))))
return r
# sub powers_of {
# my $x = shift;
# iterate_function(sub {$_[0] * $x}, 1);
# }
def powers_of(x):
return iterate_function(lambda i: i*x, 1)
# sub term_values {
# my ($s, $x) = @_;
# mul2($s, powers_of($x));
# }
def term_values(s,x):
return mul2(s, powers_of(x))
# sub evaluate {
# my ($s, $x) = @_;
# partial_sums(term_values($s, $x));
# }
def evaluate(s,x):
return partial_sums(term_values(s,x))
# my $pi = 3.1415926535897932;
# show(evaluate($cos, $pi/6), 20);
pi = 3.1415926535897932
show(evaluate(cos, pi/6.0), 20)
### grrr..... each of the pieces i test
### above seems to be behaving correctly
### but for some reason the cos(pi/6) example
### is not coming out correctly. no idea :(
# # Get the n'th term from a stream
# sub nth {
# my $s = shift;
# my $n = shift;
# return $n == 0 ? head($s) : nth(tail($s), $n-1);
# }
# # Calculate the approximate cosine of x
# sub cosine {
# my $x = shift;
# nth(evaluate($cos, $x), 20);
# }
def nth(s,n):
if n == 0:
return head(s)
else:
return nth(tail(s), n-1)
def cosine(x):
return nth(evaluate(cos, x), 20)
# sub is_zero_when_x_is_pi {
# my $x = shift;
# my $c = cosine($x/6);
# $c * $c - 3/4;
# }
# show(solve(\&is_zero_when_x_is_pi), 20);
def is_zero_when_x_is_pi(x):
c = cosine(x/6.0)
return c * c - 3/4.0
show(solve(is_zero_when_x_is_pi), 20)
# sub derivative {
# my $s = shift;
# mul2(upfrom(1), tail($s));
# }
def derivative(s):
return mul2(upfrom(1), tail(s))
# show(derivative($sin), 20);
show(derivative(sin), 20)
# exp = tabulate(sub { my $N = shift; 1/factorial($N) });
exp = tabulate(lambda N: 1.0/factorial(N))
# $log_ = tabulate(sub { my $N = shift;
# $N==0 ? 0 : (-1)**$N/-$N });
log_ = tabulate(lambda N: N!=0 and (-1)**N/-N or 0)
# sub multiply {
# my ($S, $T) = @_;
# my ($s, $t) = (head($S), head($T));
# node($s*$t,
# promise { add2(scale(tail($T), $s),
# add2(scale(tail($S), $t),
# node(0,
# promise {multiply(tail($S), tail($T))}),
# ))
# }
# );
# }
def multiply(S,T):
s, t = head(S), head(T)
return node(s*t,
promise(add2(scale(tail(T),s),
add2(scale(tail(S),t),
node(0,
promise(multiply(tail(S), tail(T))))))))
# sub scale {
# my ($s, $c) = @_;
# return if $c == 0;
# return $s if $c == 1;
# transform { $_[0]*$c } $s;
# }
def scale(s, c):
if c == 0:
return None
if c == 1:
return s
return transform(lambda i: i*c, s)
# my $one = add2(multiply($cos, $cos), multiply($sin, $sin));
# show($one, 20);
one = add2(multiply(cos, cos), multiply(sin, sin))
show(one, 20)
### unfortunately i get:
### OverflowError: long int too large to convert to float
### perhaps come back later and figure this out
# sub sum {
# my @s = grep $_, @_;
# my $total = 0;
# $total += head($_ ) for @s;
# node($total,
# promise { sum(map tail($_ ), @s) }
# );
# }
def sum_(_s):
s = [s_ for s_ in _s if s_]
total = 0
for x in s:
total += head(x)
return node(total, promise(lambda: sum_([tail(x) for x in s])))
# sub multiply {
# my ($S, $T) = @_;
# my ($s, $t) = (head($S), head($T));
# node($s*$t,
# promise { sum(scale(tail($T), $s),
# scale(tail($S), $t),
# node(0,
# promise {multiply(tail($S), tail($T))}),
# )
# }
# );
# }
def multiply(S,T):
s,t = head(S), head(T)
return node(s*t,
promise(lambda: sum_(scale(tail(T),s), scale(tail(S),t), node(0, promise(lambda: multiply(tail(S), tail(T)))))))
# # Works only if head($s) = 1
# sub recip {
# my ($s) = shift;
# my $r;
# $r = node(1,
# promise { scale(multiply($r, tail($s)), -1) });
# }
def recip(s):
r = node(1,
promise(lambda: scale(multiply(r,tail(s)), -1)))
return r
# # Works only if head($t) = 1
# sub divide {
# my ($s, $t) = @_;
# multiply($s, recip($t));
# }
# $tan = divide($sin, $cos);
# show($tan, 10);
def divide(s,t):
return multiply(s, recip(t))
tan = divide(sin, cos)
show(tan, 10)
# my @fact = (Math::BigRat->new(1));
# sub factorial {
# my $n = shift;
# return $fact[$n] if defined $fact[$n];
# $fact[$n] = $n * factorial($n-1);
# }
# python 2.6 has "fractions" library
fact = [fraction.Fraction(1,1)]
def factorial(n):
if fact.get(n):
return fact[n]
fact[n] = n * factorial(n-1)
return fact[n]
Sunday, March 22, 2009
99 problems - python - 58
Generate-and-test paradigm
Apply the generate-and-test paradigm to construct all symmetric, completely balanced binary trees with a given number of nodes.
Apply the generate-and-test paradigm to construct all symmetric, completely balanced binary trees with a given number of nodes.
# Example:
# * sym-cbal-trees(5,Ts).
# Ts = [t(x, t(x, nil, t(x, nil, nil)), t(x, t(x, nil, nil), nil)), t(x, t(x, t(x, nil, nil), nil), t(x, nil, t(x, nil, nil)))]
def symmetric_completely_balanced_trees(node_count):
return [tree for tree in completely_balanced_tree(node_count) \
if symmetric_binary_tree(tree)]
Thursday, March 19, 2009
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.
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.
Monday, March 9, 2009
Higher Order Perl (Python Style) : Chapter 5 - From Recursion To Iterators
TOC
### Chapter 5 - From Recursion To Iterators
### 5.1 The Partition Problem Revisited
# sub find_share {
# my ($target, $treasures) = @_;
# return [] if $target == 0;
# return if $target < 0 || @$treasures == 0;
# my ($first, @rest) = @$treasures;
# my $solution = find_share($target-$first, \@rest);
# return [$first, @$solution] if $solution;
# return find_share($target , \@rest);
# }
def find_share(target, treasures):
if target == 0:
return []
if target < 0 or len(treasures) == 0:
return
first, rest = treasures[0], treasures[1:]
solution = find_share(target-first, rest)
if solution != None:
return [first] + solution
return find_share(target, rest)
# sub partition {
# my ($target, $treasures) = @_;
# return [] if $target == 0;
# return () if $target < 0 || @$treasures == 0;
# my ($first, @rest) = @$treasures;
# my @solutions = partition($target-$first, \@rest);
# return ((map {[$first, @$_]} @solutions),
# partition($target, \@rest));
# }
def partition(target, treasures):
if target == 0:
return [[]]
if target < 0 or len(treasures) == 0:
return []
first, rest = treasures[0], treasures[1:]
solutions = partition(target-first, rest)
return [[first] + solution for solution in solutions] + partition(target, rest)
# sub make_partitioner {
# my ($n, $treasures) = @_;
# my @todo = [$n, $treasures, []];
# sub {
# while (@todo) {
# my $cur = pop @todo;
# my ($target, $pool, $share) = @$cur;
# if ($target == 0) { return $share }
# next if $target < 0 || @$pool == 0;
# my ($first, @rest) = @$pool;
# push @todo, [$target-$first, \@rest, [@$share, $first]],
# [$target , \@rest, $share ];
# }
# return undef;
# } # end of anonymous iterator function
# } # end of make_partitioner
def make_partitioner(n, treasures):
todo = [[n, treasures, []]]
while todo:
target, pool, share = todo.pop()
if target == 0:
yield share
continue
if target < 0 or len(pool) == 0:
continue
first, rest = pool[0], pool[1:]
todo.append([target-first, rest, share+[first]])
todo.append([target, rest, share])
# sub make_partitioner {
# my ($n, $treasures) = @_;
# my @todo = [$n, $treasures, []];
# sub {
# while (@todo) {
# my $cur = pop @todo;
# my ($target, $pool, $share) = @$cur;
# if ($target == 0) { return $share }
# next if $target < 0 || @$pool == 0;
# my ($first, @rest) = @$pool;
# push @todo, [$target, \@rest, $share ] if @rest;
# if ($target == $first) {
# return [@$share, $first];
# } elsif ($target > $first && @rest) {
# push @todo, [$target-$first, \@rest, [@$share, $first]],
# }
# }
# return undef;
# } # end of anonymous iterator function
# } # end of make_partitioner
def make_partitioner(n, treasures):
todo = [[n, treasures, []]]
while todo:
target, pool, share = todo.pop()
if target == 0:
yield share
continue
if target < 0 or len(pool) == 0:
continue
first, rest = pool[0], pool[1:]
if rest:
todo.append([target, rest, share])
if target == first:
yield share+[first]
elif (target > first and rest):
todo.append([target-first, rest, share+[first]])
### 5.2 How to Convert a Recursive Function to an Iterator
# sub rec {
# my ($n, $k) = @_;
# print $k x $n, "\n";
# for (1 .. $n-1) {
# rec($n-$_, $_);
# }
# }
def rec(n, k):
print str(k) * n
for i in range(1,n):
rec(n-i, i)
# sub partition {
# print "@_\n";
# my ($n, @parts) = @_;
# for (1 .. $n-1) {
# partition($n-$_, $_, @parts);
# }
# }
def partition(n, parts):
print [n] +parts
for i in range(1,n):
partition(n-i, [i]+parts)
# for (@words) { $seen{$_}++ }
# @repeats = grep $seen{$_} > 1, keys %seen;
seen = {}
for word in words:
seen.setdefault(word,[0])[0] += 1
repeats = [word for word in seen if seen[word][0] > 1]
# for (@words) { $seen{lc $_}++ }
# @repeats = grep $seen{$_} > 1, keys %seen;
seen = {}
for word in words:
seen.setdefault(word.lower(),[0])[0] += 1
repeats = [word for word in seen if seen[word][0] > 1]
# sub partition {
# print "@_\n" if decreasing_order(@_);
# my ($n, @parts) = @_;
# for (1 .. $n-1) {
# partition($n-$_, $_, @parts);
# }
# }
def partition(n, parts):
if decreasing_order([n] +parts):
print [n] + parts
for i in range(1,n):
partition(n-i, [i]+parts)
# sub partition {
# print "@_\n";
# my ($largest, @rest) = @_;
# my $min = $rest[0] || 1;
# my $max = int($largest/2);
# for ($min .. $max) {
# partition($largest-$_, $_, @rest);
# }
# }
def partition(largest, rest):
print [largest] + rest
min = (rest + [1])[0]
max = largest / 2
for i in range(min, max+1):
partition(largest-i, [i]+rest)
# sub make_partition {
# my $n = shift;
# my @agenda = ([$n, # $largest
# [], # \@rest
# 1, # $min
# int($n/2), # $max
# ]);
# return Iterator {
# while (@agenda) {
# my $item = pop @agenda;
# my ($largest, $rest, $min, $max) = @$item;
# for ($min .. $max) {
# push @agenda, [$largest - $_, # $largest
# [$_, @$rest], # \@rest
# $_, # $min
# int(($largest - $_)/2), # $max
# ];
# }
# return [$largest, @$rest];
# }
# return;
# };
# }
def make_partition(n):
agenda = [(n, # largest
[], # rest
1, # min
n/2) # max
]
while agenda:
(largest, rest, min, max) = agenda.pop()
for i in range(min, max+1):
agenda.append((largest - i, # largest
[i]+rest, # rest
i, # min
(largest-i)/2 # max
))
yield [largest]+rest
# sub partition {
# my ($largest, $rest, $min, $max) = @_;
# for ($min .. $max) {
# partition($largest-$_, [$_, @$rest], $_, int(($largest - $_)/2));
# }
# return [$largest, @$rest];
# }
def partition(largest, rest, min, max):
for i in range(min, max+1):
partition(largest-i, [i]+rest, i, (largest-i)/2)
return [largest] + rest
# sub make_partition {
# my $n = shift;
# my @agenda = [$n];
# return Iterator {
# while (@agenda) {
# my $item = pop @agenda;
# my ($largest, @rest) = @$item;
# my $min = $rest[0] || 1;
# my $max = int($largest/2);
# for ($min .. $max) {
# push @agenda, [$largest-$_, $_, @rest];
# }
# return $item;
# }
# return;
# };
# }
def make_partition(n):
agenda = [[n,[]]]
while agenda:
largest, rest = agenda.pop()
min = (rest + [1])[0]
max = largest / 2
for i in range(min, max+1):
agenda.append([largest-i, [i]+rest])
yield [largest] + rest
# sub make_partition {
# my $n = shift;
# my @agenda = [$n];
# return Iterator {
# return unless @agenda;
# my $item = pop @agenda;
# my ($largest, @rest) = @$item;
# my $min = $rest[0] || 1;
# my $max = int($largest/2);
# for ($min .. $max) {
# push @agenda, [$largest-$_, $_, @rest];
# }
# return $item;
# };
# }
### we *do* keep the while loop in the python version
### and it looks just like the previous solution
# # Compare two partitions for preferred order
# sub partitions {
# for my $i (0 .. $#$a) {
# my $cmp = $b->[$i] <=> $a->[$i];
# return $cmp if $cmp;
# }
# }
# lists and tuples will compare naturally
# in the correct way (unless i'm missing something here)
def partitions(a,b):
return cmp(a,b)
# sub make_partition {
# my $n = shift;
# my @agenda = [$n];
# return Iterator {
# return unless @agenda;
# my $item = pop @agenda;
# my ($largest, @rest) = @$item;
# my $min = $rest[0] || 1;
# my $max = int($largest/2);
# for ($min .. $max) {
# push @agenda, [$largest-$_, $_, @rest];
# }
# @agenda = sort partitions @agenda;
# return $item;
# };
# }
def make_partition(n):
agenda = [[n,[]]]
while agenda:
largest, rest = agenda.pop()
min = (rest + [1])[0]
max = largest / 2
for i in range(min, max+1):
agenda.append([largest-i, [i]+rest])
agenda.sort()
yield [largest] + rest
### 5.3 A Generic Search Iterator
# use Iterator_Utils 'Iterator';
# sub make_dfs_search {
# my ($root, $children) = @_;
# my @agenda = $root;
# return Iterator {
# return unless @agenda;
# my $node = pop @agenda;
# push @agenda, $children->($node);
# return $node;
# };
# }
def make_dfs_search(root, children):
agenda = [root]
while agenda:
node = agenda.pop()
agenda.extend(children(node))
yield node
# sub make_partition {
# my $n = shift;
# my $root = [$n];
# my $children = sub {
# my ($largest, @rest) = @{shift()};
# my $min = $rest[0] || 1;
# my $max = int($largest/2);
# map [$largest-$_, $_, @rest], ($min .. $max);
# };
# make_dfs_search($root, $children);
# }
def make_partition(n):
root = [n]
def children(largest, rest):
min = (rest + [1])[0]
max = largest / 2
return [(largest-i, [i]+rest) for i in range(min, max+1)]
return make_dfs_search(root, children)
# sub make_dfs_search {
# my ($root, $children, $is_interesting) = @_;
# my @agenda = $root;
# return Iterator {
# while (@agenda) {
# my $node = pop @agenda;
# push @agenda, $children->($node);
# return $node if !$is_interesting || $is_interesting->($node);
# }
# return;
# };
# }
def make_dfs_search(root, children, is_interesting=None):
agenda = [root]
while agenda:
node = agenda.pop()
agenda.extend(children(node))
if is_interesting and is_interesting(node):
yield node
# sub make_dfs_value_search {
# my ($root, $children, $is_interesting, $evaluate) = @_;
# $evaluate = memoize($evaluate);
# my @agenda = $root;
# return Iterator {
# while (@agenda) {
# my $best_node_so_far = 0;
# my $best_node_value = $evaluate->($agenda[0]);
# for (0 .. $#agenda) {
# my $val = $evaluate->($agenda[$_]);
# next unless $val > $best_node_value;
# $best_node_value = $val;
# $best_node_so_far = $_;
# }
# my $node = splice @agenda, $best_node_so_far, 1;
# push @agenda, $children->($node);
# return $node if !$is_interesting || $is_interesting->($node);
# }
# return;
# };
# }
def make_dfs_value_search(root, children, is_interesting=None, evaluate=None):
if not is_interesting:
is_interesting = (lambda x: True)
if not evaluate:
evaluate = (lambda x: x)
agenda = [root]
while agenda:
node = agenda.pop()
agenda.extend(children(node))
if is_interesting(node):
yield node
# sub make_dfs_search {
# my ($root, $children, $is_interesting) = @_;
# my @agenda = $root;
# return Iterator {
# while (@agenda) {
# my $node = pop @agenda;
# push @agenda, reverse $children->($node);
# return $node if !$is_interesting || $is_interesting->($node);
# }
# return;
# };
# }
def make_dfs_search(root, children, is_interesting=None):
agenda = [root]
while agenda:
node = agenda.pop()
agenda.extend(reversed(children(node)))
if is_interesting and is_interesting(node):
yield node
### 5.4 Other General Techniques for Eliminating Recursion
# sub gcd {
# my ($m, $n) = @_;
# if ($n == 0) {
# return $m;
# }
# return gcd($n, $m % $n);
# }
def gcd(m,n):
if n == 0:
return m
return gcd(n, m % n)
# sub gcd {
# my ($m, $n) = @_;
# until ($n == 0) {
# ($m, $n) = ($n, $m % $n);
# }
# return $m;
# }
def gcd(m,n):
while n != 0:
m, n = n, m % n
return m
# sub print_tree {
# my $t = shift;
# return unless $t; # Null tree
# print_tree($t->left);
# print $t->root, "\n";
# print_tree($t->right);
# }
def print_tree(t):
if not t:
return
print_tree(t.left)
print t.root
print_tree(t.right)
# sub print_tree {
# my $t = shift;
# while ($t) {
# print_tree($t->left);
# print $t->root, "\n";
# $t = $t->right;
# }
# }
def print_tree(t):
while t:
print_tree(t.left)
print t.root
t = t.right
# sub print_tree {
# my $t = shift;
# print_tree($t->left) if $t->left;
# print $t->root, "\n";
# print_tree($t->right) if $t->right;
# }
def print_tree(t):
if t.left:
print_tree(t.left)
print t.root
if t.right:
print_tree(t.right)
# sub print_tree {
# my $t = shift;
# do {
# print_tree($t->left) if $t->left;
# print $t->root, "\n";
# $t = $t->right;
# } while $t;
# }
def print_tree(t):
while t:
if t.left:
print_tree(t.left)
print t.root
t = t.right
# sub powerset_recurse ($;@) {
# my ( $set, $powerset, $keys, $values, $n, $i ) = @_;
# if ( @_ == 1 ) { # Initialize.
# my $null = { };
# $powerset = { $null, $null };
# $keys = [ keys %{ $set } ];
# $values = [ values %{ $set } ];
# $nmembers = keys %{ $set }; # This many rounds.
# $i = 0; # The current round.
# }
# # Ready?
# return $powerset if $i == $nmembers;
# # Remap.
# my @powerkeys = keys %{ $powerset };
# my @powervalues = values %{ $powerset };
# my $powern = @powerkeys;
# my $j;
# for ( $j = 0; $j < $powern; $j++ ) {
# my %subset = ( );
# # Copy the old set to the subset.
# @subset{keys %{ $powerset->{ $powerkeys [ $j ] } }} =
# values %{ $powerset->{ $powervalues[ $j ] } };
# # Add the new member to the subset.
# $subset{$keys->[ $i ]} = $values->[ $i ];
# # Add the new subset to the powerset.
# $powerset->{ \%subset } = \%subset;
# }
# # Recurse.
# powerset_recurse( $set, $powerset, $keys, $values, $nmembers, $i+1 );
# }
# we are stuck since python won't permit keys that aren't hashable
# so instead of dicts of dicts i'll use set() with tuples.
# we can easily go back to dicts from a set of tuples
# but i may be missing some subtly important feature of this
# algorithm. but in any case it works.
# also: this algorithm *seems* ridiculously unpythonic
# _set: [(key,val)] # list of
# powerset: [set([(key, val)])] # list of sets of tuple
def powerset_recurse(_set, powerset=None, i=0):
# set up init stuff
if powerset == None:
powerset = [set()]
if i == len(_set):
return powerset
powerset_copy = copy.deepcopy(powerset)
ith_item = _set[i]
for subset in powerset_copy:
subset.add(ith_item)
powerset += powerset_copy
return powerset_recurse(_set, powerset, i+1)
### uggg. so that works, and *seems* very close
### in principle to the original but I feel like
### i didn't try hard enough to match the original style
# sub powerset_recurse ($) {
# my ( $set ) = @_;
# my $null = { };
# my $powerset = { $null, $null };
# my $keys = [ keys %{ $set } ];
# my $values = [ values %{ $set } ];
# my $nmembers = keys %{ $set }; # This many rounds.
# my $i = 0; # The current round.
# until ($i == $nmembers) {
# # Remap.
# my @powerkeys = keys %{ $powerset };
# my @powervalues = values %{ $powerset };
# my $powern = @powerkeys;
# my $j;
# for ( $j = 0; $j < $powern; $j++ ) {
# my %subset = ( );
# # Copy the old set to the subset.
# @subset{keys %{ $powerset->{ $powerkeys [ $j ] } }} =
# values %{ $powerset->{ $powervalues[ $j ] } };
# # Add the new member to the subset.
# $subset{$keys->[ $i ]} = $values->[ $i ];
# # Add the new subset to the powerset.
# $powerset->{ \%subset } = \%subset;
# }
# $i++;
# }
# return $powerset;
# }
def powerset_recurse(_set, powerset=None, i=0):
# set up init stuff
if powerset == None:
powerset = [set()]
while i < len(_set):
powerset_copy = copy.deepcopy(powerset)
ith_item = _set[i]
for subset in powerset_copy:
subset.add(ith_item)
powerset += powerset_copy
i += 1
return powerset
# sub powerset_recurse ($) {
# my ( $set ) = @_;
# my $null = { };
# my $powerset = { $null, $null };
# my $keys = [ keys %{ $set } ];
# my $values = [ values %{ $set } ];
# my $nmembers = keys %{ $set }; # This many rounds.
# for my $i (0 .. $nmembers-1) {
# # Remap.
# my @powerkeys = keys %{ $powerset };
# my @powervalues = values %{ $powerset };
# my $powern = @powerkeys;
# my $j;
# for ( $j = 0; $j < $powern; $j++ ) {
# my %subset = ( );
# # Copy the old set to the subset.
# @subset{keys %{ $powerset->{ $powerkeys [ $j ] } }} =
# values %{ $powerset->{ $powervalues[ $j ] } };
# # Add the new member to the subset.
# $subset{$keys->[ $i ]} = $values->[ $i ];
# # Add the new subset to the powerset.
# $powerset->{ \%subset } = \%subset;
# }
# }
# return $powerset;
# }
def powerset_recurse(_set, powerset=None, i=0):
# set up init stuff
if powerset == None:
powerset = [set()]
for i in range(len(_set)):
powerset_copy = copy.deepcopy(powerset)
ith_item = _set[i]
for subset in powerset_copy:
subset.add(ith_item)
powerset += powerset_copy
return powerset
# sub powerset_recurse ($) {
# my ( $set ) = @_;
# my $null = { };
# my $powerset = { $null, $null };
# while (my ($key, $value) = each %$set) {
# # Remap.
# my @powerkeys = keys %{ $powerset };
# my @powervalues = values %{ $powerset };
# my $powern = @powerkeys;
# my $j;
# for ( $j = 0; $j < $powern; $j++ ) {
# my %subset = ( );
# # Copy the old set to the subset.
# @subset{keys %{ $powerset->{ $powerkeys [ $j ] } }} =
# values %{ $powerset->{ $powervalues[ $j ] } };
# # Add the new member to the subset.
# $subset{$key} = $value;
# # Add the new subset to the powerset.
# $powerset->{ \%subset } = \%subset;
# }
# }
# return $powerset;
# }
def powerset_recurse(_set):
powerset = [set()]
for ith_item in (_set):
powerset_copy = copy.deepcopy(powerset)
for subset in powerset_copy:
subset.add(ith_item)
powerset += powerset_copy
return powerset
# sub binary {
# my ($n) = @_;
# return $n if $n == 0 || $n == 1;
# my $k = int($n/2);
# my $b = $n % 2;
# my $E = binary($k);
# return $E . $b;
# }
def binary(n):
if n in (0,1):
return str(n)
k = n / 2
b = n % 2
return binary(k) + str(b)
# sub binary {
# my ($n, $RETVAL) = @_;
# $RETVAL = "" unless defined $RETVAL;
# my $k = int($n/2);
# my $b = $n % 2;
# $RETVAL = "$b$RETVAL";
# return $RETVAL if $n == 0 || $n == 1;
# binary($k, $RETVAL);
# }
def binary(n, retval=""):
k = n / 2
b = n % 2
retval = str(b)+retval
if n in (0,1):
return retval
return binary(k, retval)
# sub binary {
# my ($n, $RETVAL) = @_;
# $RETVAL = "";
# while (1) {
# my $k = int($n/2);
# my $b = $n % 2;
# $RETVAL = "$b$RETVAL";
# return $RETVAL if $n == 0 || $n == 1;
# $n = $k;
# }
# }
def binary(n, retval=""):
while 1:
k = n / 2
b = n % 2
retval = str(b)+retval
if n in (0,1):
return retval
n = k
# sub binary {
# my ($n, $RETVAL) = @_;
# $RETVAL = "";
# while (1) {
# my $b = $n % 2;
# $RETVAL = "$b$RETVAL";
# return $RETVAL if $n == 0 || $n == 1;
# $n = int($n/2);
# }
# }
def binary(n, retval=""):
while 1:
b = n % 2
retval = str(b)+retval
if n in (0,1):
return retval
n = n/2
# sub factorial {
# my ($n) = @_;
# return 1 if $n == 0;
# return factorial($n-1) * $n;
# }
def factorial(n):
if n == 0:
return 1
return factorial(n-1)*n
# sub factorial {
# my ($n, $product) = @_;
# $product = 1 unless defined $product;
# return $product if $n == 0;
# return factorial($n-1, $n * $product);
# }
def factorial(n, product=1):
if n == 0:
return product
return factorial(n-1, n*product)
# sub factorial {
# my ($n) = @_;
# my $product = 1;
# until ($n == 0) {
# $product *= $n;
# $n--;
# }
# return $product;
# }
def factorial(n):
product = 1
while n != 0:
product *= n
n -= 1
return product
# sub print_tree {
# my $t = shift;
# do {
# print_tree($t->left) if $t->left;
# print $t->root, "\n";
# $t = $t->right;
# } while $t;
# }
def print_tree(t):
while t:
if t.left:
print_tree(t.left)
print t.root
t = t.right
# sub print_tree {
# my $t = shift;
# my @STACK;
# do {
# push(@STACK, $t), $t = $t->left if $t->left;
# RETURN:
# print $t->root, "\n";
# $t = $t->right;
# } while $t;
# return unless @STACK;
# $t = pop @STACK;
# goto RETURN;
# }
### this and the next couple examples
### use GOTOs. not much i can do about that.
### if there is a way to simulate gotos in python
### i'd be interested to hear it.
# sub fib {
# my $n = shift;
# if ($n < 2) { return $n }
# fib($n-2) + fib($n-1);
# }
def fib(n):
if n < 2:
return n
return fib(n-2) + fib(n-1)
# sub fib {
# my $n = shift;
# if ($n < 2) {
# return $n;
# } else {
# my $s1 = fib($n-2);
# my $s2 = fib($n-1);
# return $s1 + $s2;
# }
# }
def fib(n):
if n < 2:
return n
else:
s1 = fib(n-2)
s2 = fib(n-1)
return s1 + s2
# sub fib {
# my $n = shift;
# while (1) {
# if ($n < 2) {
# return $n;
# } else {
# my $s1 = fib($n-2);
# my $s2 = fib($n-1);
# return $s1 + $s2;
# }
# }
# }
def fib(n):
while 1:
if n < 2:
return n
else:
s1 = fib(n-2)
s2 = fib(n-1)
return s1 + s2
# sub fib {
# my $n = shift;
# my ($s1, $s2, $return);
# while (1) {
# if ($n < 2) {
# return $n;
# } else {
# if ($BRANCH == 0) {
# $return = fib($n-2);
# } elsif ($BRANCH == 1) {
# $s1 = $return;
# $return = fib($n-1);
# } elsif ($BRANCH == 2) {
# $s2 = $return;
# $return = $s1 + $s2;
# }
# }
# }
# }
def fib(n):
BRANCH = 0
while 1:
if n < 2:
return n
else:
if BRANCH == 0:
_return = fib(n-2)
elif BRANCH == 1:
s1 = _return
_retrun = fib(n-2)
elif BRANCH == 2:
s2 = _return
_return = s1 + s2
return _return
# sub fib {
# my $n = shift;
# my ($s1, $s2, $return);
# my $BRANCH = 0;
# while (1) {
# if ($n < 2) {
# return $n;
# } else {
# if ($BRANCH == 0) {
# $return = fib($n-2);
# } elsif ($BRANCH == 1) {
# $s1 = $return;
# $return = fib($n-1);
# } elsif ($BRANCH == 2) {
# $s2 = $return;
# $return = $s1 + $s2;
# }
# }
# }
# }
def fib(n):
BRANCH = 0
while 1:
if n < 2:
return n
else:
if BRANCH == 0:
_return = fib(n-2)
elif BRANCH == 1:
s1 = _return
_return = fib(n-1)
elif BRANCH == 2:
s2 = _return
_return = s1 + s2
return _return
# sub fib {
# my $n = shift;
# my ($s1, $s2, $return);
# my $BRANCH = 0;
# while (1) {
# if ($n < 2) {
# $return = $n;
# } else {
# if ($BRANCH == 0) {
# $return = fib($n-2);
# } elsif ($BRANCH == 1) {
# $s1 = $return;
# $return = fib($n-1);
# } elsif ($BRANCH == 2) {
# $return = $s1 + $s2;
# }
# }
# }
# }
def fib(n):
BRANCH = 0
while 1:
if n < 2:
_return = n
else:
if BRANCH == 0:
_return = fib(n-2)
elif BRANCH == 1:
s1 = _return
_return = fib(n-1)
elif BRANCH == 2:
_return = s1 + s2
return _return
# sub fib {
# my $n = shift;
# my ($s1, $s2, $return);
# my $BRANCH = 0;
# my @STACK;
# while (1) {
# if ($n < 2) {
# $return = $n;
# } else {
# if ($BRANCH == 0) {
# push @STACK, [ $BRANCH, $s1, $s2, $n ];
# $n -= 2;
# $BRANCH = 0;
# next;
# } elsif ($BRANCH == 1) {
# $s1 = $return;
# push @STACK, [ $BRANCH, $s1, $s2, $n ];
# $n -= 1;
# $BRANCH = 0;
# next;
# } elsif ($BRANCH == 2) {
# $s2 = $return;
# $return = $s1 + $s2;
# }
# }
# }
# }
def fib(n):
BRANCH = 0
STACK = []
while 1:
if n < 2:
_return = n
else:
if BRANCH == 0:
STACK.append([BRANCH, s1, s2, n])
n -= 2
BRANCH = 0
continue
elif BRANCH == 1:
s1 = _return
STACK.append([BRANCH, s1, s2, n])
n -= 1
BRANCH = 0
continue
elif BRANCH == 2:
s2 = _return
_return = s1 + s2
return _return
# sub fib {
# my $n = shift;
# my ($s1, $s2, $return);
# my $BRANCH = 0;
# my @STACK;
# while (1) {
# if ($n < 2) {
# $return = $n;
# } else {
# if ($BRANCH == 0) {
# push @STACK, [ $BRANCH, $s1, $s2, $n ];
# $n -= 2;
# $BRANCH = 0;
# next;
# } elsif ($BRANCH == 1) {
# $s1 = $return;
# push @STACK, [ $BRANCH, $s1, $s2, $n ];
# $n -= 1;
# $BRANCH = 0;
# next;
# } elsif ($BRANCH == 2) {
# $s2 = $return;
# $return = $s1 + $s2;
# }
# }
# return $return unless @STACK;
# ($BRANCH, $s1, $s2, $n) = @{pop @STACK};
# $BRANCH++;
# }
def fib(n):
BRANCH = 0
STACK = []
while 1:
if n < 2:
_return = n
else:
if BRANCH == 0:
STACK.append([BRANCH, s1, s2, n])
n -= 2
BRANCH = 0
continue
elif BRANCH == 1:
s1 = _return
STACK.append([BRANCH, s1, s2, n])
n -= 1
BRANCH = 0
continue
elif BRANCH == 2:
s2 = _return
_return = s1 + s2
if not STACK:
return _return
(BRANCH, s1, s2, n) = STACK.pop()
BRANCH += 1
# sub fib {
# my $n = shift;
# my ($s1, $s2, $return);
# my $BRANCH = 0;
# my @STACK;
# while (1) {
# if ($n < 2) {
# $return = $n;
# } else {
# if ($BRANCH == 0) {
# push @STACK, [ $BRANCH, 0, $s2, $n ];
# $n -= 2;
# next;
# } elsif ($BRANCH == 1) {
# push @STACK, [ $BRANCH, $return, $s2, $n ];
# $n -= 1;
# $BRANCH = 0;
# next;
# } elsif ($BRANCH == 2) {
# $s2 = $return;
# $return = $s1 + $s2;
# }
# }
# return $return unless @STACK;
# ($BRANCH, $s1, $s2, $n) = @{pop @STACK};
# $BRANCH++;
# }
def fib(n):
BRANCH = 0
STACK = []
while 1:
if n < 2:
_return = n
else:
if BRANCH == 0:
STACK.append([BRANCH, 0, s2, n])
n -= 2
BRANCH = 0
continue
elif BRANCH == 1:
s1 = _return
STACK.append([BRANCH, _return, s2, n])
n -= 1
BRANCH = 0
continue
elif BRANCH == 2:
s2 = _return
_return = s1 + s2
if not STACK:
return _return
(BRANCH, s1, s2, n) = STACK.pop()
BRANCH += 1
# sub fib {
# my $n = shift;
# my ($s1, $return);
# my $BRANCH = 0;
# my @STACK;
# while (1) {
# if ($n < 2) {
# $return = $n;
# } else {
# if ($BRANCH == 0) {
# push @STACK, [ $BRANCH, 0, $n ];
# $n -= 2;
# next;
# } elsif ($BRANCH == 1) {
# push @STACK, [ $BRANCH, $return, $n ];
# $n -= 1;
# $BRANCH = 0;
# next;
# } elsif ($BRANCH == 2) {
# $return += $s1;
# }
# }
# return $return unless @STACK;
# ($BRANCH, $s1, $n) = @{pop @STACK};
# $BRANCH++;
# }
# }
def fib(n):
BRANCH = 0
STACK = []
while 1:
if n < 2:
_return = n
else:
if BRANCH == 0:
STACK.append([BRANCH, 0, n])
n -= 2
continue
elif BRANCH == 1:
STACK.append([BRANCH, _return, n])
n -= 1
BRANCH = 0
continue
elif BRANCH == 2:
_return += s1
if not STACK:
return _return
(BRANCH, s1, s2, n) = STACK.pop()
BRANCH += 1
# sub fib {
# my $n = shift;
# my ($s1, $return);
# my $BRANCH = 0;
# my @STACK;
# while (1) {
# if ($n < 2) {
# $return = $n;
# } else {
# if ($BRANCH == 0) {
# push (@STACK, [ $BRANCH, 0, $n ]), $n -= 1 while $n >= 2;
# $return = $n;
# } elsif ($BRANCH == 1) {
# push @STACK, [ $BRANCH, $return, $n ];
# $n -= 2;
# $BRANCH = 0;
# next;
# } elsif ($BRANCH == 2) {
# $return += $s1;
# }
# }
# return $return unless @STACK;
# ($BRANCH, $s1, $n) = @{pop @STACK};
# $BRANCH++;
# }
def fib(n):
BRANCH = 0
STACK = []
while 1:
if n < 2:
_return = n
else:
if BRANCH == 0:
STACK.append([BRANCH, 0, n])
while n >= 2:
n =- 1
_return = n
elif BRANCH == 1:
STACK.append([BRANCH, _return, n])
n -= 2
BRANCH = 0
continue
elif BRANCH == 2:
_return += s1
if not STACK:
return _return
(BRANCH, s1, n) = STACK.pop()
BRANCH += 1
# sub fib {
# my $n = shift;
# my ($s1, $return);
# my $BRANCH = 0;
# my @STACK;
# while (1) {
# if ($n < 2) {
# $return = $n;
# } else {
# if ($BRANCH == 0) {
# push (@STACK, [ 1, 0, $n ]), $n -= 1 while $n >= 2;
# $return = $n;
# } elsif ($BRANCH == 1) {
# push @STACK, [ 2, $return, $n ];
# $n -= 2;
# $BRANCH = 0;
# next;
# } elsif ($BRANCH == 2) {
# $return += $s1;
# }
# }
# return $return unless @STACK;
# ($BRANCH, $s1, $n) = @{pop @STACK};
# }
# }
# NOTE: I got lazy/confused by the end of this chapter so
# so these last few "fib" functions are not tested
# But it was an interesting discussion on "unfolding"
# recursion.
def fib(n):
BRANCH = 0
STACK = []
while 1:
if n < 2:
_return = n
else:
if BRANCH == 0:
while n >= 2:
STACK.append([1, 0, n])
n =- 1
_return = n
elif BRANCH == 1:
STACK.append([2, _return, n])
n -= 2
BRANCH = 0
continue
elif BRANCH == 2:
_return += s1
if not STACK:
return _return
(BRANCH, s1, n) = STACK.pop()
Subscribe to:
Posts (Atom)
