In this article, I'll explain why implementing numbers with just algebraic datatypes is desirable. I'll then talk about common implementations of FFT (Fast Fourier Transform) and why they hide inherent inefficiencies. I'll then show how to implement integers and complex numbers with just algebraic datatypes, in a way that is extremely simple and elegant. I'll conclude by deriving a pure functional implementation of complex FFT with just datatypes, no floats.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
(def levdist | |
(let [lev (atom nil) | |
impl | |
(fn [s t] | |
(let [lev @lev] | |
(cond | |
(empty? s) (count t) | |
(empty? t) (count s) | |
:else (let [ns (rest s) | |
nt (rest t)] |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
(ns cljclass) | |
;; Various ways to solve the problem of transforming a vector to a vector of indices starting at zero, but | |
;; using an index of -1 for items for which (pred item) is true. | |
;; E.g. (index-except odd? [1 4 18 7 9 2 4 3]) => [-1 0 1 -1 -1 2 3 -1] | |
;; NB: | |
;; This is not the same as assigning indices and replacing the elements for which pred is true with -1. | |
;; E.g. (index-except odd? [1 2 3]) => [-1 0 -1] and not [-1 1 -1]. |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
(defn permx [coll] | |
(letfn [(helper [m] | |
(if (empty? m) | |
'(()) | |
(for [[i x] m | |
perm (helper (dissoc m i))] | |
(cons x perm))))] | |
(helper (into (sorted-map) | |
(map-indexed vector coll))))) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
(defn dijkstra | |
([a] | |
(dijkstra a (find-walls a) (find-lowest a))) | |
([a closed open-cells] | |
(loop [open open-cells] | |
(when (seq open) | |
(recur (reduce (fn [newly-open [i v]] | |
(reduce (fn [acc dir] | |
(if (or (closed dir) (open dir) | |
(>= (inc v) (hiphip/aget a n))) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
;; This buffer is for notes you don't want to save, and for Lisp evaluation. | |
;; If you want to create a file, visit that file with C-x C-f, | |
;; then enter the text in that file's own buffer. | |
(defn extract-render-listener | |
"A RenderListener implementation that extracts images from a PDF and | |
writes them to disk." | |
[path] | |
(reify RenderListener | |
(renderImage [_ render-info] |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#################################### | |
# BASIC REQUIREMENTS | |
# http://graphite.wikidot.com/installation | |
# http://geek.michaelgrace.org/2011/09/how-to-install-graphite-on-ubuntu/ | |
# Last tested & updated 10/13/2011 | |
#################################### | |
sudo apt-get update | |
sudo apt-get upgrade |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
(ns algo2.unionfind) | |
(defprotocol DisjointSet | |
"A data structure that maintains informations on a number of disjoint sets." | |
(add-singleton [this x] "Add the element x to a new singleton set") | |
(connect [this x y] "Union the sets that x and y are in") | |
(get-canonical [this x] "Return the canonical element of the set x is in")) | |
(defrecord UFNode [value rank parent]) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
(def v (into [] (repeatedly 1e5 #(rand 100)))) | |
(defn rnd [x] | |
(Math/round x)) | |
(defn prnd [x] | |
(let [^double x x] | |
(Math/round x))) | |
(time (r/fold + (r/map rnd v))) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
(defn longest-palindrome [s] | |
(let [palindrome? #(= (seq %) (reverse %)) | |
slice-all (fn [s] (mapcat #(partition % 1 s) | |
(map first | |
(take-while seq | |
(iterate rest | |
(range (count s) 1 -1))))))] | |
(first (filter palindrome? (slice-all s))))) |
NewerOlder