A Replace Function in Lisp That Duplicates Mathematica Functionality

Question

What is the easiest way to accomplish the following in a Mathematica clone or in any version of Lisp(any language is probably okay actually even Haskell)? It doesn't appear any lisps have a similar replace function.

Replace[{
  f[{x, "[", y, "]"}],
  f@f[{x, "[", y, y2, "]"}]
  }
 , f[{x_, "[", y__, "]"}] :> x[y],
 Infinity]

and a return value of {x[y], f[x[y, y2]]}

It replaces all instances of f[{x_, "[", y__, "]"}] in args where x_ represents a single variable and y__ represents one or more variables.

In lisp the function and replacement would probably be the equivalent(forgive me I am not the best with Lisp). I'm looking for a function of the form (replace list search replace).

(replace
  '(
   (f (x "[" y "]"))
   (f (f '(x "[" y y2 "]")))
  )
  '(f (x_ "[" y__ "]"))
  '(x y)
)

and get a return value of ((x y) (f (x y y2))).

@ScottHunter Fixed here is the link to Mathematica.se post mathematica.stackexchange.com/questions/94720/… — Lime
– Lime, Commented Sep 15, 2015 at 19:47
Mind telling us what that Mathematica code does? And what you've tried that didn't work? — Joshua Taylor
– Joshua Taylor, Commented Sep 16, 2015 at 0:18
@JoshuaTaylor It replaces all instances of f[{x_, "[", y__, "]"}] where x_ represents a single variable and y__ represents one or more variables. — Lime
– Lime, Commented Sep 16, 2015 at 0:54

coredump · Accepted Answer · 2015-10-09 05:59:40Z

4

+100

Let's give it another try.

First, install quicklisp and use it to fetch, install and load optima and alexandria.

(ql:quickload :optima)
(ql:quickload :alexandria)
(use-package :alexandria)

The functions from alexandria referenced below are ensure-list and last-elt. If you don't have them installed, you can use the following definitions:

(defun ensure-list (list) (if (listp list) list (list list)))
(defun last-elt (list) (car (last list)))

We define rules as functions from one form to another. Below, the function tries to destructure the input as (f (<X> "[" <ARGS> "]"), where <ARGS> is zero or more form. If destructuring fails, we return NIL (we expect non-matching filters to return NIL hereafter).

(defun match-ugly-funcall (form)
  (optima:match form
    ((list 'f (cons x args))
     (unless (and (string= "[" (first args))
                  (string= "]" (last-elt args)))
       (optima:fail))
     `(,x ,@(cdr (butlast args))))))

(match-ugly-funcall '(f (g "[" 1 3 5 4 8 "]")))
; => (G 1 3 5 4 8)

Then, we mimic Mathematica's Replace with this function, which takes a form and a list of rules to be tried. It is possible to pass a single rule (thanks to ensure-list). If a list of list of rules is given, a list of matches should be returned (to be done).

(defun match-replace (form rules &optional (levelspec '(0)))
  (setf rules (ensure-list rules))
  (multiple-value-bind (match-levelspec-p recurse-levelspec-p)
      (optima:ematch levelspec
        ((list n1 n2) (if (some #'minusp (list  n1 n2))
                          (optima:fail)
                          (values (lambda (d) (<= n1 d n2))
                                  (lambda (d) (< d n2)))))
        ((list n) (if (minusp n)
                      (optima:fail)
                      (values (lambda (d) (= d n))
                              (lambda (d) (< d n)))))
        (:infinity (values (constantly t) (constantly t))))
    (labels
        ((do-replace (form depth)
           (let ((result
                   (and (funcall match-levelspec-p depth)
                        (some (lambda (r) (funcall r form)) rules))))
             (cond
               (result (values result t))
               ((and (listp form)
                     (funcall recurse-levelspec-p depth))
                (incf depth)
                (do (newlist
                     (e (pop form) (pop form)))
                    ((endp form) (values form nil))
                  (multiple-value-bind (result matchedp) (do-replace e depth)
                    (if matchedp
                        (return (values (nconc (nreverse newlist) 
                                               (list* result form)) t))
                        (push e newlist)))))
               (t (values form nil))))))
      (do-replace form 0))))

And a test:

(match-replace '(a b (f (x "[" 1 2 3 "]")) c d)
               #'match-ugly-funcall
               :infinity)
; => (A B (X 1 2 3) C D)
;    T

In order to replace all expressions instead of the first matching one, use this instead:

  (defun match-replace-all (form rules &optional (levelspec '(0)))
      (setf rules (ensure-list rules))
      (multiple-value-bind (match-levelspec-p recurse-levelspec-p)
          (optima:ematch levelspec
            ((list n1 n2) (if (some #'minusp (list  n1 n2))
                              (optima:fail)
                              (values (lambda (d) (<= n1 d n2))
                                      (lambda (d) (< d n2)))))
            ((list n) (if (minusp n)
                          (optima:fail)
                          (values (lambda (d) (= d n))
                                  (lambda (d) (< d n)))))
            (:infinity (values (constantly t) (constantly t))))
        (labels
            ((do-replace (form depth)
               (let ((result
                       (and (funcall match-levelspec-p depth)
                            (some (lambda (r) (funcall r form)) rules))))
                 (cond
                   (result result)
                   ((and (listp form)
                         (funcall recurse-levelspec-p depth))
                    (incf depth)
                    (mapcar (lambda (e) (do-replace e depth)) form))
                   (t form)))))
          (do-replace form 0))))

edited Oct 9, 2015 at 5:59

answered Sep 18, 2015 at 14:25

coredump

39.4k7 gold badges47 silver badges85 bronze badges

Sign up to request clarification or add additional context in comments.

13 Comments

Lime Over a year ago

+1 but it appears at first glance that the function only works with replacements list at depth 1. In addition I was hopeful to have something over the form (replace list search rule) similar to M.

coredump Over a year ago

@William Surely it should not be too difficult to modify the implementation to suit your need, but the at the moment I don't have much time and I am not sure to know exactly what you need. I never used Mathematica, and the reference I get when looking for Replace is this one: reference.wolfram.com/language/ref/Replace.html. I would gladly be shown another reference if you have one. It says that "[Replace] does not map down to subparts", though there is an optional levelspec argument. Also, I don't see anything similar to (replace list search rule).

Lime Over a year ago

Technically it is Replace[expr,rules,levelspec] but because rules are two parts in would translate into something like Replace[expr,rule1,rule2,levelspec] so it would be (replace expr rule1 rule2 levelspec). levelspec because I believe your example only works for 1 level spec.

Lime Over a year ago

It appears to work thanks! Is there a way to use a lambda instead of creating another function?

Lime Over a year ago

I have another question what would happen if you had something like f[a_,b_,c_,x_,y__,z___] would that be to complex for your example?

|

Vsevolod Dyomkin · Accepted Answer · 2015-09-18 10:16:03Z

0

Oh boy, how Mathematica manages to obfuscate everything by applying its renown NIH approach.

Basically, you're looking for a function to perform string replacement according to some pattern. In most languages, this is accomplished with regular expressions.

For instance, in Common Lisp using the cl-ppcre library it will look something like this:

(cl-ppcre:regex-replace-all
 ;; regular expression you match against with groups
 "f\\[{(x[^ ]*), \"\\[\", ((y[^ ]* ?)+), \"\\]\"}\\]"
 ;; your string
 "{f[{x, \"[\", y, \"]\"}], f@f[{x, \"[\", y, y2, \"]\"}]}"
 ;; substitution expression using groups 1 & 2 
 "\\1[\\2]")

Surely, you can write a specialized 20-line function for this problem of matching and substituting subtrees using subst and recursion, but if all that you want is cases similar to the presented one you can get away with a simple regex-based approach.

edited Sep 18, 2015 at 10:16

answered Sep 18, 2015 at 7:51

Vsevolod Dyomkin

9,4912 gold badges35 silver badges37 bronze badges

6 Comments

Lime Over a year ago

Thank you for the answer but I'm looking for pattern matching not REGEX.

Vsevolod Dyomkin Over a year ago

@William regex is pattern matching on strings. :)

Lime Over a year ago

You really shouldn't parse a gramar with REGEX stackoverflow.com/questions/1732348/…

Vsevolod Dyomkin Over a year ago

is there a grammar behind this? where's its spec?

Lime Over a year ago

The wolfram language spec(at least the basics of the grammar) I believe are described here

|

Collectives™ on Stack Overflow

A Replace Function in Lisp That Duplicates Mathematica Functionality

2 Answers 2

13 Comments

6 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

13 Comments

6 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related