Ruby

Ruby unterstützt neben objektorientiertem Programmieren auch die funktionale Programmierung, wobei Funktionen höherer Ordnung, wie zum Beispiel map, ein zentraler Bestandteil von Ruby sind. Des Weiteren besitzen viele Klassen weitere Methoden, die für Monaden-Implementierungen von Interesse sind. So haben die Klassen Array und Set eine flatten-Methode, die verschachtelte Datenstrukturen zusammenkonkatenieren können. Da bind mathematisch aus den beiden Funktionen map und join aufgebaut ist, gibt es in Ruby eine Implementierung für Set und Array, die auf diesen beide Funktionen aufbaut.

Die Ruby Syntax im Überblick

Einige Elemente in der Syntax von Ruby sind etwas ungewöhnlich und benötigen einer Erklärung: Membervariablen von Klassen werden mit einem @-Präfix gekennzeichnet. Die Definition einer Funktion hat eine ähnliche Syntax wie in Python:

1
2
3

def hello(name)
	puts name
end

Puts schreibt einen String auf die Konsole. Um alle Elemente eines Arrays auszugeben, wird in Ruby die Funktion höherer Ordnung mit dem Namen each aufgerufen:

1
2
3
4

ary = [1,2,3,4,5]
ary.each { |i|
	puts i
}

Der Parameter von each ist ein so genannter Block, der in diesem Fall einen Parameter i hat. Weil Blöcke in Ruby nur für den direkten Aufruf in Funktionen höherer Ordnung designed worden sind, ist es sinnvoll, diese in Lambda-Ausdrücke einzuwickeln. Die Funktion lambda bietet genau diese Funktion an. Anschließend können diese Lambda-Ausdrücke mit einer speziellen Syntax mit eckigen Klammern ausgeführt werden

1
2

func = lambda {|x| x + 1}
func[41]

Monadengesetze

Dies sind die Monadengesetze in der Syntax von Ruby:

1
2
3

m.class.unit[x].bind[f] == f[x]
x.bind[m.class.unit] == x
x.bind[f].bind[g] == x.bind[lambda {|y| f[y].bind[y]}]

Ruby ist stark objektorientiert, unser Typ ist also eine Klasse m, die eine Konstruktorfunktion unit und eine bind-Funktion anbietet. Die objektorientierte Methoden-Notation in Ruby erlaubt es, den Bind-Operator in der Infixnotation zu verwenden.

Lazy Identitätsmonade in Ruby

Die Lazy Identitätsmonade ist eine Abwandlung der Identitätsmonade in der Hinsicht, dass eine Auswertung der zusammengebundenen Funktionen erst stattfindet, wenn diese explizit angefordert wird. Diese Auswertung kann zu einem beliebigen Zeitpunkt gestartet werden. Da Ruby keine strikte funktionale Programmiersprache ist, können in den explizit angestoßenen Auswertungen Nebeneffekte auftreten, die sich bei mehrfacher Auswertung anders verhalten.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Id
	def initialize(lam)
		@v = lam
	end

	def force # :: Id a -> a
		@v[]
	end

	def self.unit # a -> Id a
		lambda {|x| Id.new(lambda { x })}
	end

	def bind # :: Id a -> (a -> Id b) -> Id b
		x = self
		lambda {|f| f[x.force]}
	end
end

Um eine Lazy-Auswertung der Monade zu erhalten, wird in der unit-Methode jedes x in einen Lambda-Ausdruck eingewickelt. X wird so zu einem Ausdruck ohne Parameter, der x als Ergebnis liefert.

Force extrahiert dann aus unserem Lambda-Ausdruck dann das Ergebnis der Berechnung. Force hat den Typ:

1

force :: Id a -> a

Die Implementierung von Force startet die Auswertung von dem in @v gespeicherten Ausdruck.

Hacks für die bind-Funktion

Da Ruby in der Aufrufsyntax zwischen normal definierten Funktionen und Lambda-Ausdrücken unterscheidet, können Funktionen nicht wie Lambda-Ausdrücke aufgerufen werden. Zusätzlich gibt es Unterschiede, ob zwischen dem Funktionsnamen und den Parametern ein Leerzeichen steht:

* In dieser Syntax wird func ohne Parameter ausgeführt und anschließend wird das Ergebnis als Lambda-Ausdruck interpretiert.

Um überall konsistent bind aufrufen zu können, wird eine Aufruf-Syntax benötigt, die sowohl für normal definierte Funktionen als auch für Lambda-Ausdrücke funktioniert. Es stellt sich heraus, dass func[x] genau das liefert, wenn normale Funktionen keinen Parameter erwarten und einen Lambda-Ausdruck als Ergebnis liefern.

Anwendung

Diese Monade kann wie folgt verwenden werden:

1
2

x = Id.new(lambda {20}).bind[lambda {|x| puts x; Id.unit[x * 2]}]
x.force

Erst wenn x.force aufgerufen wird, schreibt puts x die 20 auf die Konsole. D.h. wir können Code-Blöcke erzeugen und sie erst zu einem bestimmten, frei wählbaren, Zeitpunkt ausführen. Dies entspricht der Lazy Semantik.

Set-Monade

Die Set-Monade ist so in Haskell nicht möglich, weil in Haskell die bind-Funktion für alle a gelten muss. Die Werte von Set müssen aber Ord implementieren. Da das Typkonzept von Ruby anders als das von Haskell ist und die Typen erst zur Laufzeit überprüft werden, kann die Set-Monade in Ruby mit den vorhandenen Mitteln implementiert werden:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

require "set"
class Set
	def self.unit # :: a -> Set a
		lambda {|x|
			Set.new [x]
		}
	end

	def bind # :: Set a -> ( a -> Set b ) -> Set b
		s = self
		lambda { |f|
			Set.new(self.map(&f).map{|x| x.map{|y|y}}.flatten(1))
		}
	end
end

Die map-Funktion der Set-Klasse hat eine etwas ungewöhnliche Signatur:

1

map :: Set a -> (a -> b) -> Array b

Die Ergebnisse von map müssen daher anschließend wieder in ein Set umgewandelt werden, um eine typkompatibele Signatur von bind zu erhalten. Außerdem ist es nicht möglich, die flatten-Funktion von der Set-Klasse zu verwenden, weil diese im Gegensatz zur flatten-Funktion von Array keinen Parameter für die Anzahl der zu konkatenierenden Hierarchiestufen hat und daher beliebig verschachtelte Sets zu einem Set zusammenfaltet. Daher wandelt die bind-Funktion der Set-Monade die Sets zuerst in Arrays um, flattet eine Hierarchiestufe zusammen, um dann anschließend das Ergebnis wieder in ein Set umzuwandeln.

Die Set-Monade kann für Berechnungen verwendet werden, die mehr als ein Ergebnis liefern, aber in denen keine doppelten Ergebnisse entstehen sollen. Wo in der Listenmonade doppelte Ergebnisse auftauchen, die dann für weitere Berechnungen verwendet werden, filtert die Set-Monade in jedem Berechnungsschritt überflüssige Ergebnisse heraus. Zu beachten ist aber, dass die Reihenfolge der Ergebnisse undefiniert ist.

Dies ist ein Beispiel, wie die Set-Monade in Ruby verwendet werden kann:

1
2

s = Set.new [1,2,3]
s.bind[lambda {|x| Set.new [x,x+1,x+10]}]

Die drei Ergebnisse

1

[[1, 2, 11], [2, 3, 12], [3, 4, 13]]

werden dann zusammengefasst:

1

[1, 2, 3, 4, 11, 12, 13]

Funktionen für Monaden

Wir können jetzt Funktionen bauen, die für alle Monaden gelten. In Ruby wird dafür ein Mixin verwendet, mit dem dann beliebige Klassen erweitert werden können.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

module Monad
	I = lambda {|x| x }

	# Structure-preserving transform that applies the given function
	# across the monad environment.
	def map
		lambda {|f|
			bind[lambda {|x| self.class.unit[f[x]] }]
		}
	end

	# Joins a monad environment containing another into one environment.
	def flatten
		bind[I]
	end

	# Applies a function internally in the monad.
	def ap
		lambda {|x|
			liftM2[I,x]
		}
	end

	# Binds a binary function across two environments.
	def liftM2
		lambda {|f, m|
			bind[lambda {|x1|
				m.bind[lambda {|x2|
					self.class.unit[f[x1,x2]]
				}]
			}]
		}
	end
end

Wenn bind und unit für eine Klasse in Ruby definiert sind, liefert dieses Mixin Funktionen wie map oder flatten, die ein konsistentes Verhalten bieten. Um dieses Mixin zu verwenden, wird ein include Statement benutzt:

1
2
3
4

import Monad.rb
class Set
	include Monad
end