Monads in Ruby

Monads? Easy!

A Monad over X simply is a Monoid in the Category of Endofunctors of X.

Monads? Really!

  • Monads are a concept in mathematics
  • Algebra is an area of mathematics
  • Category theory is an abstraction of algebra.
  • Monads are defined in category theory
  • Remember: in category theory we talk about infinity beyond cardinality of infinite sets…
  • The „idea“ has been transplanted into something used in programming languages…
  • Just think of stars in terms of astronomy, in terms of decoration and in terms of music or movies

Monad as Design Pattern

  • Actually Monads should be viewed as a design pattern
  • That describes the level of abstraction

Motivation

  • Pure functional programmers are poor guys when it comes to state
  • State is evil
  • State is not possible or hard
  • I/O is state, actually a segment of the outer world is manipulated
  • Monads encapsulate that
  • Even if you are happy with state (poor IT theology…):
    Multilevel nil problem 🙁

Monads in Functional Programming

  • Container type
  • wrap(foo):
    • class method
    • can also be called unit
    • Btw. arrogant Haskell guys call it return
  • pass(&block)
    • instance method
    • Can also be called bind
  • Optionally more operations (mjoin, empty, +,…)

Identity Monad

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

def Identity.wrap(value)
  new(value)
end

class Identity
    def pass
        yield @value
    end
end

Axioms

  • Left-identity for pass:
    Calling pass on a newly wrapped value is the same as applying the block to that value
  • Right-identity for pass:
    Calling pass with a block that only calls wrap on its parameter results in the same as its target object
  • Nesting:
    Nesting pass blocks should be equivalent to calling them in sequence.

Does our Monad survive 1st law?

Identity.wrap(foo).pass do |value|
  f(value)
end

Is equivalent to

f(foo)

That is how we defined pass.

Does our Monad survive 2nd law?

bar.pass do |value|
  Identity.wrap(value)
end

Is equivalent to

bar

That is how we defined pass.

Does our Monad survive 3rd law?

bar.pass do |value_a|
    f(value_a)
end.pass do |value_b|
    g(value_b)
end

Is equivalent to

bar.pass do |value_a|
  f(value_a).pass do |value_b|
    g(valueb)
  end
end

That is how we defined pass.

Array as Monad

def Array.wrap(value)
    [ value ]
end

class Array
    def mjoin
        inject([]) { |combined, arr| combined + arr }
    end

    def pass(&block)
        map(&block).mjoin
    end
end

Does it work?

Have a look yourself…

More Monad Operations

Empty:

def Array::empty
    []
end

+:

Already there

Other Examples

  • Option (Some, None)

Links & Sources

This article is based on a speach given in the Ruby on Rails user group Switzerland.

Share Button

Residue Class Rounding

Deutsch

If you do not know what residue classes are, just read on, it will be explained to the extent needed later on.

The concept of rounding seems familiar, but let us try to grab it a little bit more systematically.

Let us assume a set M of numbers and a subset N \subseteq M of it, whose elements can be represented in the programming or software environment we are having in mind. We want to use a metric d : M \times M \rightarrow \Bbb R_+, (x, y) \mapsto r=d(x,y)>=0. Usually we have three requirements for d:

  • Identity of indiscernibles: d(x,y) = 0 \iff x = y
  • Symmetry: d(x,y)=d(y,x)
  • Triangular inquation: d(x,z) \le d(x,y) + d(y,z)

Usually the number that we are dealing with can be considered to be within the world of real or complex numbers, we can hence assume that M \subseteq \Bbb C, often even M \subseteq \Bbb R or if we are honest M \subseteq \Bbb Q. Then we are usually working with d(x,y) = |x-y|, which is kind of implicitly clear. If you do not know complex numbers, just think of real or even rational numbers, which is the most common case anyway. Off course the concepts for rounding of p-adic numbers are really interesting and beautiful, but since I do not want to explain p-adic numbers here, I will not extend on this issue.

What is our intuitive understanding of rounding?
Maybe just a map
r: M \rightarrow N, x \mapsto r(x),
that is chosen with certain constraints for each x in such a way that d(x, r(x)) is minimal.
We need the constraints to enforce uniqueness if multiple values y\in N with minimal d(x,y) exist. The classical case of rounding to integral numbers has to answer the question of how to round 0.5. If N is a subset of the real numbers, which is „usually“ the case, we have ordering. We can choose between the following constraints:

ROUND_UP
|r(x)|\ge |x| Z.B. r(0.4)=1 and r(0.5)=1 and r(-0.5)=-1
ROUND_DOWN
|r(x)|\le |x| Z.B. r(0.6)=0 and r(0.5)=0 and r(-0.5)=0
ROUND_CEILING
r(x) \ge x Z.B. r(0.4)=1 and r(0.5)=1 and r(-0.5)=0
ROUND_FLOOR
r(x) \le x Z.B. r(0.6)=0 and r(0.5)=0 and r(-0.5)=-1
ROUND_HALF_UP
Minimize d(r(x),x), but if multiple optimal values exist for r(x), pick the one furthest away from 0, for example r(0.4)=0 and r(0.6)=1 and r(0.5)=1 and r(-0.5)=-1
ROUND_HALF_DOWN
Minimize d(r(x),x), but if multiple optimal values exist for r(x), pick the one closest to 0, for example r(0.4)=0 and r(0.6)=1 and r(0.5)=0 and r(-0.5)=0
ROUND_HALF_CEILING
Minimize d(r(x),x), but if multiple optimal values exist for r(x), pick the largest, for example r(0.4)=0 and r(0.6)=1 and r(0.5)=1 and r(-0.5)=0
ROUND_HALF_FLOOR
Minimize d(r(x),x), but if multiple optimal values exist for r(x), pick the smallest, for example r(0.4)=0 and r(0.6)=1 and r(0.5)=0 and r(-0.5)=-1
ROUND_HALF_EVEN
Minimize d(r(x),x), but if multiple optimal values exist for r(x), pick the one with even last digit. Please observe that this constraint is useful in the classical case, but it cannot be generalized. For example: r(0.4)=0 and r(0.6)=1 and r(0.5)=0 and r(-0.5)=0 and (1.5)=2
ROUND_UNNECESSARY
This constraint does not work in the mathematical sense (or only with ugly abusive math formulas), but programmatically we can do that: We try r(x)=x and throw an exception if not x\in N.

Usually we are thinking in the decimal system (even though our computers prefer something else, but the computer should serve us and not vice versa..). So we pick a power of ten 10^n with n \in \Bbb N_0, so n \ge 0. Now we simply define
N = \{ x \in M : 10^n x \in \Bbb Z\},
which means that N contains all numbers of M with a maximum of n digits after the decimal point. This rounding works quite well with something like LongDecimal in Ruby or BigDecimal in Scala or Java, but BigDecimal offers fewer rounding modes than LongDecimal for Ruby.

Now we look at the residue class rounding. We assume such a power of ten 10^n. Then we need an integral number m \ge 2 and a set of numbers R \subseteq \{0,...,m-1\}, we call them residues. Now we define N = \{ x \in M : 10^n x \in {\Bbb Z} \wedge \bigvee_{r \in R} 10^n x \equiv r \mod{m}\}.
That means that if we fill the number with zeros to the given number of places after the decimal point, remove the decimal point and perform a division with residue of this number by m, the residue lies in R. In this case ROUND_HALF_EVEN can become difficult to implement and ambiguous, so we might need to sacrifice it. But even worse, we have to deal with the case that 0 is not in R and provide rules how to round 0. The candidates have self-explanatory names:

  • ZERO_ROUND_TO_PLUS
  • ZERO_ROUND_TO_MINUS
  • ZERO_ROUND_TO_CLOSEST_PREFER_PLUS
  • ZERO_ROUND_TO_CLOSEST_PREFER_MINUS
  • ZERO_ROUND_UNNECESSARY

An important application of this is m=10 and R=\{0, 5\}. This is used in Switzerland and probably other currency regions for rounding money amounts to multiples of 5 Rappen (0.05 CHF). This has already been described in „Rounding of Money Amounts„. If we have m=10 and R=\{0,1,2,3,4,5,6,7,8,9\} we have the usual non-CHF-rounding case. Maybe there are even cases for m=10 and R=\{0,2,4,6,8\}. But the concept is more general, if you like to use it.

Share Button

Rails 4.0 Beta

Rails 4.0 Beta. 😉

Share Button

Ruby 2.0 coming soon

This is a translation of Ruby 2.0 in Sicht

According to blade.nagaokaut.ac.jp Ruby 2.0 is almost finished. The new features are already known and a release 2.0.0-p0 is planned for Q1 2013.

Share Button