amalloy

Implementing complex numbers and FFT with just datatypes (no floats)

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.

amalloy

(fn [o]
  (set
   ((fn q [s o c]
      (apply concat
             (let [a (when (pos? o)
                       (q (concat s "(") (dec o) (inc c)))
                   b (when (pos? c)
                       (q (concat s ")") o (dec c)))]
               (if (and (zero? o) (zero? c))
                 [[(clojure.string/join s)]]

amalloy

def categorize(fn, coll):
    """Like group_by, but fn returns multiple keys"""
 
    acc = {}
    for e in coll:
        for key in fn(e):
            acc.setdefault(key, []).append(e)
    return acc
 
def group_by(fn, l):

amalloy

(reduce (fn [mentioned-files file]
          (if (some #{file} mentioned-files)
            mentioned-files
            (let [duplicates (duplicates-of-file file files (:precision options))]
              (when (seq duplicates)
                (printf "%s\n" file)
                (doseq [d duplicates]
                  (printf "%s\n" d))
                (printf "\n"))
              (concat mentioned-files duplicates))))

amalloy

(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]. 

amalloy

(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)))))

amalloy

(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)))

amalloy

;; 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]

amalloy

####################################
# 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

amalloy

(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])