Common lisp: How to implement reduce

Question

I've been looking for this for days, basically I need to implement a function that does the same thing that the system function reduce does. This is what I have came up so far, but without an initial value i I can't get it to work.

Here is my code

(defun my-reduce (p i lista)
  (if (null lista)
       i
    (funcall p (car lista) (my-reduce p i (cdr lista)))))

By the way, it doesn't even work properly because it goes "backward" eg.:

(my-reduce #'list NIL '(1 2 3 4))

should return

(((1 2) 3) 4)

but I get

(1 (2 (3 (4 NIL))))

any idea?

Community · Accepted Answer · 2017-05-23 12:16:46Z

3

Left fold can be implemented with a simple iteration:

(defun my-fold-left (reducer initial list)
  (loop for fold = initial then (funcall reducer fold element)
        for element in list
        finally (return fold)))

For example:

(my-fold-left #'cons 0 '(1 2 3 4))
((((0 . 1) . 2) . 3) . 4)

(my-fold-left #'cons 0 '())
0

You can generalize and fold over vectors too if you use map:

(defun my-fold-left (reducer fold sequence)
  (map nil
       (lambda (e) (setf fold (funcall reducer fold e)))
       sequence)
  fold)

Just in case you did not read it, this answer has a nice high-level explanation of left and right fold.

edited May 23, 2017 at 12:16

CommunityBot

11 silver badge

answered Jan 24, 2017 at 6:52

coredump

39.4k7 gold badges47 silver badges85 bronze badges

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

3 Comments

user7337963 Over a year ago

Thank's! unfortunately i'm no allowed to use setf

coredump Over a year ago

You are allowed, outside of the class ;-)

user7337963 Over a year ago

Oh yes that's fore sure :) but unfortunately for all my class assignment i'm not allowed to use loops, set setf or setq... anyway i will keep in mind your answer

phipsgabler · Accepted Answer · 2017-01-24 12:24:02Z

1

I think you have implemented a correct right fold, as this is usually called, but want a left fold. Note the characteristic tail recursion, and using the "default" value as accumulator:

(defun my-left-reduce (f i xs)
  (if (null xs)
       i
    (my-left-reduce f (funcall f i (car xs)) (cdr xs))

(And I've never used Common Lisp, but the concept should be clear.)

Aside: usually it's the left fold that is considered "backwards". Compare (my-reduce cons NIL '(1 2 3)) and (my-left-reduce cons NIL '(1 2 3)). The latter should invert the original cons structure of the list.

edited Jan 24, 2017 at 12:24

answered Jan 23, 2017 at 20:45

phipsgabler

21.1k4 gold badges44 silver badges62 bronze badges

4 Comments

user7337963 Over a year ago

Thank you so much!! is there a way that you know to don't display the NIL in the output?

Sylwester Over a year ago

@user7337963 The standard function takes a keyword argument :initial-value if not set it would be as if you had called it with the cdr of the list and used the car as initial value. When the keyword argument :from-end is set to true it does the elements like a right fold.

user7337963 Over a year ago

@Sylwester thank you, I combined what you told me with phg's solution and i made a function with 2 arguments that call's my-reduce !

Sylwester Over a year ago

@user7337963 That will work. You could also have defined the helper inside with labels

Collectives™ on Stack Overflow

Common lisp: How to implement reduce

2 Answers 2

3 Comments

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related