gistfile1.clj

(ns clj-misc.parse)

(defn result [v]
  (fn [inp] [[v, inp]]))

(defn zero [inp] [])

(defn item [[x & xs]]
  (if x
    [[x, xs]]
    []))

(defn bind [p f]
  (fn [inp]
    (mapcat (fn [[v inpp]]
              ((f v) inpp)) (p inp))))

(defn sat [pred]
  (bind item (fn [x]
               (if (pred x)
                 (result x)
                 zero))))

(def lower (sat #(Character/isLowerCase %)))
(def upper (sat #(Character/isUpperCase %)))

(defn plus [p q]
  (fn [inp]
    (concat (p inp) (q inp))))

(def letter (plus lower upper))

(comment
"Original Implementation"
(defn many [p]
  (plus (bind p
              (fn [x]
                (bind (many p)
                      (fn [xs]
                        (result (cons x xs))))))
        (result [])))
)

(def many
     (memoize
      (fn [p]
        (plus (bind p
                    (fn [x]
                      (bind (many p)
                            (fn [xs]
                              (result (cons x xs))))))
              (result [])))))

(def word (many letter))

;clj-misc.parse> (word "Yes!")
;([(\Y \e \s) (\!)] [(\Y \e) (\s \!)] [(\Y) (\e \s \!)] [[] "Yes!"])

This work is based on http://www.cs.nott.ac.uk/~gmh/bib.html#monparsing

Also, an alternative formulation of bind using 'for', which better matches the definition in the paper:
(defn bind [p f](fn [inp]
%28apply concat
%28for [[v inpp] %28p inp%29] %28%28f v%29 inpp%29%29%29))