Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Reduce vs. Fold in Common Lisp

n16f.net

Post reply on HN
Print view View original

11–20 of 30 posts

Re: Reduce vs. Fold in Common Lisp

#11

Post by moonchild »

myco_logic wrote: post #10
ruricolist wrote: post #8

The history here is that Common Lisp gets reduce from APL ( https://aplwiki.com/wiki/Reduce ). It's not an attempt an ML-style fold, but a different formalism from a different lineage.

While reading this, I was immediately reminded of the reduce operator, glad to see my intuition wasn't far off. The nifty thing about this operator in the array-langs compared to the usual fold function is that they usually define identity elements for all primitive functions, which means that no initial value has to be provided: https://aplwiki.com/wiki/Identity_element The downside of this approach though, is that…

> downside of this approach though, is that using reduce with non-primitive functions can result in domain errors

Yes, that's another problem. There is precedent for associating metadata with user-defined functions (eg inverses); identities seem to have fallen by the wayside, but I am planning to fix that for j.

Re: Reduce vs. Fold in Common Lisp

#12

Post by pfdietz »

moonchild wrote: post #11
myco_logic wrote: post #10

Earlier quoted context omitted.

While reading this, I was immediately reminded of the reduce operator, glad to see my intuition wasn't far off. The nifty thing about this operator in the array-langs compared to the usual fold function is that they usually define identity elements for all primitive functions, which means that no initial value has to be provided: https://aplwiki.com/wiki/Identity_element The downside of this approach though, is that…

> downside of this approach though, is that using reduce with non-primitive functions can result in domain errors Yes, that's another problem. There is precedent for associating metadata with user-defined functions (eg inverses); identities seem to have fallen by the wayside, but I am planning to fix that for j.

Defining a number of related functions seems to be a pattern that comes up elsewhere. For example, consider functions that compute a hash value, canonicalize, and compute some notion of equality. It would be useful to associate all of these.

Re: Reduce vs. Fold in Common Lisp

#13

Post by 0x69420 »

myco_logic wrote: post #10
ruricolist wrote: post #8

The history here is that Common Lisp gets reduce from APL ( https://aplwiki.com/wiki/Reduce ). It's not an attempt an ML-style fold, but a different formalism from a different lineage.

While reading this, I was immediately reminded of the reduce operator, glad to see my intuition wasn't far off. The nifty thing about this operator in the array-langs compared to the usual fold function is that they usually define identity elements for all primitive functions, which means that no initial value has to be provided: https://aplwiki.com/wiki/Identity_element The downside of this approach though, is that…

> they usually define identity elements for all primitive functions > using reduce with non-primitive functions can result in domain errors

ml-style folds in the presence of ad-hoc polymorphism solve this rather handily -- in haskell for instance monoid is the typeclass that only requires an associative operation and an identity element

typeclasses have some clunkiness in this regard; you have to wrap numeric types as "sum" or "product" etc to go "ah yes today i want to say numbers are a monoid under this operation" but at the very least it does enable formal, user-defined associations between identity elements and functions

luckily most things programmers deal with are plausibly just one kind of monoid. for instance the eleventy billion different string types haskell programmers love to use all tend to satisfy monoid under concatenation without any wrappers

Re: Reduce vs. Fold in Common Lisp

#14

Post by moonchild »

pfdietz wrote: post #12
moonchild wrote: post #11

Earlier quoted context omitted.

> downside of this approach though, is that using reduce with non-primitive functions can result in domain errors Yes, that's another problem. There is precedent for associating metadata with user-defined functions (eg inverses); identities seem to have fallen by the wayside, but I am planning to fix that for j.

Defining a number of related functions seems to be a pattern that comes up elsewhere. For example, consider functions that compute a hash value, canonicalize, and compute some notion of equality. It would be useful to associate all of these.

Haskell calls these 'typeclasses'; cl calls them 'protocols'. Apl style is not to expose sophisticated user-level abstractions, so I think that there it is not inappropriate that the scope of associable objects (say, a monad, a dyad, an inverse, and an identity; perhaps a few others) be fixed by the language.

Re: Reduce vs. Fold in Common Lisp

#15

Post by dreamcompiler »

> It then applies the function to successive pairs of sequence elements.

No. #'reduce may take the first pair as an optimization step, but from that point on it processes sequence elements one at a time. It passes an accumulated value and the next sequence value to the function.

Re: Reduce vs. Fold in Common Lisp

#17

Post by Paul-Craft »

lispm wrote: post #16

so foldl is basically (defun foldl (function value sequence) (reduce function sequence :initial-value value))

Yeah, I'm not seeing what's so special either. Maybe it's that you do have to specify that initial value, so your return types are never something you don't expect?

Re: Reduce vs. Fold in Common Lisp

#18

Post by User23 »

I don't have a running image handy, but

  (+) ; => 0
  (*) ; => 1
and

  (+ n) ; => n
  (* n) ; => n
which I expect has some bearing on the behavior of reduce in the examples given.

It's pretty obvious that any other function could either have or be advised to have whatever equivalent semantics are appropriate.

Of course

  (apply #'+ '(1 2 3 4 5)) ; => 15
So reduce can be obviated by just letting the function take variable args too.

Re: Reduce vs. Fold in Common Lisp

#19

Post by lispm »

User23 wrote: post #18

I don't have a running image handy, but (+) ; => 0 (*) ; => 1 and (+ n) ; => n (* n) ; => n which I expect has some bearing on the behavior of reduce in the examples given. It's pretty obvious that any other function could either have or be advised to have whatever equivalent semantics are appropriate. Of course (apply #'+ '(1 2 3 4 5)) ; => 15 So reduce can be obviated by just letting the function take variable args…

> So reduce can be obviated by just letting the function take variable args too.

In Common Lisp the max number of arguments can be small.

  $ abcl
  Armed Bear Common Lisp 1.8.0
  Java 11.0.19 Ubuntu
  OpenJDK 64-Bit Server VM
  Low-level initialization completed in 0.304 seconds.
  Startup completed in 1.501 seconds.
  Type ":help" for a list of available commands.

  CL-USER(1): CALL-ARGUMENTS-LIMIT
  50

Re: Reduce vs. Fold in Common Lisp

#20

Post by nbernard »

lispm wrote: post #19
User23 wrote: post #18

I don't have a running image handy, but (+) ; => 0 (*) ; => 1 and (+ n) ; => n (* n) ; => n which I expect has some bearing on the behavior of reduce in the examples given. It's pretty obvious that any other function could either have or be advised to have whatever equivalent semantics are appropriate. Of course (apply #'+ '(1 2 3 4 5)) ; => 15 So reduce can be obviated by just letting the function take variable args…

> So reduce can be obviated by just letting the function take variable args too. In Common Lisp the max number of arguments can be small. $ abcl Armed Bear Common Lisp 1.8.0 Java 11.0.19 Ubuntu OpenJDK 64-Bit Server VM Low-level initialization completed in 0.304 seconds. Startup completed in 1.501 seconds. Type ":help" for a list of available commands. CL-USER(1): CALL-ARGUMENTS-LIMIT 50

Interesting. Do you know if that is due to constraints coming from ABCL running on a JVM, or is it an arbitrary choice ? (By contrast, SBCL on a x86_64 laptop returns 4611686018427387903...)
Post reply on HN