0

I'm a newbie when it comes to programming in lisp and ill be honest recursion is not my forte, I was tasked with writing a function that would simplify arithmetic equations but not solve them. Here is the guidelines this is a school project by the way.

*Write function simplify that takes any arithmetic expression as described above (not just the examples shown) and returns a new function in which the following improvements are made, if they are possible:

  1. Multiplication sub-expression a. With a 0 as an argument, sub-expression is replaced by 0: (* 3 5 0) -> 0 b. With a 1 as an argument, the 1 is removed: (* 1 2 6) -> (* 2 6). If only one argument remains then the sub-expression is replaced by that argument: (* 1 6) -> 6

  2. Addition sub-expression a. Any occurrence of 0 is eliminated: (+ 0 2 7 7) -> (+ 2 7 7). If only one argument remains, the sub-expression is eliminated: (+ 0 7) -> 7

My group mates and I have written this so far :

(defun simplify (lis)
  (cond
   ((null lis) '())
   ((eq (car lis) '*)
    (cond
     ((not(null (member '0 lis))) 0)
     ((not(null (member '1 lis))) (simplify (remove '1 lis)))
     (t (simplify (cdr lis)))
     )
    )

   ((eq (car lis) '+)
    (cond
     (t 0)
     )
    )
   ((listp (car lis)) (cons (simplify (car lis))(simplify (cdr lis))))
   (t (cons (simplify (car lis)) (simplify (cdr lis))))

   )
  )

We cant get it to work Correctly if you have any suggestions! Thank you also you can ignore our + function that isn't finished.

Improve this question
3
  • In your t cases, you need to iterate over all the arguments, replacing them with the result of calling simplify on them. mapcar will be useful here. Commented Oct 29, 2015 at 1:33
  • could you explain a little further on what you mean by iterate over all the arguments Commented Oct 29, 2015 at 1:40
  • If you have (* (+ 3 0) (* 1 10)), you need to call simplify on (+ 3 0) and (* 1 10), so that you get (* 3 10). Commented Oct 29, 2015 at 1:47

1 Answer 1

Reset to default
1

It's always good to try to keep functions as simple and short as possible. So let's break up this task into multiple steps:

For both + and * there is an identity element, that you are supposed to remove from the operation (as it doesn't affect the result).

(defun remove-identity-elements (operands identity)
  (flet ((is-identity (element)
           (equal element identity)))
    (let ((filtered-operands (remove-if #'is-identity operands)))
      (or filtered-operands (list identity)))))

This function returns a list of operands with identity elements removed. Note that I added a check to avoid returning an empty list, so if the filtered-operands are an empty list (()) the or will evaluate its second argument, returning a list with the identity element as single member.

For an operation, if it's called with only a single operand, you're supposed to simplify that to only the single operand. That task is a good candidate for another function:

(defun compact-single-operand-operation (expression)
  (let ((operands (rest expression)))
    (if (rest operands)
      expression
      (first operands))))

Handling an operation can then be done by first removing any identity elements from the operands and then eventually removing the operation all together:

(defun simplify-operation (operator operands identity)
  (compact-single-operand-operation
   (cons operator (remove-identity-elements operands identity))))

With these functions ready at hand we can approach the simplify function. First of all, we need to cover its recursive nature:

In order to simplify an operation, you need to first simplify each of its operands, as they could be complex (simplify-able) operations, too.

(defun simplify (expression)
  (if (listp expression)
      (let ((operator (first expression))
            (operands (mapcar #'simplify (rest expression))))
        ;; handle operations
        )
      expression))

I'm using mapcar with the currently being defined function simplify to get already simplified operands. To stop this recursion we need a base case: If the expression to simplify isn't a list, then we consider it as "self evaluating" and just return it unchanged (this is the "else" part of the if).

Handling the operations is done using the above function simplify-operation, though we need to add a special check to cope with a possible 0 in the operands of a multiplication:

(cond ((eq operator '+) (simplify-operation '+ operands 0))
      ((eq operator '*)
       (if (find 0 operands)
           0
           (simplify-operation '* operands 1)))
      (t (error "Unsupported operation")))

I also put together a live example to play with.

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

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.