CODEWITHSUNDEEP
lispcommon-lisp
Gavin
Gavin

Reputation: 2824

Compute euclidean distance with mapcar and apply

I am trying to create a function that computes this using apply and mapcar.

I am stuck after using the first mapcar to get all the differences of p-q in a list. How do I square all the elements in the list and sum them up?

enter image description here

(defun euclidean-distance-map (p q)
  ;; get a list of differences of p - q
  (mapcar #'- p q))

Upvotes: 0

Views: 697

Answers (3)

sds
sds

Reputation: 60004

Higher Order Functions

If you are really required to stick to HOFs (reduce & mapcar), then here are a few options:

(defun euclidean-distance-map (p q)
  (let ((d (mapcar #'- p q))) ; get a list of differences of p & q
    (sqrt (reduce #'+ (mapcar #'* d d)))))

(defun euclidean-distance-map (p q)
  (sqrt (reduce #'+ (mapcar (lambda (x) (* x x)) (mapcar #'- p q)))))

(defun euclidean-distance-map (p q)
  (sqrt (reduce #'+ (mapcar (lambda (x y)
                              (let ((d (- x y)))
                                (* d d)))
                            p q))))

apply vs reduce

Using apply instead of reduce is a bad idea (both because of call-arguments-limit and stylistically), but here you go:

(defun euclidean-distance-map (p q)
  (let ((d (mapcar #'- p q))) ; get a list of differences of p & q
    (sqrt (apply #'+ (mapcar #'* d d)))))

(defun euclidean-distance-map (p q)
  (sqrt (apply #'+ (mapcar (lambda (x) (* x x)) (mapcar #'- p q)))))

(defun euclidean-distance-map (p q)
  (sqrt (apply #'+ (mapcar (lambda (x y)
                             (let ((d (- x y)))
                               (* d d)))
                           p q))))

Memory

Without the proverbial "sufficiently smart compiler", mapcar allocates storage which is immediately discarded. This may not necessarily be a problem with a modern generational GC though.

Iteration

Note that the iterative version using loop is no less clear:

(defun euclidean-distance-map (p q)
  (sqrt (loop for x in p
          and y in q
          for d = (- x y)
          sum (* d d))))

Lisp is a multi-paradigm language, you do not have to force yourself into a specific framework.

Upvotes: 7

Tim
Tim

Reputation: 522

Here's a variation that uses higher-order functions and doesn't allocate a list for the differences:

(defun euclidian-distance (u v)
  (let ((sum 0.0))
    (mapc (lambda (x y)
            (let ((d (- x y)))
              (incf sum (* d d))))
          u
          v)
    (sqrt sum)))

Upvotes: 1

mobiuseng
mobiuseng

Reputation: 2386

coredump- actually answered it, but let's elaborate a bit. The problem can be split into the following tasks/steps (from the outermost to innermost):

  1. Calculate square root, that's we know: (sqrt .)
  2. To get ., we need to sum up squared differences. Here apply will do the work. We want (+ a1 a2 a3 ...), the problem is we don't know how many of the items we want to add. Assuming these items can be put into the list, can do (apply #'+ .). So, up to now we have (sqrt (apply #'+ .)).
  3. Now we need to square the differences and put the result into the list. This can be done by mapcar: (mapcar (lambda (x) (* x x)) .).
  4. Finally, this differences need to come from (mapcar #'- u v).

Overall,

(defun euclidian-distance (u v)
  (sqrt (apply #'+ (mapcar (lambda (x) (* x x)) (mapcar #'- u v)))))

> (euclidian-distance '(1 4 3) '(1 1 -1))
> 5.0

Upvotes: 2

Related Questions