Saturday, December 09, 2006

How Arrays Work In Ruby

WKC CCC wrote:

> unknown wrote:
> > WKC CCC wrote:
> >
> >>
> >> count = count + 1
> >> end
> >>
> >> puts one.inspect
> >
> > Array.new(array) copies the *array* but it does not copy its *elements*.
> > So tempArr[0] is another name for the very same object as one[0], and so
> > forth. m.
>
> If they are referring to the same object, why is it when
>
> tempArr = Array.new(one)
> one.clear
>
> results in tempArr still having the values originally assigned to array
> one?

Reread what I said. I didn't say that tempArr and one refer to the same
object; I said that tempArr[0] and one[0] (and so on) refer to the same
object.

Think of it this way. Items in an array are dogs. Arrays are people
holding leashes. Anyone can attach a leash to a dog. So I (tempArr) can
have a leash on Fido, and so can you (one). If you let go of your leash
(one.clear), Fido is still Fido; you just don't have a leash on him. But
if you cut off one Fido's legs (modify one[0]), that leg on my Fido
(tempArr[0]) is also cut off, because they are the same Fido.

m.

--
matt neuburg, phd = matt@tidbits.com, http://www.tidbits.com/matt/
Tiger - http://www.takecontrolbooks.com/tiger-customizing.html
AppleScript - http://www.amazon.com/gp/product/0596102119
Read TidBITS! It's free and smart. http://www.tidbits.com

Tuesday, December 05, 2006

Monads in Ruby Part 2: Maybe (then again Maybe not)

So here's when things start to get interesting. Today I'm going to discuss the maybe monad. In Haskell, the maybe type is used for computations that might fail. An example of this in ruby would be the #index method on arrays. In ruby index returns either the index of the passed in item in the array, or nil if the item is not in the array. Haskell is statically typed so variables can only hold one type of data. This means we can't return a 3 or a nil. Instead we have the maybe type which looks like data Maybe a = Just a | Nothing . So index would return a Maybe Integer. e.g:

index "hello" ["world", "planet", "hello", "hi"] --> Just 2
index 25 [3,4,5] --> Nothing


What does this have to do with monads you may be wondering? Well, just like identity, the maybe type is a monad. In fact maybe is a monad with some extra features, an instance of MonadPlus. We'll come back to that. But first a detour in ruby land. You may have seen something like this:

class NilClass
def method_missing(*args, &block)
nil
end
end

This is sometimes called the null pattern, and it makes Ruby's nil act like Objective-C's. That is, nil will just swallow messages it doesn't understand. The general opinion among the ruby community is that this is a Bad Idea (tm). I would tend to agree with that idea. It's also not as useful as it might initially appear, consider 1 + nil.

This pattern however is superficially similar to how Maybe works in Haskell as a monad. I mentioned earlier that maybe was an instance of MonadPlus. This means it supports two additional operations, mzero and mplus. mzero, acts as you might guess from it's name as a zero. mzero mplus anything will always be the anything. Likewise if you think of the bind operation (discussed last time) as a sort of multiplication, mzero bind f will always be mzero. For the maybe monad, Nothing is mzero.

So if I define

class Array
def maybe_index( obj )
i = index( obj )
if i
Maybe.Just( i )
else
Maybe.Nothing
end
end
end


I can now change the first 3 in an array for instance into a 4, with no need for error checking:

a = [1,3,5]
b = Maybe.m_bind( a.maybe_index( 3 ) ) { |i| a1 = a.dup; a1[ i ] += 1; Maybe.m_return( a1 ) }


So b will either be Just [1,4,5] or Nothing. Either way, we had no opportunity to index an array by nil, and no need to litter our code with if statements. (What we did litter our code with was quite a bit more verbose, but you win some you lose some.)

Now, you must be wondering, what about this mplus business? Well let's same you need to address someone. If you know their nickname, you'd like to use that, if you don't know their nickname, you'd like to use their first name, and if you don't know their first name, you'd like to use their last name (which you know you'll always have). So how do we do this? We get all three and mplus the results together:

class Hash
def maybe_fetch( key )
if has_key? key
Maybe.Just(self[key])
else
Maybe.Nothing
end
end
end

person1 = { :nick => 'Big Joe', :first => 'Joseph', :last => 'Smith' }
person2 = { :last => 'Baggins' }

greeting1 = Maybe.mplus( Maybe.m_bind( person1.maybe_fetch( :nick ) ) { |nick| Maybe.m_return("Hey, #{nick}") },
Maybe.mplus( Maybe.m_bind( person1.maybe_fetch( :first ) ) { |first| Maybe.m_return("Hi, #{first}") },
Maybe.m_bind( person1.maybe_fetch( :last ) ) { |last| Maybe.m_return("Hello, Mr. #{last}") }))

puts greeting1.from_just

greeting2 = Maybe.mplus( Maybe.m_bind( person2.maybe_fetch( :nick ) ) { |nick| Maybe.m_return("Hey, #{nick}") },
Maybe.mplus( Maybe.m_bind( person2.maybe_fetch( :first ) ) { |first| Maybe.m_return("Hi, #{first}") },
Maybe.m_bind( person2.maybe_fetch( :last ) ) { |last| Maybe.m_return("Hello, Mr. #{last}") }))

puts greeting2.from_just



This is similar to something likep1[:nick] || p1[:first] || p1[:last] in your standard ruby idiom, but note how I also transformed each value differently. And this code won't misevaluate due to things like nil being false or "" being true. The effect is localized entirely to the semantics you give it. This also means that you won't easily run into the major problem of the null pattern in that it runs away with you. It's very easy to contain this to a small section of code.

Before I post the code, I'm going to make one small note. I've decided not to bother with writing "type-safe" versions of this monads anymore. a) They aren't really type-safe anyway and b) classes aren't types, especially not in Ruby. It's a losing battle, so I think that to use monads in ruby you'll unfortunately have to rely more on self-discipline and less on type-checking.


class Maybe
def initialize(*args)
if args.length > 1
raise ArgumentError, "Expected 0 or 1 arguments, got #{args.length}"
end

@nothing = args.empty?
@val = args.first
end

def nothing?
@nothing
end

def from_just
raise "Maybe pattern match failure" if nothing?
@val
end

def self.Just( v )
new(v)
end

def self.Nothing
new
end
end

# Monad stuff
class Maybe
def self.m_bind(maybe_a)
if maybe_a.nothing?
Maybe.Nothing
else
yield(maybe_a.from_just)
end
end

def self.m_return(v)
Maybe.Just v
end

def self.mplus(a, b)
if a.nothing?
b
else
a
end
end
end

Sunday, December 03, 2006

Monads In Ruby Part 1.5: Identity

So after chatting in #haskell on freenode it became apparent that my Identity monad was kind of a cheat. It wasn't a function from types to types. So I present here for comment, a modified version, that pretends that ruby has parametric types:

% cat identity.rb
$implementation_detail = {}
def Identity(klass)
$implementation_detail[klass] ||= Class.new do
define_method :initialize do |obj|
@obj = obj
end

define_method :m_bind do |f|
r = f.call( @obj )
raise TypeError, "Bind did not type check" unless r.kind_of? Identity(klass)
r
end

(class << self; self; end).class_eval {
define_method :m_return do |obj|
raise TypeError, "#{obj} not instance of #{klass}" unless obj.kind_of? klass
self.new( obj )
end

define_method :name do
"Identity(#{klass})"
end

alias_method( :to_s, :name )
alias_method( :inspect, :name )
}
end
end

p Identity(Array).m_return( [1, 2, 3] ).m_bind( lambda do |a|
Identity(Array).m_return( [3] + a[1..-1] )
end)




% ruby identity.rb
#<#:0x1eaff0 @obj=[3, 2, 3]>

Monads in Ruby Part 1: Identity

Just to get this out of the way, yes it's been done before: http://moonbase.rydia.net/mental/writings/programming/monads-in-ruby/00introduction.html

In order to better understand the various monads available in Haskell, I've been re-implementing them in Ruby. Thus far I've done Identity, List (well Array), Maybe and State. Today I'm going to show you the Identity monad. A monad is a framework of sorts for applying rules to a series of computations. A monad has at least two operations, bind and return. return takes a non monadic value and converts it to a monadic one, it has type:
(Monad m) => a -> m a
(I'm using Haskell type notation here because ruby doesn't have type notation ;) )

Bind takes a monadic value and de-monadifies it to feed it into a function that returns a monadic value. It has the type:
(Monad m) => m a -> (a -> m b) -> m b

Bind is where the magic happens. Haskell uses it's type system to ensure that every sequence of computations in a given monad goes through bind. Bind therefore lets the writer of the monad decide the rules for the little monadic world within a given program. (This is how Haskell deals with side-effects (IO) ).

So now without further ado, I present the Identity monad:

class Identity
def initialize( val )
@val = val
end

def self.m_return( a )
Identity.new( a )
end

def self.m_bind(id_a, &f)
f.call( id_a.val )
end

def val
@val
end
end


Short and sweet. All you can really do with an Identity monad is force evaluation order. Ruby is imperative so that doesn't really matter.

Here's some code using Identity:

Identity.m_bind( Identity.m_return( 1 ) ) do |x| # x is 1, we've sucked it out of the Monad.
Identity.m_return( x + 1 )
end


This is quite verbose. In Haskell it would be return 1 >>= (\x -> return x + 1), where >>= is bind and (\x -> ... ) is analogous to lambda { |x| ... }. Haskell also has some syntactic sugar for monadic expressions like this. Using the the syntactic sugar it would look like:


let i = return 1 in
do x <- i
return x + 1



The real difference of course is the type checking. If I wrote return 1 >>= (\x -> x + 1) in Haskell it would not compile where ruby cares not a whit if we want to escape our monads. That combined with the fact that unlike Haskell we have no syntactic sugar for monads means it's going to be difficult to debug our ruby implementations. Hopefully I've whet your appetite, next time we'll tackle the Maybe monad, that allows us to handle computations that might fail.