Friday, March 23, 2012

Implementation of monoids

Monoids are functions that have the property that calls to the monoid within the monoid can be replaced with the arguments of the call. In other words, the order and amount of calls to the operation is irrelevant. Addition, concatenation, composition, and other related operations are all monoidal.
(+ 1 2 3)
(concat [1 2] [3 4])
(comp (partial apply +) range inc)
The set of quantities under multiplication forms a monoid. Furthermore, with respect to booleans there are two commutative monoids corresponding to the two possible identities. The function or? corresponds to a monoid with an identity of false and the function and? corresponds to a monoid with an identity of true. The computer algebra system can simplify the call to any monoid:
(defn simplify-monoid-call

   (first expr)
   (apply concat
           (fn [current-expr]
             (if (and (seq? current-expr)
                      (= (first expr) (first current-expr)))
               (rest (simplify-monoid-call current-expr))
               (list current-expr)))
           (rest expr)))))
Here is an example of how this function might work:
(= (simplify-monoid-call '(+ 1 2 (+ 3 4) 5 (+))
  '(+ 1 2 3 4 5))
This is one small step towards building an effective Lisp based computer algebra system.

No comments:

Post a Comment