2

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?

soundslikeodd
  • 1,078
  • 3
  • 19
  • 32
user7337963
  • 103
  • 1
  • 9

2 Answers2

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.

Community
  • 1
  • 1
coredump
  • 37,664
  • 5
  • 43
  • 77
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.

phipsgabler
  • 20,535
  • 4
  • 40
  • 60
  • Thank you so much!! is there a way that you know to don't display the `NIL` in the output? – user7337963 Jan 23 '17 at 20:50
  • @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. – Sylwester Jan 23 '17 at 21:15
  • @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 ! – user7337963 Jan 24 '17 at 07:18
  • @user7337963 That will work. You could also have defined the helper inside with [`labels`](http://www.lispworks.com/documentation/HyperSpec/Body/s_flet_.htm) – Sylwester Jan 24 '17 at 09:23