datastructures.clj

(ns repl.datastructures
  (:use clojure.repl))

(defmacro t [& body]
  `(let [sw-out# (java.io.StringWriter.)]
     (binding [*out* sw-out#]
       (let [result# (time (do ~@body))]
         {:out (.toString sw-out#)
          :result result#}))))

(defmacro deft [n form]
  `(with-out-str (time (def ~n ~form))))

(set! *print-length* 100)

(comment
  (deft a (into [] (range 1e7)))


  (t (nth a (dec (count a))))

  (t (last a))

  (doc last)

  (with-out-str (time (def b (assoc a 666777 :foo))))

  (t (nth a (dec (count b))))

  (t (a 666777))
  (t (b 666777))

  ;; b kann keine Kopie sein!!!
  ;; Wie implementiert man sowas?
 



  )

y.clj

(ns repl.y)
(comment


  ;; Refactoring 1
  ;; Verpacken eines Ausdrucks in einer Funktion und sofortiges Aufrufen ändert nichts
  ;; am Ergebnis
  2
  ((fn [] 5))

  (#(* 3 %) 11)
  ((fn [] (#(* 3 %) 12)))
  (((fn []  #(* 3 %))) 13)
  (#(* ((fn [] 3)) %) 14)
  (#(* 3 ((fn [] %))) 15)
  (#(((fn [] *)) 3 %) 16)


  ;; Refactoring 2
  ;; Binding einführen
  (def x 1)
  ((fn [] x))
  ((fn [y] x) :blah)

  ;; Was muss man beachten?
  ((fn [x] x) :blah)

  ;; Refactoring 3
  ;; Wrapping

  (defn mk-adder [x]
    (println :call)
    (fn [n] (+ x n)))

  (def add1 (mk-adder 1))
  (add1 3)

  (defn mk-adder' [x]
    (fn [v] ((mk-adder x) v)))

  (def add1' (mk-adder' 1))
  (add1' 2)

(def foo1 add1)
  
  ;; Refactoring 4
  ;; Inline Definition
  (def foo2 (fn [x] (foo1 x)))
  (def foo3 (fn [x] ((fn [n] (+ 1 n)) x)))
  (foo3 5)

  ;; Lambda Kalkül und Rekursion

  (def fact (fn [n] (if (= 0 n) 1 (* n (fact (dec n))))))
  (fact 3)

  ;; Wie wird das eigentlich beerechnet?
  (fact 3)
  ;; Inlining
  ((fn [n] (if (= 0 n) 1 (* n (fact (dec n))))) 3)
  ;; reduction ...
  (if (= 0 3) 1 (* 3 (fact (dec 3))))
  (* 3 (fact 2))
  ;; Inlining
  (* 3 ((fn [n] (if (= 0 n) 1 (* n (fact (dec n))))) 2))
  ;; reduction ...
  (* 3 (if (= 0 2) 1 (* 2 (fact (dec 2)))))
  (* 3 (* 2 (fact 1)))
  ;; Inlining
  (* 3 (* 2 ((fn [n] (if (= 0 n) 1 (* n (fact (dec n))))) 1)))
  ;; reduction ...
  (* 3 (* 2 (if (= 0 1) 1 (* 1 (fact (dec 1))))))
  (* 3 (* 2 (* 1 (fact 0))))
  ;; Inlining
  (* 3 (* 2 (* 1 ((fn [n] (if (= 0 n) 1 (* n (fact (dec n))))) 0))))
  ;; reduction
  (* 3 (* 2 (* 1 (if (= 0 0) 1 (* 0 (fact (dec 0)))))))
  (* 3 (* 2 (* 1 1)))

  ;; Wie können wir fact im Lambda Kalkül ausdrücken?

  ;; Das Problem: Im Lambda Kalkül haben wir keine Namen, nur anonyme
  ;; Funktionen

  ;; Wir können ein Binding einführen
  (def improve_fact
    (fn [partial_fact]
      (fn [n]
        (if (= 0 n) 1 (* n (partial_fact (dec n)))))))

  ;; jetzt können wir fact definieren:
  ;; (def fact (improve_fact fact))
  ;; fact = mk_fact(fact)
  ;; Ein Fixpunkt x ist ein Wert für den gilt: x = f(x)

  ;; Aha! fact ist Fixpunkt der Funktion mk_fact!

  (defn bumm! [n] (throw (Exception. "d'oh!")))

  (def f0 (improve_fact bumm!))
  (f0 0)
  (f0 1)
  (def f1 (improve_fact f0))
  (f1 0)
  (f1 1)
  (f1 2)
  (def f2 (improve_fact f1))
  (f2 0)
  (f2 1)
  (f2 2)
  (f2 3)
  ;; ...

  ;; improve_fact bekommt eine Funktion, die (n-1)! berechnen kann und
  ;; liefert eine Funktion, die n! berechnen kann

  ;; Es folgen einige Refactorings ausgehend von f1

  (def f0 (improve_fact bumm!))
  (def f1 (improve_fact f0))

  (def f1 (improve_fact (improve_fact bumm!)))

  ;; Refactoring 1: Wrapping

  (def f1 (
           (fn [improver] (improver (improver bumm!)))
           improve_fact))

  ;; Inlining von improve_fact

  (def f1
    ((fn [improver] (improver (improver bumm!)))
     (fn [partial_fact]
       (fn [n]
         (if (= 0 n) 1 (* n (partial_fact (dec n))))))))

  (f1 1)
  (f1 2)

  ;; bumm! hat eigentlich nichts mit der Fakultät zu tun
  ;; Kann man das entfernen?
  (def f1
    ((fn [improver] (improver improver))
     (fn [partial_fact]
       (fn [n]
         (if (= 0 n) 1 (* n (partial_fact (dec n))))))))

  (f1 0)
  (f1 1)

  ;; partial_fact ist beim Aufruf die Funktion improver
  ;; wir können das ein bischen sauberer schreiben durch Umbenennung
  (def f1
    ((fn [improver] (improver improver))
     (fn [improver]
       (fn [n]
         (if (= 0 n) 1 (* n (improver (dec n))))))))

  (f1 0)
  (f1 1)

  ;; improver nimmt keine Zahl als Argument, sondern eine Funktion!

  ;; Welche Funktion könnten wir nehmen?





  (def f1
    ((fn [improver] (improver improver))
     (fn [improver]
       (fn [n]
         (if (= 0 n) 1 (* n ((improver improver) (dec n))))))))



  (f1 0)
  (f1 1)
  (f1 2)
  (f1 3)
  (f1 20)








  ;; Yo Dawg, I herd you like functions, so I put a function in your function


  ;; Inlining gibt einen reinen lambda-Ausdruck, der die Fakultät berechnet!
  (((fn [improver] (improver improver))
    (fn [improver]
      (fn [n]
        (if (= 0 n) 1 (* n ((improver improver) (dec n))))))) 10)

  ;; Das ist komplex, es mischt Fakultät mit der Fixpunkt-Berechnung

  ( ;; Rekursionsbehandlung
   ((fn [r]
      ((fn [f] (f f))
       (fn [f]
         (r (fn [x] ((f f) x))))))
    ;; improve_fact
    (fn [partial_fact]
      (fn [n]
        (if (= 0 n) 1 (* n (partial_fact (dec n))))))

    ) 10)

  ;; Der Teil, der die Rekursion erledigt heisst Y Combinator
  (def Y (fn [r]
           ((fn [f] (f f))
            (fn [f]
              (r (fn [x] ((f f) x)))))))

  ((Y improve_fact) 11)

  ;; Der Y Combinator berechnet den Fixpunkt von Generator Funktionen

  ;; Summe von Elementen in einer Liste:
  (defn sum-seq [s]
    (if (empty? s)
      0
      (+ (first s) (sum-seq (rest s)))))

  ;; Generator
  (defn sum-seq-fn-gen [func]
    (fn [s]
      (if (empty? s)
        0
        (+ (first s) (func (rest s))))))

  ((Y sum-seq-fn-gen ) [1 2 3 4 5])

  )