6

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

repeat
  • 18,496
  • 4
  • 54
  • 166
Lime
  • 13,400
  • 11
  • 56
  • 88
  • 1
    This *is* stackoverflow. – Scott Hunter Sep 15 '15 at 19:44
  • @ScottHunter Fixed here is the link to Mathematica.se post http://mathematica.stackexchange.com/questions/94720/duplicate-mathematica-functionality-in-mathematica-clone-or-lisp – Lime Sep 15 '15 at 19:47
  • Mind telling us what that Mathematica code *does*? And what you've tried that didn't work? – Joshua Taylor Sep 16 '15 at 00:18
  • It sounds like maybe you want [**subst-if**](http://www.lispworks.com/documentation/HyperSpec/Body/f_substc.htm). – Joshua Taylor Sep 16 '15 at 00:21
  • @JoshuaTaylor It replaces all instances of `f[{x_, "[", y__, "]"}]` where x_ represents a single variable and y__ represents one or more variables. – Lime Sep 16 '15 at 00:54
  • @William OK, but `f[{x_, "[", y__, "]"}]` isn't a Lisp object. What would the lisp counterpart be? Something like "every list of the form `(f x (y...))` is replaced by `(x y...)`? – Joshua Taylor Sep 16 '15 at 00:56
  • @JoshuaTaylor I think `(f (x_ "[" y__ "]"))` is the closest you can get without knowing the proper syntax for doing multiple or single replacements. – Lime Sep 16 '15 at 00:59
  • so actual "[" and "]" strings in there? – Joshua Taylor Sep 16 '15 at 00:59
  • Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/89751/discussion-between-william-and-joshua-taylor). – Lime Sep 16 '15 at 01:00
  • @JoshuaTaylor Yes. Give me a couple minutes and I'll post a self contained example. – Lime Sep 16 '15 at 01:20
  • **and get a return value of `((x y), (f (x y y2)))`.** What does the comma represent in that return value? – Joshua Taylor Sep 16 '15 at 12:14
  • @JoshuaTaylor ignore the comma – Lime Sep 16 '15 at 15:59
  • @Bill Sed just includes regex parsing(from my knowledge). If anything does this it will probably a lisp or maybe some variant of Haskell or something. – Lime Sep 17 '15 at 18:52
  • @Bill http://hyperpolyglot.org/lisp#lisp-macros It doesn't look that is natively supported. – Lime Sep 17 '15 at 23:33

2 Answers2

4

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))))
coredump
  • 37,664
  • 5
  • 43
  • 77
  • +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. – Lime Sep 18 '15 at 16:00
  • @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: https://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)`. – coredump Sep 21 '15 at 09:43
  • 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 Sep 21 '15 at 21:53
  • @William I made some changes. I hope this is sufficient for your need. – coredump Sep 22 '15 at 09:50
  • I'm going to let it automatically award you half the bounty because I appreciate the help but as it stands it doesn't work correctly all the time. For example try running the following `(match-replace '(a b (f (x "[" 1 2 3 "]")) (f (x "[" 1 2 3 "]")) c d) #'match-ugly-funcall :infinity)` it only replaces the first match and not both. I'm still amazed lisp doesn't have such functionality more or less built in to the program. `match-replace` looks quiet complex. – Lime Sep 24 '15 at 16:11
  • @William Oh... I thought Replace should quit as soon as one rule matched (vs. ReplaceAll; note the secondary return value which tells you if a match was found), so I tried very hard to stop as soon as possible (I don't have Mathematica to test things). Otherwise it would be simpler (mapcar). Lisp has subst-if, subst, which make sense for Lisp, but Mathematica is designed for other needs and you won't find exactly the same features without having to reimplement them. In particular, dealing with levelspec was verbose, but not difficult. – coredump Sep 24 '15 at 17:22
  • You can install [mathics](https://github.com/mathics/Mathics/wiki/Installing) if you you don't have Mathematica it supports most of the basic commands. I'll go ahead and give you the bounty if you don't mind fixing `match-replace` to replace all values. – Lime Sep 24 '15 at 17:28
  • @William Thanks for the link. I modified the answer. – coredump Sep 24 '15 at 18:29
  • 1
    It appears to work thanks! Is there a way to use a lambda instead of creating another function? – Lime Sep 24 '15 at 22:49
  • 1
    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? – Lime Sep 24 '15 at 23:14
  • @William Thanks. The case for rules as functions is to avoid limiting ourselves with what rules can match: you can rely on closures and generic functions too, if needed. Regarding your example, the one thing that is somewhat tricky is `y__` followed by `z__`, since there could be multiple ways to partition a list and bind the variables to different sublists. This can be done, but details matter. Depending on your needs, maybe Prolog is a better option. If you could narrow the scope of your question and tell us why you need this, you would certainly have more useful answers. – coredump Sep 25 '15 at 07:11
  • I'm trying to understand your code and I'm getting `undefined-function: LAST-ELT` – Lime Oct 09 '15 at 05:07
  • @Willam You can replace `(last-elt args)` with `(first(last args))` because `last` returns the last cons-cell. `last-elt` is part of the alexandria library. – coredump Oct 09 '15 at 05:22
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.

Vsevolod Dyomkin
  • 9,343
  • 2
  • 31
  • 36