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.

Read more...

Tags , ,

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 ,

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.

Read more...

Tags , , ,

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.

Read more...

Tags , ,

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.

Read more...

Tags , , ,

15 Minutes and 150MB of RAM to Compare Unix and Linux

Posted by Eric Fri, 20 Jun 2003 00:00:00 GMT

SCO has recently made two accusations: (1) IBM has contributed IBM employees' code to Linux in violation of certain SCO/IBM contracts, and (2) some proprietary Unix code has somehow been illegally contributed to Linux. I'm not qualified to comment on whether or not IBM owns the code IBM wrote--though on behalf of software authors everywhere, I hope IBM does. However, I've written a tool which will allow SCO to find any code shared between Linux and Unix in about 15 minutes. What SCO does with this tool is up to them.

Read more...

Tags

Bayesian Whitelisting: Finding the Good Mail Among the Spam

Posted by Eric Sun, 29 Sep 2002 00:00:00 GMT

The biggest challenge with spam filtering is reducing false positives--that is, finding the good mail among the spam. Even the best spam filters occasionally mistake legitimate e-mail for spam. For example, in some recent tests, bogofilter processed 18,000 e-mails with only 34 false positives. Unfortunately, several of these false positives were urgent e-mails from former clients. This unpleasant mistake wasn't necessary--the most important of these false positives could have been avoided with an automatic whitelisting system.

Read more...

Tags , , , ,

How To Test a Trainable Spam Filter

Posted by Eric Sun, 22 Sep 2002 00:00:00 GMT

Ever since Paul Graham published A Plan for Spam, "trainable" spam filters have become the latest fashion. These filters train themselves to know the characteristics of your personal e-mail. Supposedly, this extra knowledge allows them to make fewer mistakes, and makes them harder to fool. But do these filters actually work? In this article, I try out Eric Raymond's bogofilter, a trainable Bayesian spam filter, and describe the steps required to evaluate such a filter accurately.

Read more...

Tags , ,

Why Hygienic Macros Rock

Posted by Eric Fri, 13 Sep 2002 00:00:00 GMT

I've recently been reading a lot of excellent essays on programming language design by Paul Graham. Paul and I agree about a number of things: (1) LISP is beautiful and powerful family of languages, even by modern standards, (2) all existing dialects of LISP are lacking a certain something, and (3) programmatic macros are a Good Idea.

Read more...

Tags , , ,