diff options
8 files changed, 1194 insertions, 0 deletions
diff --git a/modules/accumulators/src/examples/clojure/examples/accumulators.clj b/modules/accumulators/src/examples/clojure/examples/accumulators.clj new file mode 100644 index 00000000..e5c0d98d --- /dev/null +++ b/modules/accumulators/src/examples/clojure/examples/accumulators.clj @@ -0,0 +1,93 @@ +;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; +;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; +;; +;; Accumulator application examples +;; +;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; +;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; + +(ns + #^{:author "Konrad Hinsen" + :skip-wiki true + :doc "Examples for using accumulators"} + examples.accumulators + (:use [clojure.contrib.accumulators + :only (combine add add-items + empty-vector empty-list empty-queue empty-set empty-map + empty-counter empty-counter-with-total + empty-sum empty-product empty-maximum empty-minimum + empty-min-max empty-mean-variance empty-string empty-tuple)])) + +; Vector accumulator: combine is concat, add is conj +(combine [:a :b] [:c :d] [:x :y]) +(add [:a :b] :c) +(add-items empty-vector [:a :b :a]) + +; List accumulator: combine is concat, add is conj +(combine '(:a :b) '(:c :d) '(:x :y)) +(add '(:a :b) :c) +(add-items empty-list [:a :b :a]) + +; Queue accumulator +(let [q1 (add-items empty-queue [:a :b :a]) + q2 (add-items empty-queue [:x :y])] + (combine q1 q2)) + +; Set accumulator: combine is union, add is conj +(combine #{:a :b} #{:c :d} #{:a :d}) +(add #{:a :b} :c) +(add-items empty-set [:a :b :a]) + +; Map accumulator: combine is merge, add is conj +(combine {:a 1} {:b 2 :c 3} {}) +(add {:a 1} [:b 2]) +(add-items empty-map [[:a 1] [:b 2] [:a 0]]) + +; Counter accumulator +(let [c1 (add-items empty-counter [:a :b :a]) + c2 (add-items empty-counter [:x :y])] + (combine c1 c2)) + +; Counter-with-total accumulator +(let [c1 (add-items empty-counter-with-total [:a :b :a]) + c2 (add-items empty-counter-with-total [:x :y])] + (combine c1 c2)) + +; Sum accumulator: combine is addition +(let [s1 (add-items empty-sum [1 2 3]) + s2 (add-items empty-sum [-1 -2 -3])] + (combine s1 s2)) + +; Product accumulator: combine is multiplication +(let [p1 (add-items empty-product [2 3]) + p2 (add-items empty-product [(/ 1 2)])] + (combine p1 p2)) + +; Maximum accumulator: combine is max +(let [m1 (add-items empty-maximum [2 3]) + m2 (add-items empty-maximum [(/ 1 2)])] + (combine m1 m2)) + +; Minimum accumulator: combine is min +(let [m1 (add-items empty-minimum [2 3]) + m2 (add-items empty-minimum [(/ 1 2)])] + (combine m1 m2)) + +; Min-max accumulator: combination of minimum and maximum +(let [m1 (add-items empty-min-max [2 3]) + m2 (add-items empty-min-max [(/ 1 2)])] + (combine m1 m2)) + +; Mean-variance accumulator: sample mean and sample variance +(let [m1 (add-items empty-mean-variance [2 4]) + m2 (add-items empty-mean-variance [6])] + (combine m1 m2)) + +; String accumulator: combine is concatenation +(combine "a" "b" "c" "def") +(add "a" (char 44)) +(add-items empty-string [(char 55) (char 56) (char 57)]) + +; Accumulator tuples permit to update several accumulators in parallel +(let [pair (empty-tuple [empty-vector empty-string])] + (add-items pair [[1 "a"] [2 "b"]])) diff --git a/modules/condition/src/examples/clojure/examples/condition.clj b/modules/condition/src/examples/clojure/examples/condition.clj new file mode 100644 index 00000000..f0f2307e --- /dev/null +++ b/modules/condition/src/examples/clojure/examples/condition.clj @@ -0,0 +1,66 @@ +;; Copyright (c) Stephen C. Gilardi. All rights reserved. The use and +;; distribution terms for this software are covered by the Eclipse Public +;; License 1.0 (http://opensource.org/licenses/eclipse-1.0.php) which can +;; be found in the file epl-v10.html at the root of this distribution. By +;; using this software in any fashion, you are agreeing to be bound by the +;; terms of this license. You must not remove this notice, or any other, +;; from this software. +;; +;; clojure.contrib.condition.example.clj +;; +;; scgilardi (gmail) +;; Created 09 June 2009 + +(ns example.condition + (:use (clojure.contrib + [condition + :only (handler-case print-stack-trace raise *condition*)]))) + +(defn func [x y] + "Raises an exception if x is negative" + (when (neg? x) + (raise :type :illegal-argument :arg 'x :value x)) + (+ x y)) + +(defn main + [] + + ;; simple handler + + (handler-case :type + (println (func 3 4)) + (println (func -5 10)) + (handle :illegal-argument + (print-stack-trace *condition*)) + (println 3)) + + ;; multiple handlers + + (handler-case :type + (println (func 4 1)) + (println (func -3 22)) + (handle :overflow + (print-stack-trace *condition*)) + (handle :illegal-argument + (print-stack-trace *condition*))) + + ;; nested handlers + + (handler-case :type + (handler-case :type + nil + nil + (println 1) + (println 2) + (println 3) + (println (func 8 2)) + (println (func -6 17)) + ;; no handler for :illegal-argument + (handle :overflow + (println "nested") + (print-stack-trace *condition*))) + (println (func 3 4)) + (println (func -5 10)) + (handle :illegal-argument + (println "outer") + (print-stack-trace *condition*)))) diff --git a/modules/datalog/src/examples/clojure/examples/datalog.clj b/modules/datalog/src/examples/clojure/examples/datalog.clj new file mode 100644 index 00000000..4e1efbb8 --- /dev/null +++ b/modules/datalog/src/examples/clojure/examples/datalog.clj @@ -0,0 +1,116 @@ +;; Copyright (c) Jeffrey Straszheim. All rights reserved. The use and +;; distribution terms for this software are covered by the Eclipse Public +;; License 1.0 (http://opensource.org/licenses/eclipse-1.0.php) which can +;; be found in the file epl-v10.html at the root of this distribution. By +;; using this software in any fashion, you are agreeing to be bound by the +;; terms of this license. You must not remove this notice, or any other, +;; from this software. +;; +;; example.clj +;; +;; A Clojure implementation of Datalog - Example +;; +;; straszheimjeffrey (gmail) +;; Created 2 March 2009 + + +(ns examples.datalog + (:use [clojure.contrib.datalog :only (build-work-plan run-work-plan)] + [clojure.contrib.datalog.rules :only (<- ?- rules-set)] + [clojure.contrib.datalog.database :only (make-database add-tuples)] + [clojure.contrib.datalog.util :only (*trace-datalog*)])) + + + + +(def db-base + (make-database + (relation :employee [:id :name :position]) + (index :employee :name) + + (relation :boss [:employee-id :boss-id]) + (index :boss :employee-id) + + (relation :can-do-job [:position :job]) + (index :can-do-job :position) + + (relation :job-replacement [:job :can-be-done-by]) + ;(index :job-replacement :can-be-done-by) + + (relation :job-exceptions [:id :job]))) + +(def db + (add-tuples db-base + [:employee :id 1 :name "Bob" :position :boss] + [:employee :id 2 :name "Mary" :position :chief-accountant] + [:employee :id 3 :name "John" :position :accountant] + [:employee :id 4 :name "Sameer" :position :chief-programmer] + [:employee :id 5 :name "Lilian" :position :programmer] + [:employee :id 6 :name "Li" :position :technician] + [:employee :id 7 :name "Fred" :position :sales] + [:employee :id 8 :name "Brenda" :position :sales] + [:employee :id 9 :name "Miki" :position :project-management] + [:employee :id 10 :name "Albert" :position :technician] + + [:boss :employee-id 2 :boss-id 1] + [:boss :employee-id 3 :boss-id 2] + [:boss :employee-id 4 :boss-id 1] + [:boss :employee-id 5 :boss-id 4] + [:boss :employee-id 6 :boss-id 4] + [:boss :employee-id 7 :boss-id 1] + [:boss :employee-id 8 :boss-id 7] + [:boss :employee-id 9 :boss-id 1] + [:boss :employee-id 10 :boss-id 6] + + [:can-do-job :position :boss :job :management] + [:can-do-job :position :accountant :job :accounting] + [:can-do-job :position :chief-accountant :job :accounting] + [:can-do-job :position :programmer :job :programming] + [:can-do-job :position :chief-programmer :job :programming] + [:can-do-job :position :technician :job :server-support] + [:can-do-job :position :sales :job :sales] + [:can-do-job :position :project-management :job :project-management] + + [:job-replacement :job :pc-support :can-be-done-by :server-support] + [:job-replacement :job :pc-support :can-be-done-by :programming] + [:job-replacement :job :payroll :can-be-done-by :accounting] + + [:job-exceptions :id 4 :job :pc-support])) + +(def rules + (rules-set + (<- (:works-for :employee ?x :boss ?y) (:boss :employee-id ?e-id :boss-id ?b-id) + (:employee :id ?e-id :name ?x) + (:employee :id ?b-id :name ?y)) + (<- (:works-for :employee ?x :boss ?y) (:works-for :employee ?x :boss ?z) + (:works-for :employee ?z :boss ?y)) + (<- (:employee-job* :employee ?x :job ?y) (:employee :name ?x :position ?pos) + (:can-do-job :position ?pos :job ?y)) + (<- (:employee-job* :employee ?x :job ?y) (:job-replacement :job ?y :can-be-done-by ?z) + (:employee-job* :employee ?x :job ?z)) + (<- (:employee-job* :employee ?x :job ?y) (:can-do-job :job ?y) + (:employee :name ?x :position ?z) + (if = ?z :boss)) + (<- (:employee-job :employee ?x :job ?y) (:employee-job* :employee ?x :job ?y) + (:employee :id ?id :name ?x) + (not! :job-exceptions :id ?id :job ?y)) + (<- (:bj :name ?x :boss ?y) (:works-for :employee ?x :boss ?y) + (not! :employee-job :employee ?y :job :pc-support)))) + + + +(def wp-1 (build-work-plan rules (?- :works-for :employee '??name :boss ?x))) +(run-work-plan wp-1 db {'??name "Albert"}) + +(def wp-2 (build-work-plan rules (?- :employee-job :employee '??name :job ?x))) +(binding [*trace-datalog* true] + (run-work-plan wp-2 db {'??name "Li"})) + +(def wp-3 (build-work-plan rules (?- :bj :name '??name :boss ?x))) +(run-work-plan wp-3 db {'??name "Albert"}) + +(def wp-4 (build-work-plan rules (?- :works-for :employee ?x :boss ?y))) +(run-work-plan wp-4 db {}) + + +;; End of file diff --git a/modules/miglayout/src/examples/clojure/examples/miglayout.clj b/modules/miglayout/src/examples/clojure/examples/miglayout.clj new file mode 100644 index 00000000..04c9a040 --- /dev/null +++ b/modules/miglayout/src/examples/clojure/examples/miglayout.clj @@ -0,0 +1,60 @@ +;; Copyright (c) Stephen C. Gilardi. All rights reserved. The use and +;; distribution terms for this software are covered by the Eclipse Public +;; License 1.0 (http://opensource.org/licenses/eclipse-1.0.php) which can +;; be found in the file epl-v10.html at the root of this distribution. By +;; using this software in any fashion, you are agreeing to be bound by the +;; terms of this license. You must not remove this notice, or any other, +;; from this software. +;; +;; clojure.contrib.miglayout.example +;; +;; A temperature converter using miglayout. Demonstrates accessing +;; components by their id constraint. +;; +;; scgilardi (gmail) +;; Created 31 May 2009 + +(ns examples.miglayout + (:import (javax.swing JButton JFrame JLabel JPanel JTextField + SwingUtilities)) + (:use (clojure.contrib + [miglayout :only (miglayout components)] + [swing-utils :only (add-key-typed-listener)]))) + +(defn fahrenheit + "Converts a Celsius temperature to Fahrenheit. Input and output are + strings. Returns \"input?\" if the input can't be parsed as a Double." + [celsius] + (try + (format "%.2f" (+ 32 (* 1.8 (Double/parseDouble celsius)))) + (catch NumberFormatException _ "input?"))) + +(defn- handle-key + "Clears output on most keys, shows conversion on \"Enter\"" + [event out] + (.setText out + (if (= (.getKeyChar event) \newline) + (fahrenheit (-> event .getComponent .getText)) + ""))) + +(defn converter-ui + "Lays out and shows a Temperature Converter UI" + [] + (let [panel + (miglayout (JPanel.) + (JTextField. 6) {:id :input} + (JLabel. "\u00b0Celsius") :wrap + (JLabel.) {:id :output} + (JLabel. "\u00b0Fahrenheit")) + {:keys [input output]} (components panel)] + (add-key-typed-listener input handle-key output) + (doto (JFrame. "Temperature Converter") + (.setDefaultCloseOperation JFrame/DISPOSE_ON_CLOSE) + (.add panel) + (.pack) + (.setVisible true)))) + +(defn main + "Invokes converter-ui in the AWT Event thread" + [] + (SwingUtilities/invokeLater converter-ui)) diff --git a/modules/monads/src/examples/clojure/examples/monads.clj b/modules/monads/src/examples/clojure/examples/monads.clj new file mode 100644 index 00000000..926d7edf --- /dev/null +++ b/modules/monads/src/examples/clojure/examples/monads.clj @@ -0,0 +1,425 @@ +;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; +;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; +;; +;; Monad application examples +;; +;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; +;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; + +(ns + #^{:author "Konrad Hinsen" + :skip-wiki true + :doc "Examples for using monads"} + examples.monads + (:use [clojure.contrib.monads + :only (domonad with-monad m-lift m-seq m-reduce m-when + sequence-m + maybe-m + state-m fetch-state set-state + writer-m write + cont-m run-cont call-cc + maybe-t)]) + (:require (clojure.contrib [accumulators :as accu]))) + +;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; +;; +;; Sequence manipulations with the sequence monad +;; +;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; + +; Note: in the Haskell world, this monad is called the list monad. +; The Clojure equivalent to Haskell's lists are (possibly lazy) +; sequences. This is why I call this monad "sequence". All sequences +; created by sequence monad operations are lazy. + +; Monad comprehensions in the sequence monad work exactly the same +; as Clojure's 'for' construct, except that :while clauses are not +; available. +(domonad sequence-m + [x (range 5) + y (range 3)] + (+ x y)) + +; Inside a with-monad block, domonad is used without the monad name. +(with-monad sequence-m + (domonad + [x (range 5) + y (range 3)] + (+ x y))) + +; Conditions are written with :when, as in Clojure's for form: +(domonad sequence-m + [x (range 5) + y (range (+ 1 x)) + :when (= (+ x y) 2)] + (list x y)) + +; :let is also supported like in for: +(domonad sequence-m + [x (range 5) + y (range (+ 1 x)) + :let [sum (+ x y) + diff (- x y)] + :when (= sum 2)] + (list diff)) + +; An example of a sequence function defined in terms of a lift operation. +(with-monad sequence-m + (defn pairs [xs] + ((m-lift 2 #(list %1 %2)) xs xs))) + +(pairs (range 5)) + +; Another way to define pairs is through the m-seq operation. It takes +; a sequence of monadic values and returns a monadic value containing +; the sequence of the underlying values, obtained from chaining together +; from left to right the monadic values in the sequence. +(with-monad sequence-m + (defn pairs [xs] + (m-seq (list xs xs)))) + +(pairs (range 5)) + +; This definition suggests a generalization: +(with-monad sequence-m + (defn ntuples [n xs] + (m-seq (replicate n xs)))) + +(ntuples 2 (range 5)) +(ntuples 3 (range 5)) + +; Lift operations can also be used inside a monad comprehension: +(domonad sequence-m + [x ((m-lift 1 (partial * 2)) (range 5)) + y (range 2)] + [x y]) + +; The m-plus operation does concatenation in the sequence monad. +(domonad sequence-m + [x ((m-lift 2 +) (range 5) (range 3)) + y (m-plus (range 2) '(10 11))] + [x y]) + + +;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; +;; +;; Handling failures with the maybe monad +;; +;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; + +; Maybe monad versions of basic arithmetic +(with-monad maybe-m + (def m+ (m-lift 2 +)) + (def m- (m-lift 2 -)) + (def m* (m-lift 2 *))) + +; Division is special for two reasons: we can't call it m/ because that's +; not a legal Clojure symbol, and we want it to fail if a division by zero +; is attempted. It is best defined by a monad comprehension with a +; :when clause: +(defn safe-div [x y] + (domonad maybe-m + [a x + b y + :when (not (zero? b))] + (/ a b))) + +; Now do some non-trivial computation with division +; It fails for (1) x = 0, (2) y = 0 or (3) y = -x. +(with-monad maybe-m + (defn some-function [x y] + (let [one (m-result 1)] + (safe-div one (m+ (safe-div one (m-result x)) + (safe-div one (m-result y))))))) + +; An example that doesn't fail: +(some-function 2 3) +; And two that do fail, at different places: +(some-function 2 0) +(some-function 2 -2) + +; In the maybe monad, m-plus selects the first monadic value that +; holds a valid value. +(with-monad maybe-m + (m-plus (some-function 2 0) (some-function 2 -2) (some-function 2 3))) + +;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; +;; +;; Random numbers with the state monad +;; +;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; + +; A state monad item represents a computation that changes a state and +; returns a value. Its structure is a function that takes a state argument +; and returns a two-item list containing the value and the updated state. +; It is important to realize that everything you put into a state monad +; expression is a state monad item (thus a function), and everything you +; get out as well. A state monad does not perform a calculation, it +; constructs a function that does the computation when called. + +; First, we define a simple random number generator with explicit state. +; rng is a function of its state (an integer) that returns the +; pseudo-random value derived from this state and the updated state +; for the next iteration. This is exactly the structure of a state +; monad item. +(defn rng [seed] + (let [m 259200 + value (/ (float seed) (float m)) + next (rem (+ 54773 (* 7141 seed)) m)] + [value next])) + +; We define a convenience function that creates an infinite lazy seq +; of values obtained from iteratively applying a state monad value. +(defn value-seq [f seed] + (lazy-seq + (let [[value next] (f seed)] + (cons value (value-seq f next))))) + +; Next, we define basic statistics functions to check our random numbers +(defn sum [xs] (apply + xs)) +(defn mean [xs] (/ (sum xs) (count xs))) +(defn variance [xs] + (let [m (mean xs) + sq #(* % %)] + (mean (for [x xs] (sq (- x m)))))) + +; rng implements a uniform distribution in the interval [0., 1.), so +; ideally, the mean would be 1/2 (0.5) and the variance 1/12 (0.8333). +(mean (take 1000 (value-seq rng 1))) +(variance (take 1000 (value-seq rng 1))) + +; We make use of the state monad to implement a simple (but often sufficient) +; approximation to a Gaussian distribution: the sum of 12 random numbers +; from rng's distribution, shifted by -6, has a distribution that is +; approximately Gaussian with 0 mean and variance 1, by virtue of the central +; limit theorem. +; In the first version, we call rng 12 times explicitly and calculate the +; shifted sum in a monad comprehension: +(def gaussian1 + (domonad state-m + [x1 rng + x2 rng + x3 rng + x4 rng + x5 rng + x6 rng + x7 rng + x8 rng + x9 rng + x10 rng + x11 rng + x12 rng] + (- (+ x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12) 6.))) + +; Let's test it: +(mean (take 1000 (value-seq gaussian1 1))) +(variance (take 1000 (value-seq gaussian1 1))) + +; Of course, we'd rather have a loop construct for creating the 12 +; random numbers. This would be easy if we could define a summation +; operation on random-number generators, which would then be used in +; combination with reduce. The lift operation gives us exactly that. +; More precisely, we need (m-lift 2 +), because we want both arguments +; of + to be lifted to the state monad: +(def gaussian2 + (domonad state-m + [sum12 (reduce (m-lift 2 +) (replicate 12 rng))] + (- sum12 6.))) + +; Such a reduction is often quite useful, so there's m-reduce predefined +; to simplify it: +(def gaussian2 + (domonad state-m + [sum12 (m-reduce + (replicate 12 rng))] + (- sum12 6.))) + +; The statistics should be strictly the same as above, as long as +; we use the same seed: +(mean (take 1000 (value-seq gaussian2 1))) +(variance (take 1000 (value-seq gaussian2 1))) + +; We can also do the subtraction of 6 in a lifted function, and get rid +; of the monad comprehension altogether: +(with-monad state-m + (def gaussian3 + ((m-lift 1 #(- % 6.)) + (m-reduce + (replicate 12 rng))))) + +; Again, the statistics are the same: +(mean (take 1000 (value-seq gaussian3 1))) +(variance (take 1000 (value-seq gaussian3 1))) + +; For a random point in two dimensions, we'd like a random number generator +; that yields a list of two random numbers. The m-seq operation can easily +; provide it: +(with-monad state-m + (def rng2 (m-seq (list rng rng)))) + +; Let's test it: +(rng2 1) + +; fetch-state and get-state can be used to save the seed of the random +; number generator and go back to that saved seed later on: +(def identical-random-seqs + (domonad state-m + [seed (fetch-state) + x1 rng + x2 rng + _ (set-state seed) + y1 rng + y2 rng] + (list [x1 x2] [y1 y2]))) + +(identical-random-seqs 1) + +;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; +;; +;; Logging with the writer monad +;; +;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; + +; A basic logging example +(domonad (writer-m accu/empty-string) + [x (m-result 1) + _ (write "first step\n") + y (m-result 2) + _ (write "second step\n")] + (+ x y)) + +; For a more elaborate application, let's trace the recursive calls of +; a naive implementation of a Fibonacci function. The starting point is: +(defn fib [n] + (if (< n 2) + n + (let [n1 (dec n) + n2 (dec n1)] + (+ (fib n1) (fib n2))))) + +; First we rewrite it to make every computational step explicit +; in a let expression: +(defn fib [n] + (if (< n 2) + n + (let [n1 (dec n) + n2 (dec n1) + f1 (fib n1) + f2 (fib n2)] + (+ f1 f2)))) + +; Next, we replace the let by a domonad in a writer monad that uses a +; vector accumulator. We can then place calls to write in between the +; steps, and obtain as a result both the return value of the function +; and the accumulated trace values. +(with-monad (writer-m accu/empty-vector) + + (defn fib-trace [n] + (if (< n 2) + (m-result n) + (domonad + [n1 (m-result (dec n)) + n2 (m-result (dec n1)) + f1 (fib-trace n1) + _ (write [n1 f1]) + f2 (fib-trace n2) + _ (write [n2 f2]) + ] + (+ f1 f2)))) + +) + +(fib-trace 5) + +;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; +;; +;; Sequences with undefined value: the maybe-t monad transformer +;; +;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; + +; A monad transformer is a function that takes a monad argument and +; returns a monad as its result. The resulting monad adds some +; specific behaviour aspect to the input monad. + +; The simplest monad transformer is maybe-t. It adds the functionality +; of the maybe monad (handling failures or undefined values) to any other +; monad. We illustrate this by applying maybe-t to the sequence monad. +; The result is an enhanced sequence monad in which undefined values +; (represented by nil) are not subjected to any transformation, but +; lead immediately to a nil result in the output. + +; First we define the combined monad: +(def seq-maybe-m (maybe-t sequence-m)) + +; As a first illustration, we create a range of integers and replace +; all even values by nil, using a simple when expression. We use this +; sequence in a monad comprehension that yields (inc x). The result +; is a sequence in which inc has been applied to all non-nil values, +; whereas the nil values appear unmodified in the output: +(domonad seq-maybe-m + [x (for [n (range 10)] (when (odd? n) n))] + (inc x)) + +; Next we repeat the definition of the function pairs (see above), but +; using the seq-maybe monad: +(with-monad seq-maybe-m + (defn pairs-maybe [xs] + (m-seq (list xs xs)))) + +; Applying this to a sequence containing nils yields the pairs of all +; non-nil values interspersed with nils that result from any combination +; in which one or both of the values is nil: +(pairs-maybe (for [n (range 5)] (when (odd? n) n))) + +; It is important to realize that undefined values (nil) are not eliminated +; from the iterations. They are simply not passed on to any operations. +; The outcome of any function applied to arguments of which at least one +; is nil is supposed to be nil as well, and the function is never called. + + +;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; +;; +;; Continuation-passing style in the cont monad +;; +;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; + +; A simple computation performed in continuation-passing style. +; (m-result 1) returns a function that, when called with a single +; argument f, calls (f 1). The result of the domonad-computation is +; a function that behaves in the same way, passing 3 to its function +; argument. run-cont executes a continuation by calling it on identity. +(run-cont + (domonad cont-m + [x (m-result 1) + y (m-result 2)] + (+ x y))) + +; Let's capture a continuation using call-cc. We store it in a global +; variable so that we can do with it whatever we want. The computation +; is the same one as in the first example, but it has the side effect +; of storing the continuation at (m-result 2). +(def continuation nil) + +(run-cont + (domonad cont-m + [x (m-result 1) + y (call-cc (fn [c] (def continuation c) (c 2)))] + (+ x y))) + +; Now we can call the continuation with whatever argument we want. The +; supplied argument takes the place of 2 in the above computation: +(run-cont (continuation 5)) +(run-cont (continuation 42)) +(run-cont (continuation -1)) + +; Next, a function that illustrates how a captured continuation can be +; used as an "emergency exit" out of a computation: +(defn sqrt-as-str [x] + (call-cc + (fn [k] + (domonad cont-m + [_ (m-when (< x 0) (k (str "negative argument " x)))] + (str (. Math sqrt x)))))) + +(run-cont (sqrt-as-str 2)) +(run-cont (sqrt-as-str -2)) + +;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; diff --git a/modules/probabilities/src/examples/clojure/examples/finite_distributions.clj b/modules/probabilities/src/examples/clojure/examples/finite_distributions.clj new file mode 100644 index 00000000..8a795e16 --- /dev/null +++ b/modules/probabilities/src/examples/clojure/examples/finite_distributions.clj @@ -0,0 +1,209 @@ +;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; +;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; +;; +;; Probability distribution application examples +;; +;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; +;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; + +(ns + #^{:author "Konrad Hinsen" + :skip-wiki true + :doc "Examples for finite probability distribution"} + examples.finite-distributions + (:use [clojure.contrib.probabilities.finite-distributions + :only (uniform prob cond-prob join-with dist-m choose + normalize certainly cond-dist-m normalize-cond)]) + (:use [clojure.contrib.monads + :only (domonad with-monad m-seq m-chain m-lift)]) + (:require clojure.contrib.accumulators)) + +;; Simple examples using dice + +; A single die is represented by a uniform distribution over the +; six possible outcomes. +(def die (uniform #{1 2 3 4 5 6})) + +; The probability that the result is odd... +(prob odd? die) +; ... or greater than four. +(prob #(> % 4) die) + +; The sum of two dice +(def two-dice (join-with + die die)) +(prob #(> % 6) two-dice) + +; The sum of two dice using a monad comprehension +(assert (= two-dice + (domonad dist-m + [d1 die + d2 die] + (+ d1 d2)))) + +; The two values separately, but as an ordered pair +(domonad dist-m + [d1 die + d2 die] + (if (< d1 d2) (list d1 d2) (list d2 d1))) + +; The conditional probability for two dice yielding X if X is odd: +(cond-prob odd? two-dice) + +; A two-step experiment: throw a die, and then add 1 with probability 1/2 +(domonad dist-m + [d die + x (choose (/ 1 2) d + :else (inc d))] + x) + +; The sum of n dice +(defn dice [n] + (domonad dist-m + [ds (m-seq (replicate n die))] + (apply + ds))) + +(assert (= two-dice (dice 2))) + +(dice 3) + + +;; Construct an empirical distribution from counters + +; Using an ordinary counter: +(def dist1 + (normalize + (clojure.contrib.accumulators/add-items + clojure.contrib.accumulators/empty-counter + (for [_ (range 1000)] (rand-int 5))))) + +; Or, more efficiently, using a counter that already keeps track of its total: +(def dist2 + (normalize + (clojure.contrib.accumulators/add-items + clojure.contrib.accumulators/empty-counter-with-total + (for [_ (range 1000)] (rand-int 5))))) + + +;; The Monty Hall game +;; (see http://en.wikipedia.org/wiki/Monty_Hall_problem for a description) + +; The set of doors. In the classical variant, there are three doors, +; but the code can also work with more than three doors. +(def doors #{:A :B :C}) + +; A simulation of the game, step by step: +(domonad dist-m + [; The prize is hidden behind one of the doors. + prize (uniform doors) + ; The player make his initial choice. + choice (uniform doors) + ; The host opens a door which is neither the prize door nor the + ; one chosen by the player. + opened (uniform (disj doors prize choice)) + ; If the player stays with his initial choice, the game ends and the + ; following line should be commented out. It describes the switch from + ; the initial choice to a door that is neither the opened one nor + ; his original choice. + choice (uniform (disj doors opened choice)) + ] + ; If the chosen door has the prize behind it, the player wins. + (if (= choice prize) :win :loose)) + + +;; Tree growth simulation +;; Adapted from the code in: +;; Martin Erwig and Steve Kollmansberger, +;; "Probabilistic Functional Programming in Haskell", +;; Journal of Functional Programming, Vol. 16, No. 1, 21-34, 2006 +;; http://web.engr.oregonstate.edu/~erwig/papers/abstracts.html#JFP06a + +; A tree is represented by two attributes: its state (alive, hit, fallen), +; and its height (an integer). A new tree starts out alive and with zero height. +(def new-tree {:state :alive, :height 0}) + +; An evolution step in the simulation modifies alive trees only. They can +; either grow by one (90% probability), be hit by lightning and then stop +; growing (4% probability), or fall down (6% probability). +(defn evolve-1 [tree] + (let [{s :state h :height} tree] + (if (= s :alive) + (choose 0.9 (assoc tree :height (inc (:height tree))) + 0.04 (assoc tree :state :hit) + :else {:state :fallen, :height 0}) + (certainly tree)))) + +; Multiple evolution steps can be chained together with m-chain, +; since each step's input is the output of the previous step. +(with-monad dist-m + (defn evolve [n tree] + ((m-chain (replicate n evolve-1)) tree))) + +; Try it for zero, one, or two steps. +(evolve 0 new-tree) +(evolve 1 new-tree) +(evolve 2 new-tree) + +; We can also get a distribution of the height only: +(with-monad dist-m + ((m-lift 1 :height) (evolve 2 new-tree))) + + + +;; Bayesian inference +;; +;; Suppose someone has three dice, one with six faces, one with eight, and +;; one with twelve. This person throws one die and gives us the number, +;; but doesn't tell us which die it was. What are the Bayesian probabilities +;; for each of the three dice, given the observation we have? + +; A function that returns the distribution of a dice with n faces. +(defn die-n [n] (uniform (range 1 (inc n)))) + +; The three dice in the game with their distributions. With this map, we +; can easily calculate the probability for an observation under the +; condition that a particular die was used. +(def dice {:six (die-n 6) + :eight (die-n 8) + :twelve (die-n 12)}) + +; The only prior knowledge is that one of the three dice is used, so we +; have no better than a uniform distribution to start with. +(def prior (uniform (keys dice))) + +; Add a single observation to the information contained in the +; distribution. Adding an observation consists of +; 1) Draw a die from the prior distribution. +; 2) Draw an observation from the distribution of that die. +; 3) Eliminate (replace by nil) the trials that do not match the observation. +; 4) Normalize the distribution for the non-nil values. +(defn add-observation [prior observation] + (normalize-cond + (domonad cond-dist-m + [die prior + number (get dice die) + :when (= number observation) ] + die))) + +; Add one observation. +(add-observation prior 1) + +; Add three consecutive observations. +(-> prior (add-observation 1) + (add-observation 3) + (add-observation 7)) + +; We can also add multiple observations in a single trial, but this +; is slower because more combinations have to be taken into account. +; With Bayesian inference, it is most efficient to eliminate choices +; as early as possible. +(defn add-observations [prior observations] + (with-monad cond-dist-m + (let [n-nums #(m-seq (replicate (count observations) (get dice %)))] + (normalize-cond + (domonad + [die prior + nums (n-nums die) + :when (= nums observations)] + die))))) + +(add-observations prior [1 3 7]) diff --git a/modules/probabilities/src/examples/clojure/examples/monte_carlo.clj b/modules/probabilities/src/examples/clojure/examples/monte_carlo.clj new file mode 100644 index 00000000..4583dcf9 --- /dev/null +++ b/modules/probabilities/src/examples/clojure/examples/monte_carlo.clj @@ -0,0 +1,73 @@ +;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; +;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; +;; +;; Monte-Carlo application examples +;; +;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; +;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; + +(ns + #^{:author "Konrad Hinsen" + :skip-wiki true + :doc "Examples for monte carlo methods"} + examples.monte-carlo + (:require [clojure.contrib.generic.collection :as gc]) + (:use [clojure.contrib.probabilities.random-numbers + :only (lcg rand-stream)]) + (:use [clojure.contrib.probabilities.finite-distributions + :only (uniform)]) + (:use [clojure.contrib.probabilities.monte-carlo + :only (random-stream discrete interval normal lognormal exponential + n-sphere + sample sample-sum sample-mean sample-mean-variance)] + :reload) + (:use [clojure.contrib.monads + :only (domonad state-m)])) + +; Create a linear congruential generator +(def urng (lcg 259200 7141 54773 1)) + +;; Use Clojure's built-in random number generator +;(def urng rand-stream) + +; Sample transformed distributions +(defn sample-distribution + [n rt] + (take n (gc/seq (random-stream rt urng)))) + +; Interval [-2, 2) +(sample-distribution 10 (interval -2 2)) +; Compare with a direct transformation +(= (sample-distribution 10 (interval -2 2)) + (map (fn [x] (- (* 4 x) 2)) (take 10 (gc/seq urng)))) + +; Normal distribution +(sample-distribution 10 (normal 0 1)) + +; Log-Normal distribution +(sample-distribution 10 (lognormal 0 1)) + +; Exponential distribution +(sample-distribution 10 (exponential 1)) + +; n-sphere distribution +(sample-distribution 10 (n-sphere 2 1)) + +; Discrete distribution +(sample-distribution 10 (discrete (uniform (range 1 7)))) + +; Compose distributions in the state monad +(def sum-two-dists + (domonad state-m + [r1 (interval -2 2) + r2 (normal 0 1)] + (+ r1 r2))) + +(sample-distribution 10 sum-two-dists) + +; Distribution transformations +(sample-distribution 5 (sample 2 (interval -2 2))) +(sample-distribution 10 (sample-sum 10 (interval -2 2))) +(sample-distribution 10 (sample-mean 10 (interval -2 2))) +(sample-distribution 10 (sample-mean-variance 10 (interval -2 2))) + diff --git a/modules/types/src/examples/clojure/examples/types.clj b/modules/types/src/examples/clojure/examples/types.clj new file mode 100644 index 00000000..57bcb54e --- /dev/null +++ b/modules/types/src/examples/clojure/examples/types.clj @@ -0,0 +1,152 @@ +;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; +;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; +;; +;; Application examples for data types +;; +;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; +;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; + +(ns + #^{:author "Konrad Hinsen" + :skip-wiki true + :doc "Examples for data type definitions"} + examples.types + (:refer-clojure :exclude (deftype)) + (:use [clojure.contrib.types + :only (deftype defadt match)]) + (:require [clojure.contrib.generic.collection :as gc]) + (:require [clojure.contrib.generic.functor :as gf])) + +; +; Multisets implemented as maps to integers +; + +; The most basic type definition. A more elaborate version could add +; a constructor that verifies that its argument is a map with integer values. +(deftype ::multiset multiset + "Multiset (demo implementation)") + +; Some set operations generalized to multisets +; Note that the multiset constructor is nowhere called explicitly, as the +; map operations all preserve the metadata. +(defmethod gc/conj ::multiset + ([ms x] + (assoc ms x (inc (get ms x 0)))) + ([ms x & xs] + (reduce gc/conj (gc/conj ms x) xs))) + +(defmulti union (fn [& sets] (type (first sets)))) + +(defmethod union clojure.lang.IPersistentSet + [& sets] + (apply clojure.set/union sets)) + +; Note: a production-quality implementation should accept standard sets +; and perhaps other collections for its second argument. +(defmethod union ::multiset + ([ms] ms) + ([ms1 ms2] + (letfn [(add-item [ms [item n]] + (assoc ms item (+ n (get ms item 0))))] + (reduce add-item ms1 ms2))) + ([ms1 ms2 & mss] + (reduce union (union ms1 ms2) mss))) + +; Let's use it: +(gc/conj #{} :a :a :b :c) +(gc/conj (multiset {}) :a :a :b :c) + +(union #{:a :b} #{:b :c}) +(union (multiset {:a 1 :b 1}) (multiset {:b 1 :c 2})) + +; +; A simple tree structure defined as an algebraic data type +; +(defadt ::tree + empty-tree + (leaf value) + (node left-tree right-tree)) + +(def a-tree (node (leaf :a) + (node (leaf :b) + (leaf :c)))) + +(defn depth + [t] + (match t + empty-tree 0 + (leaf _) 1 + (node l r) (inc (max (depth l) (depth r))))) + +(depth empty-tree) +(depth (leaf 42)) +(depth a-tree) + +; Algebraic data types with multimethods: fmap on a tree +(defmethod gf/fmap ::tree + [f t] + (match t + empty-tree empty-tree + (leaf v) (leaf (f v)) + (node l r) (node (gf/fmap f l) (gf/fmap f r)))) + +(gf/fmap str a-tree) + +; +; Nonsense examples to illustrate all the features of match +; for type constructors. +; +(defadt ::foo + (bar a b c)) + +(defn foo-to-int + [a-foo] + (match a-foo + (bar x x x) x + (bar 0 x y) (+ x y) + (bar 1 2 3) -1 + (bar a b 1) (* a b) + :else 42)) + +(foo-to-int (bar 0 0 0)) ; 0 +(foo-to-int (bar 0 5 6)) ; 11 +(foo-to-int (bar 1 2 3)) ; -1 +(foo-to-int (bar 3 3 1)) ; 9 +(foo-to-int (bar 0 3 1)) ; 4 +(foo-to-int (bar 10 20 30)) ; 42 + +; +; Match can also be used for lists, vectors, and maps. Note that since +; algebraic data types are represented as maps, they can be matched +; either with their type constructor and positional arguments, or +; with a map template. +; + +; Tree depth once again with map templates +(defn depth + [t] + (match t + empty-tree 0 + {:value _} 1 + {:left-tree l :right-tree r} (inc (max (depth l) (depth r))))) + +(depth empty-tree) +(depth (leaf 42)) +(depth a-tree) + +; Match for lists, vectors, and maps: + +(for [x ['(1 2 3) + [1 2 3] + {:x 1 :y 2 :z 3} + '(1 1 1) + [2 1 2] + {:x 1 :y 1 :z 2}]] + (match x + '(a a a) 'list-of-three-equal-values + '(a b c) 'list + [a a a] 'vector-of-three-equal-values + [a b a] 'vector-of-three-with-first-and-last-equal + [a b c] 'vector + {:x a :y z} 'map-with-x-equal-y + {} 'any-map)) |