Andrew Gwozdziewycz on 9 Aug 2007 13:35:29 -0000

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

[philly-lambda] Functional Reduce

  • From: "Andrew Gwozdziewycz" <>
  • To:
  • Subject: [philly-lambda] Functional Reduce
  • Date: Thu, 9 Aug 2007 09:35:18 -0400
  • Dkim-signature: a=rsa-sha1; c=relaxed/relaxed;; s=beta; h=domainkey-signature:received:received:message-id:date:from:to:subject:mime-version:content-type:content-transfer-encoding:content-disposition; b=ur1ZZgaoDTtntvQoRAqjEIMMOtEk7UF3koMBQitITXfn1PyD0qLdbTEiw/rSeKS+9pvWIp7iAiOVXgvgqc9BBhBq9iQam/IsHhMcdFzXp5aC+W4xnCjxCAMh0aJ+ZuJiZgr5JLefDsdBCMHRnD/N5Dlz24PqhsCretC+FV2oH3Q=
  • Domainkey-status: good (test mode)
  • Mailing-list: list; contact
  • Reply-to:
  • Sender:

I don't remember who said it, but someone last night mentioned that
reduce was inherently not functional due to the accumulation (and
mutation of that accumulation) of values.

When reduce (or fold if you will) "iterates" through the values of
list it applies the passed in function to the spot in the list it's at
and the accumulation so far. This fact makes it unparallelizable (I
think), unlike map, or filter, which do not accumulate any values, but
instead return "results" of subsequent calls.

Anyway reduce can actually be implemented functionally in Scheme with
recursion. Best yet, it's actually a tail call and so it can be
optimized (and in Scheme of course has to be).

(define (reduce func accum lst)
   ((null? lst) accum)
    (let ((accum-new (func (car lst) accum)))
      (reduce func accum-new (cdr lst))))))

;(reduce cons '() '(1 2 3)) => (3 2 1)
;(reduce + 0 '(1 2 3)) => 6

As with most functional functions, there exists a non recursive
version which would
require a mutated variable, but reduce is a tail call in scheme.

Hope this clears up some confusion...

Andrew Gwozdziewycz  |

You received this message because you are subscribed to the Google Groups "Philly Lambda" group.
To unsubscribe from this group, send email to
For more options, visit this group at