preduce function sequence &key key from-end start end initial-value parts recurse

preduce (pronounced pee-reduce) is a parallel version of reduce. It chops up the input sequence into N parts and, in parallel, calls reduce on each part. The N partial results are then reduced again, either by reduce (the default) or, if the :recurse argument is non-nil, by preduce. The default value of N is the number of worker threads (the number given to make-kernel) which may be overridden by the :parts option.

(defpackage :example (:use :cl :lparallel))
(in-package :example)

(preduce '+ #(1 2 3 4 5 6) :parts 2)

is hand-wavingly similar to

(reduce '+ (vector (reduce '+ #(1 2 3))
                   (reduce '+ #(4 5 6))))

This code is misleading, of course: the two inner reduces are done in parallel, and the two inner arrays are displaced versions of the input array (no copying is done).

In order for the outcome of preduce to be independent of the choice of parts, the function passed must be associative with respect to the sequence elements and must produce an identity-like function when the :initial-value argument (if given) is partially applied. The latter condition is a consequence of :initial-value really meaning initial value per part.

(preduce '+ #(1 2 3 4 5 6) :parts 1 :initial-value 1)  ; => 22
(preduce '+ #(1 2 3 4 5 6) :parts 2 :initial-value 1)  ; => 23
(preduce '+ #(1 2 3 4 5 6) :parts 3 :initial-value 1)  ; => 24

In similar fashion, the :from-end option means from the end of each part.

The :start and :end arguments remain as they are in reduce, referring to the original input sequence.

The :key argument is thrown out while reducing the partial results. It applies to the first pass only.

preduce-partial is a variant of preduce which returns the unmolested partial results.

(preduce-partial '+ #(1 2 3 4 5 6) :parts 2)  ; => #(6 15)
(preduce-partial '+ #(1 2 3 4 5 6) :parts 3)  ; => #(3 7 11)

We can use preduce-partial to write premove-if for lists.

(defun premove-if* (test list)
  (reduce 'nreconc
          (preduce-partial (lambda (acc x)
                             (if (funcall test x)
                                 (cons x acc)))
                           :initial-value nil)
          :initial-value nil
          :from-end t))

It works as follows: after the partial results are returned by preduce-partial, each being a list in the reverse order of what we wish, we then walk backwards through the results, reversing and concatenating as we go.