Random Hacks

Haskell: What happens when you divide infinity by 2?

Posted by Eric Kidd Fri, 02 Feb 2007 22:00:00 GMT

Sometime back in elementary school, I first asked teachers, “What happens when you divide infinity by 2?” Some teachers couldn’t answer, and others told me, “It’s still infinity!”

More recently, a couple of friends were discussing a similar question at lunch: “What happens when you add 1 to infinity?”

Of course I said, “It’s still infinity!”, but I couldn’t explain it much better than my school teachers (at least not without using the word denumerable, which is a good way to ruin a lunch conversation).

And then tonight, while reading a paper about Haskell, I was hit by an evil idea: When in doubt, ask the Haskell interpreter!

Step 1: Counting

First, we need to teach Haskell about the natural numbers. (Why not use Haskell’s built-in integers? Just humor the crazy programmer for a moment, OK?)

A number is either zero, or the successor of another number. We can write that in Haskell as:

data Nat = Zero | Succ Nat
  deriving (Show, Eq, Ord)

Math geeks in the audience will recognize this as the Peano arithmetic. The “deriving” keyword tells Haskell to define show and the comparison operators for us.

Using this definition of Nat, we can now define some numbers:

one   = Succ Zero
two   = Succ one
three = Succ two
four  = Succ three

These work the way you’d expect:

*Main> three
Succ (Succ (Succ Zero))
*Main> two < three
True

OK, I threw in that last example just for fun.

Tags Hacks, Haskell, Math

Some useful closures, in Ruby

Posted by Eric Kidd Thu, 01 Feb 2007 18:36:00 GMT

Reginald Braithwaite has just posted a short introduction to closures in Ruby. Closures allow you to pass functions around your program, and build new functions from old ones.

Programming languages that support closures include Perl, Ruby, Python (sorta), Lisp, Haskell, Dylan, Javascript and many others.

The Dylan programming language included four very useful functions built using closures: complement, conjoin, disjoin and compose. The names are a bit obscure, but they can each be written in a few lines of Ruby.

Let’s start with complement:

# Builds a function that returns true
# when 'f' returns false, and vice versa.
def complement f
  lambda {|*args| not f.call(*args) }
end

We can use this to build the “opposite” of a function:

is_even = lambda {|n| n % 2 == 0 }
is_odd  = complement(is_even)

is_odd.call(1) # true
is_odd.call(2) # false

compose is another useful function:

# Builds a function which calls 'f' with
# the return value of 'g'.
def compose f, g
  lambda {|*args| f.call(g.call(*args)) }
end

We can use this to pass the output of one function to the input of another:

mult2 = lambda {|n| n*2 }
add1  = lambda {|n| n+1 }
mult2_add1 = compose(add1, mult2)

mult2_add1.call(3) # 7

The conjoin function is a bit more complicated, but still very useful:

# Builds a function which returns true
# whenever _every_ function in 'predicates'
# returns true.
def conjoin *predicates
  base = lambda {|*args| true }
  predicates.inject(base) do |built, pred|
    lambda do |*args|
      built.call(*args) && pred.call(*args)
    end
  end
end

We can use it to construct the logical “and” of a list of functions:

is_number = lambda {|n| n.kind_of?(Numeric) }
is_even_number = conjoin(is_number, is_even)

is_even_number.call("a") # false
is_even_number.call(1)   # false
is_even_number.call(2)   # true

The opposite of conjoin is disjoin:

# Builds a function which returns true
# whenever _any_ function in 'predicates'
# returns true.
def disjoin *predicates
  base = lambda {|*args| false }
  predicates.inject(base) do |built, pred|
    lambda do |*args|
      built.call(*args) || pred.call(*args)
    end
  end
end

This allows us to construct the logical “or” of a list of functions:

is_string  = lambda {|n| n.kind_of?(String) }
is_string_or_number =
  disjoin(is_string, is_number)

is_string_or_number.call("a") # true
is_string_or_number.call(1)   # true
is_string_or_number.call(:a)  # false

These were four of the first closure-related functions I ever used, and they’re still favorites today.

Feel free to post versions in other languages below!

Tags Hacks, Ruby

High-Performance Haskell

Posted by Eric Kidd Mon, 22 Jan 2007 08:32:00 GMT

Yesterday, I was working on a Haskell program that read in megabytes of data, parsed it, and wrote a subset of the data back to standard output. At first it was pretty fast: 7 seconds for everything.

But then I made the mistake of parsing some floating point numbers, and printing them back out. My performance died: 120 seconds.

You can see similar problems at the Great Language Shootout. Haskell runs at 1/2th the speed of C for many benchmarks, then suddently drops to 1/20th for others.

Here’s what’s going on, and how to fix it.

(Many thanks to Don Stewart and the other folks on #haskell for helping me figure this out!)

Tags Haskell, Performance

13 Ways of Looking at a Ruby Symbol

Posted by Eric Kidd Sat, 20 Jan 2007 03:20:00 GMT

New Ruby programmers often ask, “What, exactly, is a symbol? And how does it differ from a string?” No one answer works for everybody, so–with apologies to Wallace Stevens–here are 13 ways of looking at a Ruby symbol.

Tags Ruby

Selenium on Rails, Reloaded: Client-Side Tests in Ruby

Posted by Eric Kidd Wed, 15 Feb 2006 08:06:00 GMT

Like most Ruby on Rails developers, I write lots of test cases for my models and controllers. This lets me add new features quickly, without worrying about breakage: My test cases act as a safety net, warning me whenever existing code fails.

Sadly, it’s much harder to test client-side behavior. Sure, you know your controllers work, but what actually happens if a user clicks the Submit button? We need a better way to test the system end-to-end, including the actual JavaScript and web browsers.

This article shows how to combine Selenium, Selenium on Rails, and a custom patch to write client-side test cases in Ruby:

test.setup # Load fixtures
test.open :controller => 'customer',
          :action => 'list'
test.assert_title 'Customers'
test.click 'myLink', :wait => true
test.assert_title 'Customer: *'

These test cases actually run in your browser, loading pages and clicking links just as a user would. As the above example shows, you have full access to the Rails environment, including URL routing and configuration data.

Tags Hacks, Rails, Selenium, testing

Why Ruby is an acceptable LISP

Posted by Eric Kidd Sat, 03 Dec 2005 11:30:00 GMT

Years ago, I looked at Ruby and decided to ignore it. Ruby wasn’t as popular as Python, and it wasn’t as powerful as LISP. So why should I bother?

Of course, we could turn those criteria around. What if Ruby were more popular than LISP, and more powerful than Python? Would that be enough to make Ruby interesting?

Before answering this question, we should decide what makes LISP so powerful. Paul Graham has written eloquently about LISP’s virtues. But, for the sake of argument, I’d like to boil them down to two things:

1. LISP is a dense functional language.
2. LISP has programmatic macros.

As it turns out, Ruby compares well as a functional language, and it fakes macros better than I’d thought.

Tags LISP, Macros, Recommended, Ruby

Moving a blog to Typo

Posted by Eric Kidd Tue, 15 Nov 2005 22:13:00 GMT

This weekend, I moved Random Hacks to Typo, a nifty Rails-based blogging system. Here’s what I did:

• Set up my Mac for Rails development
• Pointed Typo at MySQL
• Created a custom theme
• Wrote an article importer
• Routed my old URLs to new locations
• Wrote some custom sidebars
• Configured Debian’s mod_fcgid

Now for the gruesome details.

Tags Rails, Ruby, Typo

Typo sidebars: Recent Comments and Tagged Articles

Posted by Eric Kidd Sun, 13 Nov 2005 21:04:00 GMT

Here's two new plugins for Typo, the cool Rails-based blogging software. The first shows a list of recent comments. The second shows articles with a specific tag. (I use it to implement the "Recommended Reading" list in my sidebar.)

To install the plugins, simply unzip them in your Typo root directory, restart Typo, and take a look at the "Sidebar" tab in the admin screen.

These plugins were unbelievably simple to write. If you'd like to see how they work, keep reading.

Tags Hacks, Rails, Typo

McCarthy's Ambiguous Operator

Posted by Eric Tue, 11 Oct 2005 00:00:00 GMT

Back in 1961, John McCarthy (the inventor of LISP) described an interesting mathematical operator called amb. Essentially, amb hates to be called with no arguments, and can look into the future to keep that from happening. Here's how it might look in Ruby.

Tags Continuations, Hacks, Recommended, Ruby

Random Hacks is back online

Posted by Eric Tue, 11 Oct 2005 00:00:00 GMT

I just recovered the contents of this site after a two-year hiatus. I'm going to try to dig up some other old stuff, too.

I should really rebuild this whole site using Ruby on Rails and some Ajax goodness. But that's going to have to wait until I ship some software at work and take care of other personal projects.

Tags Rails, Ruby