Created
January 11, 2011 05:23
-
-
Save anonymous/774055 to your computer and use it in GitHub Desktop.
de-Brujin index
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
(use '[clojure.contrib.seq-utils]) | |
(defn position [f coll] | |
(first (positions f coll))) | |
(defn de-brujin-index [x coll] | |
(position #(= x %) coll)) | |
(defn append [x gamma] | |
(cons x gamma)) | |
(defn variable? [sexp] | |
(not (coll? sexp))) | |
(defn abstraction? [sexp] | |
(and (= (first sexp) :fn) | |
(= (count sexp) 3))) | |
(defn application? [sexp] | |
(coll? sexp)) | |
(defn body [sexp] | |
(first (next (next sexp)))) | |
(defn removenames | |
([sexp] | |
(removeterm sexp [])) | |
([sexp gamma] | |
(cond | |
(variable? sexp) (de-brujin-index sexp gamma) | |
(abstraction? sexp) (seq [:fn (removenames (body sexp) (append (second sexp) gamma))]) | |
(application? sexp) (map #(removenames % gamma) sexp)))) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment