Mumuki(2)

The programming blog of James Whiteman

Monday, September 20, 2010

Quicksort in PHP

Tonight I decided to write a Quicksort in PHP. Thank you Zend for create_function because Ruby has made me hopelessly closure dependent. Once I figured out that array_filter could take a lambda instead of a string I knew that it was on.

<?php
function qsort($l) {
  if (is_array($l) && empty($l)) { return array(); }
  list($car, $cdr) = array(array_shift($l), $l);
  return array_merge(
     qsort(array_filter($cdr, create_function('$e', "return \$e <= $car;"))), 
     array($car), 
     qsort(array_filter($cdr, create_function('$e', "return \$e > $car;")))
  );
}
?>

And I was pleased to see that I could, more or less, emulate Ruby's select/find iterator:

// Ruby
cdr.select { |x| x <= car }

/* in PHP */
<?php array_filter($cdr, create_function('$e', "return \$e <= $car;")); ?>


"But is it fast, Jim", you ask with baited breath. No. It could hardly be slower. PEAR has a nice little benchmarking package that will bring this point home (each sorting an array of 1000 random integers):

My Dumb Quicksort
time: 0.3607

PHP's built in sort
time: 0.0015

It isn't as nearly ugly as you'd expect it to be -- and still much easier to read than it would have been without the use of create_function. I'm always finding that I can do more with PHP than I thought I could.

Thursday, January 1, 2009

Home Made Continuations with Ruby

More functional experiments from yours truly. Upon review, I've realized that this code is quite tricky.

Here's the rub: Basically, evens_only_star_cc is a function that processes a gnarly data structure of nested lists (I designate these types of functions with 'star') using a collector (aka a continuation -- hence the cc in the function name). It could just as easily have been called evens_only.

A continuation in this context means that instead of using the call stack the normal way, I'm opting to just nest lambdas. That means that the function needs to be called with a lambda as one of the arguments. You can think of this lambda as the innermost doll in those nifty russian matryoshka doll sets. Each time the function recurs, it wraps the previous doll (lambda) in a new one. When the function reaches its termination point, we can either hand back our 'nested doll lambda call stack' thing as is, or we can apply it to its arguments and undwind it. I'm doing the latter here.

What we're doing is recurring through a crazy ass data structure of integers and collecting only the evens, while at the same time finding the sum of the odd numbers and the product of the even numbers. For sure, there are easier ways to do the same thing, but it's nice to put Ruby to the test every now and again. It's a great language.

The Code
def evens_only_star_cc(l, col)
if l.empty?
col.call [], 1, 0
elsif l.car.is_a? Fixnum
if l.car.even?
evens_only_star_cc l.cdr, ->(op, ep, os) {
col.call op.cons(l.car),
(ep * l.car),
os
}
else
evens_only_star_cc l.cdr, ->(op, ep, os) {
col.call op,
ep,
(os + l.car)
}
end
else
evens_only_star_cc l.car, ->(nop, nep, nos) {
evens_only_star_cc l.cdr, ->(op, ep, os) {
col.call op.cons(nop),
(ep * nep),
(os + nos)
}
}
end
end

Usage
evens_only_star_cc([1, [2, [3]], 4, [[[5]]], 6, [7, [8]], 9, 10],  ->(output, poe, soo) { 
{:output => output, :product_of_evens => poe, :sum_of_odds => soo}
})

Preliminaries
class Array
def car
first
end

def cdr
self[1..-1]
end

def cons(s)
self.unshift s
end
end

class Fixnum
def even?
(self % 2) == 0
end
end

Monday, December 15, 2008

Ruby: throw/catch vs callcc

More diversions. I earlier stated that this code should be readily understood by intermediate Rubyists. That is false, actually. The code is difficult. Not because it's using advanced Ruby, but because it's using Ruby in a very non standard way. rember_upto_last stands for "remove member upto last". 'a' stands for any atom (perhaps an integer or a symbol or a char). 'lat' stands for list-of-atoms (a simple array of atoms).

rember_upto_last
# if the atom is not in the list we simply return the list.
rember_upto_last 'a', %w(x y z)
=> %w(x y z)

# if the atom is in the list, we only return everything
# after the atom.
rember_upto_last 'a', %w(x y z a b c)
=> %w(b c)

# if the atom exists in multiple places, then we only
# return everything after the last instance of the atom.
rember_upto_last 'a', %w(x y z a b c a p q)
=> %w(p q)

version using throw/catch
# with try/catch
def rember_upto_last(a, lat)
result = catch(:jump!) do
r = lambda do |l|
if l.empty?
[]
elsif l.first == a
throw :jump!, r.call(l[1..-1])
else
cons l.first, r.call(l[1..-1])
end
end

r.call(lat)
end
end

version using callcc
# with callcc
def rember_upto_last(a, lat)
result = callcc do |c|
yComb do |f|
lambda do |l|
if l.empty?
[]
elsif l.first == a
c.call f.call(l[1..-1])
else
cons l.first, f.call(l[1..-1])
end
end
end.call(lat)
end
end

helpers
def cons(a, b)
b.unshift a
end

def yComb
lambda { |f|
f[f]
}.call(
lambda { |f| yield lambda { |x| f[f][x] } }
)
end

Friday, September 26, 2008

Beware Herd Thinking in Design Patterns

I was reading Object Design a few months back and came upon an example illustrating Double Dispatch. The example was showing a simple way to model Rock, Paper, Scissors. Here is the code translated to Ruby from Java:

class Rock
def beats?(obj)
obj.loses_to_rock?
end

def loses_to_rock?; false; end
def loses_to_paper?; true; end
def loses_to_scissors?; false; end
end

class Paper
def beats?(obj)
obj.loses_to_paper?
end

def loses_to_rock?; false; end
def loses_to_paper?; false; end
def loses_to_scissors?; true; end
end

class Scissors
def beats?(obj)
obj.loses_to_scissors?
end

def loses_to_rock?; true; end
def loses_to_paper?; false; end
def loses_to_scissors?; false; end
end
Programmers with some experience with metaprogramming may instinctively feel uneasy with this code. I mean, it looks like a pattern. And we know that if we wished to extend the game, then we're obligated to add another boxy class with all of those silly `loses_to...` methods.

Here's a much better way:

# this makes me happy :)
class Piece
class << self
def beats(*args)
class_eval do
define_method(:beats) do
args.map { |s| Object.const_get(s.to_s.capitalize) }
end
end
end
end

def beats?(opp)
beats.include? opp.class
end
end

class Rock < Piece
beats :scissors
end

class Scissors < Piece
beats :paper
end

class Paper < Piece
beats :rock
end


In this way, it is trivial to extend the game:

class JamesWhiteman < Piece
beats :paper, :scissors, :rock
end

# ok, let me instantiate myself...
james_whiteman = JamesWhiteman.new

# and time to start kicking some ass :)
james_whiteman.beats? Rock.new
=> TRUE

james_whiteman.beats? Paper.new
=> TRUE

james_whiteman.beats? Scissors.new
=> TRUE

Meta Programming 101: A Compression Macro

Here is another small (and hopefully instructive) example I came up with to help you grok meta programming. Any subclass of Bar will have a `compress` class method (aka ruby-style macro).

require 'zlib'

class Bar
class << self
def compress(*args)
args.each do |id|
module_eval <<-"end;"
alias_method :__#{id.to_i}__, :#{id.to_s}
private :__#{id.to_i}__
def #{id.to_s}(*args, &block)
Zlib::Deflate.deflate(__#{id.to_i}__(*args, &block), Zlib::BEST_COMPRESSION )
end
end;
end
nil # let's not return anything
end
end
end


class Foo < Bar

def output
('a'..'z').to_a.join * 500
end
compress :output

end

Tuesday, September 16, 2008

Creating Random Usernames and Passwords with Ruby

NUMBER_OF_USERNAME_PASSWORDS = 10_000
LENGTH = 8

passwords = Hash[
*Array.new(NUMBER_OF_USERNAME_PASSWORDS) do
proc { |n| Array.new(n) { (97..122).to_a[ rand(26) ].chr }.join }[LENGTH]
end
]


In this case, the variable passwords will be a hash of { :usernames => :passwords }.

Monday, September 8, 2008

PHP: A Language Full of Ceremony

Porting some of the previous post into PHP:
<?php
class SillyReverse {

private $string;


function __construct($s) {
$this->string = $s;
}


function reverse() {
return $this->reverse_helper($this->string);
}


private function reverse_helper($string) {
if ($this->is_midpoint($string)) {
return $string;
} else {
return $this->last_char($string) .
$this->reverse_helper($this->middle($string)) .
$this->first_char($string);
}
}


private function is_midpoint($string) {
return strlen($string) == 0 || strlen($string) == 1;
}


private function last_char($string) {
return $string[strlen($string)-1];
}


private function first_char($string) {
return substr($string, 0, 1);
}


private function middle($string) {
return substr($string, 1, -1);
}
}


$sr = new SillyReverse('hello, world');
print $sr->reverse() . "\n";

?>

Wednesday, August 27, 2008

Reversing Strings in Ruby: Two Different Kinds

Admittedly, reversing a string in Ruby is as easy as string.reverse. But for the sake of code katas (and preparing for Ruby job interviews) it's sometimes worth the effort to roll your own. Here are two different ways that I came up with.

A smarter way (while not using C)
class String

# reversing in place
def reverse_i!
(0...midpoint).each do |i|
self[i], self[-(i+1)] = self[-(i+1)], self[i]
end

self
end

private

def midpoint
self.size / 2
end

end

A very pretty way (but would get you fired!)
def reverse(s)
if s.midpoint?
s
else
s.last + reverse(s.middle) + s.first
end
end

### helpers ###
def midpoint?
self.size == 0 or
self.size == 1
end

def first; self[0].chr end

def middle; self[1...-1] end

def last; self[-1].chr end

Saturday, August 16, 2008

More Hitchens

"The essence of the independent mind lies not in what it thinks, but in how it thinks."

-- Christopher Hitchens

Thursday, June 26, 2008

A Y-Combinator for Josh Susser

A couple of days ago Josh Susser posted a very attractive recursive lambda in his blog.

A couple of people in the comments said that a recursive lambda is a prime opportunity to use the Y-combinator.

In Scheme? Sure. In a Rails application? I don't think so.

While I think that functional programing represents a more powerful programming paradigm than what's typically used in Ruby, I think it's a mistake to parade Ruby around like it's Lisp (or Haskell, or ML, etc). It can 'do' Lisp (sans macros) but it's so much better at being itself.

Anyhoo, I whipped this thing up just to see what it would look like. I started writing in Ruby 1.9, but for some reason, when you coerce a lambda into a block (i.e function(& my_lambda)) it turns hash iterations (i.e |key,value|) into arrays ( |array| ). So I did it in 1.8 -- for which lambda syntax sucks. So I'm going to use &lambda instead of lambda 'cuz it just looks good.

class ApplicationController < ActionController::Base
before_filter { |controller| controller.params.each(&λ { |le|
λ {|f|
f[f]
}.call( λ {|f| le.call( λ { f[f] }) })
}.call(λ {|m|
λ {|k,v|
case v
when String then v.remove_accents!
when Hash then v.each(&m.call)
end
}
}))
}
end

Well...it is completely anonymous now. Are we having fun yet? Obviously, there are more readable ways to use Y but none of them result in anything nicer than what Josh wrote. This is basically a long way of saying avoid overly complicated code. You can never justify masturbatory programming because you're using strict FP -- especially in Ruby and even more so in Rails.

Sunday, April 27, 2008

Smalltalk Best Practice Patterns

"Coding is where your fuzzy comfortable ideas awaken in the harsh dawn of reality."

-- Kent Beck

Tuesday, April 22, 2008

Testing #new in Ruby with RSpec and Mocha

Here's a trick I came up with:
class Foo
def initialize
my_nifty_init_method
end
end

describe Foo, "#new" do
it "should call my_nifty_init_method" do
f = Foo.allocate
f.expects(:my_nifty_init_method).returns(true)
f.send(:initialize)
end
end

Class#allocate creates an object without calling initialize. Pretty cool stuff.

Saturday, May 26, 2007

Programming Erlang

Just got the PDF to Programing Erlang a few weeks ago. Erlang is a functional language, and, from what I can tell, is even more terse than Scheme. The book has a very nice and very compact Quicksort in the second chapter. Here's my version in Ruby:
def qsort(l) 
return [] if l.empty?
car, *cdr = l
qsort(cdr.select { |x| x <= car }) +
[car] +
qsort(cdr.select { |x| x > car })
end

Not nearly as nice as the one in the book, but still pretty small. I borrowed 'car' and 'cdr' from the Little Schemer...I suppose 'first' and 'rest' would have been more readable. The Erlang book users 'Pivot' and 'L'. All in all, a very good book so far.

About Me

I develop applications in Ruby and PHP.