Why isn't there a fold-right?

[Yang Dong]

Maybe because Clojure has a vector, and conj conjoins new elements to
the end of the vector, so there's mere little use of fold-right. But,
fold-right is an abstraction tool, missing it in the core is kind of
pity.

[Michel Alexandre Salim]

fold-right and reduce-right are both called reduce in Clojure:
http://clojure.github.com/clojure/clojure.core-api.html#clojure.core/
reduce

Regards,

--
Michel Alexandre Salim, MSc., University of Erlangen-Nuremberg
Open Source Research Group, Applied Software Engineering
Web: http://osr.cs.fau.de, Email: michel...@cs.fau.de
GPG key ID: D09272F7

() ascii ribbon campaign - against html e-mail
/\ www.asciiribbon.org - against proprietary attachments

[Alan]

Clojure's reduce is fold-left, not fold-right. My suspicion is that
fold-right is not as amenable to laziness or to tail-call recursion as
fold-right, but I don't have much experience in the area so I could be
wrong.

What I'm surprised we're missing is unfold, not foldr: unfold is easy
to define lazily, and foldr can often be replaced with foldl.

On Nov 6, 6:33 pm, Michel Alexandre Salim <michael.silva...@gmail.com>
wrote:

> On Fri, 05 Nov 2010 19:03:20 -0700, Yang Dong wrote:
> > Maybe because Clojure has a vector, and conj conjoins new elements to
> > the end of the vector, so there's mere little use of fold-right. But,
> > fold-right is an abstraction tool, missing it in the core is kind of
> > pity.
>
> fold-right and reduce-right are both called reduce in Clojure:http://clojure.github.com/clojure/clojure.core-api.html#clojure.core/
> reduce
>
> Regards,
>
> --
> Michel Alexandre Salim, MSc., University of Erlangen-Nuremberg
> Open Source Research Group, Applied Software Engineering

> Web:http://osr.cs.fau.de,  Email: michel.sa...@cs.fau.de

[Michael Gardner]

What's wrong with just using reverse?

[Laurent PETIT]

2010/11/7 Alan <al...@malloys.org>:

> Clojure's reduce is fold-left, not fold-right. My suspicion is that
> fold-right is not as amenable to laziness or to tail-call recursion as
> fold-right, but I don't have much experience in the area so I could be
> wrong.
>
> What I'm surprised we're missing is unfold, not foldr: unfold is easy
> to define lazily, and foldr can often be replaced with foldl.

There's iterate, which seems to be like unfold (minus the recursion
stopping predicate)

>
> On Nov 6, 6:33 pm, Michel Alexandre Salim <michael.silva...@gmail.com>
> wrote:
>> On Fri, 05 Nov 2010 19:03:20 -0700, Yang Dong wrote:
>> > Maybe because Clojure has a vector, and conj conjoins new elements to
>> > the end of the vector, so there's mere little use of fold-right. But,
>> > fold-right is an abstraction tool, missing it in the core is kind of
>> > pity.
>>
>> fold-right and reduce-right are both called reduce in Clojure:http://clojure.github.com/clojure/clojure.core-api.html#clojure.core/
>> reduce
>>
>> Regards,
>>
>> --
>> Michel Alexandre Salim, MSc., University of Erlangen-Nuremberg
>> Open Source Research Group, Applied Software Engineering
>> Web:http://osr.cs.fau.de,  Email: michel.sa...@cs.fau.de
>>                 GPG key ID: D09272F7
>>
>> ()  ascii ribbon campaign - against html e-mail
>> /\  www.asciiribbon.org  - against proprietary attachments
>

> --
> You received this message because you are subscribed to the Google
> Groups "Clojure" group.
> To post to this group, send email to clo...@googlegroups.com
> Note that posts from new members are moderated - please be patient with your first post.
> To unsubscribe from this group, send email to
> clojure+u...@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/clojure?hl=en

[Ken Wesson]

On Sun, Nov 7, 2010 at 3:04 AM, Laurent PETIT <lauren...@gmail.com> wrote:
> 2010/11/7 Alan <al...@malloys.org>:
>> Clojure's reduce is fold-left, not fold-right. My suspicion is that
>> fold-right is not as amenable to laziness or to tail-call recursion as
>> fold-right, but I don't have much experience in the area so I could be
>> wrong.
>>
>> What I'm surprised we're missing is unfold, not foldr: unfold is easy
>> to define lazily, and foldr can often be replaced with foldl.
>
> There's iterate, which seems to be like unfold (minus the recursion
> stopping predicate)

And then there's (take-while #(not (stop-pred %)) (iterate f start)).

[David Sletten]

You could define a naive 'foldr' like this:
(defn foldr [f coll]
(if (empty? (rest coll))
(first coll)
(f (first coll) (foldr f (rest coll)))) )

(foldr list '(1 2 3 4)) => (1 (2 (3 4)))
(foldr - [1 2 3 4]) => -2

However, this is not a tail-recursive function and will be limited by the size of the stack.

An alternative involves reversing the sequence and applying the function with its arguments reversed. Then we can just pretend that we are doing a left fold and use 'reduce':
(defn foldr [f coll]
(reduce (fn [x y] (f y x)) (reverse coll)))

Or for those of you who prefer that other people won't be able to read your code:
(defn foldr [f coll]
(reduce #(f %2 %1) (reverse coll)))

Have all good days,
David Sletten

[iko...@gmail.com]

2010/11/7 David Sletten <da...@bosatsu.net>

Or for those of you who prefer that other people won't be able to read your code:
(defn foldr [f coll]
 (reduce #(f %2 %1) (reverse coll)))

To be honest, I find this one more readable... 

[nicola...@gmail.com]

On Sun, Nov 7, 2010 at 3:28 PM, iko...@gmail.com <iko...@gmail.com> wrote:
> 2010/11/7 David Sletten <da...@bosatsu.net>
>>
>> Or for those of you who prefer that other people won't be able to read
>> your code:
>> (defn foldr [f coll]
>>  (reduce #(f %2 %1) (reverse coll)))
>>
>

fold-right can not be made tail-recursive and in one-pass at the same time.
reverse and reduce is a good way to do it.

[Yang Dong]

If that's the case, I can accept it. Thank you guys :)

On Nov 8, 2:18 am, "nicolas.o...@gmail.com" <nicolas.o...@gmail.com>
wrote:

[tpeng]

but this foldr can't handle the infinite list, am i right?

On Nov 8, 2:18 am, "nicolas.o...@gmail.com" <nicolas.o...@gmail.com>
wrote:

> On Sun, Nov 7, 2010 at 3:28 PM, iko...@gmail.com <iko...@gmail.com> wrote:
> > 2010/11/7 David Sletten <da...@bosatsu.net>
>
> >> Or for those of you who prefer that other people won't be able to read
> >> your code:

> >> (defnfoldr[f coll]

[Alex Osborne]

tpeng <peng...@gmail.com> writes:

>> (defn foldr [f coll]

>> (reduce #(f %2 %1) (reverse coll)))

> but this foldr can't handle the infinite list, am i right?

Correct. In a lazily evaluated language like Haskell you can have a
combining function which doesn't always evaluate its arguments and thus
only partially uses the list. Clojure is eagerly evaluated, so we can't
do it quite the same way.

We can of course achieve much the same effect by explicitly delaying
evaluation using closures. This is how lazy-seq works. For example, if
we make the second argument to the combining function a closure:

(defn lazy-foldr [f val coll]
(if-let [[x & xs] coll]
(f x #(lazy-foldr f val xs))
val))

;; Finite seq of trues
(lazy-foldr #(and %1 (%2)) true [true true])
;; => true

;; Infinite seq of falses
(lazy-foldr #(and %1 (%2)) true (repeat false))
;; => false

[nicola...@gmail.com]

On Fri, Nov 26, 2010 at 5:28 PM, tpeng <peng...@gmail.com> wrote:
> but this foldr can't handle the infinite list, am i right?
>

I doubt there is a foldr that handles the infinite list.
To do anything, it would have to read at least one element: the last.

Alex nice answer is a foldl.

[Alex Osborne]

"nicola...@gmail.com" <nicola...@gmail.com> writes:

> I doubt there is a foldr that handles the infinite list.
> To do anything, it would have to read at least one element: the last.
>
> Alex nice answer is a foldl.

Actually I think you have them backwards. Wikipedia has a pair of
diagrams which I find very useful for visualising which is which:

foldr:
http://en.wikipedia.org/wiki/File:Right-fold-transformation.png

foldl (reduce in Clojure):
http://en.wikipedia.org/wiki/File:Left-fold-transformation.png

Look at the right side of the diagram. That's the call structure. (The
left side of the diagram is the linked list (1 2 3 4 5). The ":" just
means cons in Haskell syntax.)

With a foldr the outermost call is given the first element of the list,
so mine is definitely a foldr.

Let's use (and) as the combining function and use an infinite list that
begins [true true false false ...]. So that looks like:

(lazy-foldr #(and %1 (%2)) nil (cycle [true true false false]))

We can draw an ASCII call structure diagram in the same form as the
Wikipedia one and see this:

and
/ \
T and
/ \
T and
/ \
F (not evaluated)

Since (and) short-circuits when given false, only the part of the list
up to the first false is evaluated.

There's probably not much practical use for lazy-foldr. But it was fun
to write. :-)

[tpeng]

thanks Alex for this nice foldr. ;-)

however this lazy-foldr can only be used when the fn can stop by
itself (in this case, it's 'and' which is short-circuited) otherwise
lazy-foldr will never get stop.
i think for a good foldr, the evaluation of #(lazy-foldr f val xs)
should be only forced when necessary?

On Nov 27, 6:44 pm, Alex Osborne <a...@meshy.org> wrote:

[Laurent PETIT]

Hello,

clojure is not lazy on evaluation of arguments by default, so I think this is not possible to do this "transparently".

Using delay/force could help, but this would not be "transparent" at all for the writer of the fn ;-)

2010/11/27 tpeng <peng...@gmail.com>

[tpeng]

i have a one:
(defn lazy-foldr [f coll]
(lazy-seq

(if-let [[x & xs] coll]

(cons x (lazy-foldr f xs)))))

it seems works so far ;-p

On Nov 28, 4:01 pm, Laurent PETIT <laurent.pe...@gmail.com> wrote:
> Hello,
>
> clojure is not lazy on evaluation of arguments by default, so I think this
> is not possible to do this "transparently".
>
> Using delay/force could help, but this would not be "transparent" at all for
> the writer of the fn ;-)
>

> 2010/11/27 tpeng <pengt...@gmail.com>

> > clojure+u...@googlegroups.com<clojure%2Bunsu...@googlegroups.com>

[Asim Jalis]

This looks like map rather than foldr.

[Meikel Brandmeyer]

Hi,

Am 28.11.2010 um 21:33 schrieb Asim Jalis:

> This looks like map rather than foldr.
>
> On Sun, Nov 28, 2010 at 7:40 AM, tpeng <peng...@gmail.com> wrote:
>> i have a one:
>> (defn lazy-foldr [f coll]
>> (lazy-seq
>> (if-let [[x & xs] coll]
>> (cons x (lazy-foldr f xs)))))
>>
>> it seems works so far ;-p

This is just mapping the identity over the input seq. ;-p And it also gives a wrong result for an input coll like [].

Sincerely
Meikel

[Tassilo Horn]

Yoshinori Kohyama <yyko...@gmail.com> writes:

Hi!

> Here is my fold-right.
>
> (defn fold-right [f s coll]
> ((reduce (fn [acc x] #(acc (f x %))) identity coll) s))

Very elegant, but sadly it blows the stack on larger collections. On my
system, the threshold is somewhere beetween 15.000 and 16.000 elements.

Something much less elegant (and slower in cases where your variant also
does the trick) is:

(defn fold-right [f s coll]
(reduce #(f %2 %1) s (reverse coll)))

Bye,
Tassilo

[Yoshinori Kohyama]

Hello Tassilo and All,

Thank you for your comment.

Yes, it is sorry that my 'fold-right' eat large stack.

Using 'reverse' is good.

But I think 'reverse' is a special case of 'fold-right'.

(fold-right #(concat %2 (list %)) '() '(:a :b :c :d))

; -> (:d :c :b :a)

If clojure's implementation of reverse don't consume stack, how does it do?

https://github.com/clojure/clojure/blob/d0c380d9809fd242bec688c7134e900f0bbedcac/src/clj/clojure/core.clj#L883

The source of 'reverse' says it uses 'reduce1' and commented "Not lazy".

https://github.com/clojure/clojure/blob/d0c380d9809fd242bec688c7134e900f0bbedcac/src/clj/clojure/core.clj#L865

The source of 'reduce1' says it uses 'chunk-seq?', '.reduce', 'chunk-first' and 'chunk-next'.

What are these?

And is there any lazy solution?

Regards,

Yoshinori Kohyama

[OGINO Masanori]

Hello.

2012/6/11 Yoshinori Kohyama <yyko...@gmail.com>:

> If clojure's implementation of reverse don't consume stack, how does it do?

`reduce1` is a recursive function using `recur`, explicit tail
recursion with optimization. So it doesn't.

> The source of 'reverse' says it uses 'reduce1' and commented "Not lazy".

Yes. `reverse` must be strict, because all elements must be realized
(the value is computed) when you reverse a sequence.

> The source of 'reduce1' says it uses 'chunk-seq?', '.reduce', 'chunk-first'
> and 'chunk-next'.
> What are these?

See clojure.lang.{IChunk,IChunkedSeq}.

> And is there any lazy solution?

Probably no. Both `fold-right` and `reverse` must be strict IMHO.

--
OGINO Masanori <masanor...@gmail.com>
http://twitter.com/omasanori

[Yoshinori Kohyama]

Hi O. Masanori and all,

Thank you so much for your kindly explanation.

Sure that 'fold-right' itself is strict as you say.

But I think that various right-folded-type loops, which can be stopped middle of a list, can be lazy.

The continuation, which should be calculated in the later steps, should be determined when the list is searched to that point from head of it.

https://gist.github.com/2894687

https://gist.github.com/2896939

Does anyone have an idea not to eat large stack with an abstraction for these loops?

[Yoshinori Kohyama]

Hi all.

Sorry for mere my continued report.

Instead of reversing operands, I tried accumulating operators and reversing and applying it when stopping.

https://gist.github.com/2896939

It doesn't consume stack. (but heap...)

Regards,

Yoshinori Kohyama

[Tassilo Horn]

Yoshinori Kohyama <yyko...@gmail.com> writes:

Hi!

> Sorry for mere my continued report.

No apologies needed. It's very interesting.

> Instead of reversing operands, I tried accumulating operators and
> reversing and applying it when stopping.
> https://gist.github.com/2896939
> It doesn't consume stack. (but heap...)

Very interesting again. The theory should be that you iterate the
collection only once to create a big composition of function that
already know one of their args. However, you have to reverse the list
of functions, which destroys the theoretical benefit.

user> (time (reduce-right - (range 2000000)))
"Elapsed time: 6375.358049 msecs"
-1000000

So use a vector and conjoin to the tail instead of consing to a list
that later needs to be reversed.

https://gist.github.com/2908767

With that, I get this result:

user> (time (reduce-right - (range 2000000)))
"Elapsed time: 3352.812468 msecs"
-1000000

But still my reverse-the-collection-and-then-reduce-it approach is still
much faster, although it has to iterate the collection twice.

user> (time (foldr - 0 (range 2000000)))
"Elapsed time: 831.605479 msecs"
-1000000

I'm not exactly sure why, but I'd guess the allocation overhead for 2
million partial functions is rather expensive.

Bye,
Tassilo

[Yoshinori Kohyama]

Hello Tassilo and all again,

Thank you for your kind words to me and useful consideration.

However, you have to reverse the list
of functions, which destroys the theoretical benefit.

Exactly! 

 

But still my reverse-the-collection-and-then-reduce-it approach is still
much faster, although it has to iterate the collection twice. 

 

It seems to make things faster using a '(transient [])'.

Thank you.

 

I'm not exactly sure why, but I'd guess the allocation overhead for 2
million partial functions is rather expensive.

Allocation of partial functions is expensive as you say.

May it be that 'conj'ing an element at the last of a collection still takes much cost than 'cons'ing

an element at the head of it and reversing?

I'll keep thinking and trying.

Regards,

Yoshinori Kohyama

 

[Tassilo Horn]

Yoshinori Kohyama <yyko...@gmail.com> writes:

>> But still my reverse-the-collection-and-then-reduce-it approach is
>> still much faster, although it has to iterate the collection twice.
>
> It seems to make things faster using a '(transient [])'. Thank you.

The main difference is that I build up a new vector of functions instead
of a list of functions in order not to have to reverse it.

I just tried without the transient (i.e., a plain persistent vector),
and it doesn't really change the timings. So I'd conclude that building
up a new vector is cheap in comparison to the function allocations.

>> I'm not exactly sure why, but I'd guess the allocation overhead for 2
>> million partial functions is rather expensive.
>
> Allocation of partial functions is expensive as you say. May it be
> that 'conj'ing an element at the last of a collection still takes much
> cost than 'cons'ing an element at the head of it and reversing?

No, for vectors conjoining to the tail is the most efficient
"add"-operation. Consing to a list is probably a bit more efficient,
but consing and then reversing is surely not.

> I'll keep thinking and trying.

Great, I really enjoy your solutions.

Bye,
Tassilo

[Meikel Brandmeyer (kotarak)]

Hi,

Am Montag, 11. Juni 2012 10:04:59 UTC+2 schrieb Tassilo Horn:

The main difference is that I build up a new vector of functions instead
of a list of functions in order not to have to reverse it.

You should probably inline comp for your purposes. Note the reverse call there.

https://github.com/clojure/clojure/blob/d0c380d9809fd242bec688c7134e900f0bbedcac/src/clj/clojure/core.clj#L2267
 
Kind regards,
Meikel

[Yoshinori Kohyama]

Hi Meikel,

Thank you for pointing it out that 'comp' calls 'reverse' internally.

I've been calling 'reverse' twice.

Appreciate you so much.

I'll try 'comp'ing the accumulated functions manually without 'reverse'.

Regards,

Yoshinori Kohyama

[Tassilo Horn]

"Meikel Brandmeyer (kotarak)" <m...@kotka.de> writes:

>> The main difference is that I build up a new vector of functions
>> instead of a list of functions in order not to have to reverse it.
>>
>
> You should probably inline comp for your purposes. Note the reverse
> call there.
>
> https://github.com/clojure/clojure/blob/d0c380d9809fd242bec688c7134e900f0bbedcac/src/clj/clojure/core.clj#L2267

Oh, that's a pity. I'd much vote for a left-to-right version
complementing the current right-to-left `comp`.

I also have at least one function in my code I know from the top of my
head where I reverse a seq of functions before feeding them to (apply
comp ...). In my case, the seq of functions is usually user-supplied,
so probably rather small.

Bye,
Tassilo

[Tassilo Horn]

Tassilo Horn <tas...@member.fsf.org> writes:

>> You should probably inline comp for your purposes. Note the reverse
>> call there.
>>
>> https://github.com/clojure/clojure/blob/d0c380d9809fd242bec688c7134e900f0bbedcac/src/clj/clojure/core.clj#L2267
>
> Oh, that's a pity. I'd much vote for a left-to-right version
> complementing the current right-to-left `comp`.

I created a JIRA issue and added a patch:

http://dev.clojure.org/jira/browse/CLJ-1010

Bye,
Tassilo

[Tassilo Horn]

Now that's strange. If I adapt Yoshinori's code to use a list again and
the left-to-right `comp*` instead of the reversing `comp`, I expected to
get a reasonable benefit. I.e., that's the new code
(https://gist.github.com/2908767).

--8<---------------cut here---------------start------------->8---
(defn r-reduce [init updt pred retn f coll]
(loop [stat init [h & r :as curr] coll acc (list identity)]
(if (or (pred stat) (nil? r))
;; comp* is left-to-right, so it doesn't reverse
((apply comp* acc) (retn curr))
(recur (updt stat) r (cons (partial f h) acc)))))

(defn reduce-right [f coll]
(r-reduce coll next nil? first f coll))
--8<---------------cut here---------------end--------------->8---

and that's the old version:

--8<---------------cut here---------------start------------->8---
(defn r-reduce-old [init updt pred retn f coll]
(loop [stat init [h & r :as curr] coll acc (vector identity)]
(if (or (pred stat) (nil? r))
;; Will reverse acc
((apply comp acc) (retn curr))
(recur (updt stat) r (conj acc (partial f h))))))

(defn reduce-right-old [f coll]
(r-reduce-old coll next nil? first f coll))
--8<---------------cut here---------------end--------------->8---

This seems to prove that `comp*` is much faster than `comp` if there are
many functions:

--8<---------------cut here---------------start------------->8---
user> (time (apply comp* (take 2000000 (repeat identity))))
"Elapsed time: 0.078991 msecs"
#<core$comp_STAR_$fn__4071 clojure.core$comp_STAR_$fn__4071@74cee5ed>
user> (time (apply comp (take 2000000 (repeat identity))))
"Elapsed time: 1515.573253 msecs"
#<core$comp_STAR_$fn__4071 clojure.core$comp_STAR_$fn__4071@4cb8cd94>
--8<---------------cut here---------------end--------------->8---

But strangely, this 1.5 second benefit is completely lost somewhere:

--8<---------------cut here---------------start------------->8---
user> (time (reduce-right-old - (range 2000000)))
"Elapsed time: 3992.088322 msecs"
-1000000

user> (time (reduce-right - (range 2000000)))

"Elapsed time: 4125.689783 msecs"
-1000000
--8<---------------cut here---------------end--------------->8---

Can someone enlighten me what's happening?

Thanks,
Tassilo

[Yoshinori Kohyama]

Hi Tassilo and all.

I'm testing some code.

It seems that the clojure runtime remembers some results of calculation.

For an exact comparison, please do

1) Exec java clojure.main

2) Exec one version of a function

3) Quit java clojure.main

4) Exec java clojure.main

5) Exec another version of the function

instead of sequencial tests of multiple versions of a function in one runtime.

Or do sequencial tests of multiple versions of a function in the reverse order.

Regards,

Yoshinori Kohyama

[Meikel Brandmeyer (kotarak)]

Hi,

I propose to use criterium to do benchmarking. https://clojars.org/criterium

The restart of the JVM should not be necessary. You normally need just enough warm-up rounds. criterium (mostly) takes care of such details.

Kind regards
Meikel

[Tassilo Horn]

"Meikel Brandmeyer (kotarak)" <m...@kotka.de> writes:

Hi Meikel,

> I propose to use criterium to do
> benchmarking. https://clojars.org/criterium

Thanks for the hint. The short answer is that the creation of a
function composition using `comp*` (see patch attached to CLJ-1010) is
much, much faster than creating it with `comp`, which is expected cause
there's no `reverse`. However, applying the composition created with
`comp` is ~2.5 times faster than applying the composition created with
`comp*`. To make it even stranger, with my patch the arbitrary arity
version of `comp` just calls

(apply comp* (reverse (list* f1 f2 f3 fs)))

so there shouldn't be a difference. Well ok, `reverse` will eliminate
lazyness, but in my code from the last post, I'm constructing the list
of functions to compose by cons-ing to a list recursively, so there
shouldn't be lazyness involved. I also tried conjoining to a list
(because it seems iterating a clojure.lang.Cons is slower than iterating
a clojure.lang.PersistentList), but that doesn't seem to change
anything.

Below are all the hairy details...

Bye,
Tassilo

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

I've done benchmarking with criterium now, and the following suggests
that the left-to-right function composition `comp*` is created much
faster than the right-to-left version `comp` which needs to reverse the
seq of fns first.

--8<---------------cut here---------------start------------->8---
r-reduce> (do
(bench (apply comp* (take 200000 (repeat identity))) :verbose)
(println "----------------------------------------")
(bench (apply comp (take 200000 (repeat identity))) :verbose))
amd64 Linux 3.4.0-gentoo 2 cpu(s)
OpenJDK 64-Bit Server VM 22.0-b10
Runtime arguments: -agentlib:jdwp=transport=dt_socket,server=y,suspend=n -XX:+TieredCompilation -Xmx1G -Dclojure.compile.path=/home/horn/Repos/clj/testi/target/classes -Dtesti.version=0.1.0-SNAPSHOT -Dclojure.debug=false
Evaluation count : 7609380
Execution time mean : 7.894850 us 95.0% CI: (7.892085 us, 7.897481 us)
Execution time std-deviation : 278.514554 ns 95.0% CI: (275.961233 ns, 282.746932 ns)
Execution time lower ci : 7.650744 us 95.0% CI: (7.649851 us, 7.650744 us)
Execution time upper ci : 8.423008 us 95.0% CI: (8.423008 us, 8.432979 us)

Found 5 outliers in 60 samples (8.3333 %)
low-severe 2 (3.3333 %)
low-mild 3 (5.0000 %)
Variance from outliers : 22.1941 % Variance is moderately inflated by outliers
----------------------------------------
amd64 Linux 3.4.0-gentoo 2 cpu(s)
OpenJDK 64-Bit Server VM 22.0-b10
Runtime arguments: -agentlib:jdwp=transport=dt_socket,server=y,suspend=n -XX:+TieredCompilation -Xmx1G -Dclojure.compile.path=/home/horn/Repos/clj/testi/target/classes -Dtesti.version=0.1.0-SNAPSHOT -Dclojure.debug=false
Evaluation count : 780
Execution time mean : 81.983797 ms 95.0% CI: (81.961708 ms, 82.003751 ms)
Execution time std-deviation : 2.200307 ms 95.0% CI: (2.190147 ms, 2.210750 ms)
Execution time lower ci : 77.945103 ms 95.0% CI: (77.945103 ms, 77.945103 ms)
Execution time upper ci : 85.109668 ms 95.0% CI: (85.109668 ms, 85.109668 ms)
nil
--8<---------------cut here---------------end--------------->8---

So `comp*` is about 10.000 times faster than `comp` when creating
compositions.

But that doesn't change too much. If I use the two implementations of
my last post and these two benchmarking fns...

--8<---------------cut here---------------start------------->8---
(defn reduce-right-with-comp*
"Conses to a list of fns and uses (apply comp* list-of-fns)."
[]
(reduce-right - (range 200000)))

(defn reduce-right-with-comp []
"Conjoins to a vector of fns and uses (apply comp vec-of-fns) which
reverses the vector."
(reduce-right-old - (range 200000)))
--8<---------------cut here---------------end--------------->8---

... I get:

--8<---------------cut here---------------start------------->8---
r-reduce> (do
(bench (reduce-right-with-comp*) :verbose)
(println "----------------------------------------")
(bench (reduce-right-with-comp) :verbose))
amd64 Linux 3.4.0-gentoo 2 cpu(s)
OpenJDK 64-Bit Server VM 22.0-b10
Runtime arguments: -agentlib:jdwp=transport=dt_socket,server=y,suspend=n -XX:+TieredCompilation -Xmx1G -Dclojure.compile.path=/home/horn/Repos/clj/testi/target/classes -Dtesti.version=0.1.0-SNAPSHOT -Dclojure.debug=false
Evaluation count : 420
Execution time mean : 167.787313 ms 95.0% CI: (167.713185 ms, 167.874011 ms)
Execution time std-deviation : 8.172843 ms 95.0% CI: (8.095159 ms, 8.231008 ms)
Execution time lower ci : 156.327257 ms 95.0% CI: (156.327257 ms, 156.327257 ms)
Execution time upper ci : 184.392968 ms 95.0% CI: (184.162446 ms, 184.392968 ms)

Found 5 outliers in 60 samples (8.3333 %)
low-severe 3 (5.0000 %)
low-mild 2 (3.3333 %)
Variance from outliers : 35.1910 % Variance is moderately inflated by outliers
----------------------------------------
amd64 Linux 3.4.0-gentoo 2 cpu(s)
OpenJDK 64-Bit Server VM 22.0-b10
Runtime arguments: -agentlib:jdwp=transport=dt_socket,server=y,suspend=n -XX:+TieredCompilation -Xmx1G -Dclojure.compile.path=/home/horn/Repos/clj/testi/target/classes -Dtesti.version=0.1.0-SNAPSHOT -Dclojure.debug=false
Evaluation count : 360
Execution time mean : 193.625805 ms 95.0% CI: (193.566549 ms, 193.688350 ms)
Execution time std-deviation : 7.953619 ms 95.0% CI: (7.911386 ms, 7.989930 ms)
Execution time lower ci : 184.161529 ms 95.0% CI: (184.161529 ms, 184.161529 ms)
Execution time upper ci : 209.447091 ms 95.0% CI: (209.430756 ms, 209.447091 ms)

Found 2 outliers in 60 samples (3.3333 %)
low-severe 2 (3.3333 %)
Variance from outliers : 27.0944 % Variance is moderately inflated by outliers
nil
--8<---------------cut here---------------end--------------->8---

So here, the version with `comp*` is about 25 ms faster. Considering
the first benchmark, I expected it to be about 80 ms faster, because
`(apply comp seq-of-200000-fn)` takes about 80 ms longer than the same
using `comp*`. [I assume that consing or conjoining to a list is about
the same as conjoining to a vector... In fact, its faster, so the
benefit should be even greater than 80 ms.]

Even stranger, if I increase the number to one million, the
vector-with-comp version is slightly faster.

--8<---------------cut here---------------start------------->8---
r-reduce> (do
(bench (reduce-right-with-comp*) :verbose)
(println "----------------------------------------")
(bench (reduce-right-with-comp) :verbose))
amd64 Linux 3.4.0-gentoo 2 cpu(s)
OpenJDK 64-Bit Server VM 22.0-b10
Runtime arguments: -agentlib:jdwp=transport=dt_socket,server=y,suspend=n -XX:+TieredCompilation -Xmx1G -Dclojure.compile.path=/home/horn/Repos/clj/testi/target/classes -Dtesti.version=0.1.0-SNAPSHOT -Dclojure.debug=false
Evaluation count : 60
Execution time mean : 1.437824 sec 95.0% CI: (1.435744 sec, 1.439028 sec)
Execution time std-deviation : 238.811129 ms 95.0% CI: (237.060303 ms, 240.253146 ms)
Execution time lower ci : 1.221996 sec 95.0% CI: (1.221996 sec, 1.221996 sec)
Execution time upper ci : 1.923629 sec 95.0% CI: (1.921390 sec, 1.923629 sec)

Found 3 outliers in 60 samples (5.0000 %)
low-severe 3 (5.0000 %)
Variance from outliers : 87.5968 % Variance is severely inflated by outliers
----------------------------------------
amd64 Linux 3.4.0-gentoo 2 cpu(s)
OpenJDK 64-Bit Server VM 22.0-b10
Runtime arguments: -agentlib:jdwp=transport=dt_socket,server=y,suspend=n -XX:+TieredCompilation -Xmx1G -Dclojure.compile.path=/home/horn/Repos/clj/testi/target/classes -Dtesti.version=0.1.0-SNAPSHOT -Dclojure.debug=false
Evaluation count : 60
Execution time mean : 1.345220 sec 95.0% CI: (1.343476 sec, 1.347048 sec)
Execution time std-deviation : 200.290969 ms 95.0% CI: (198.836108 ms, 202.075390 ms)
Execution time lower ci : 1.139444 sec 95.0% CI: (1.139444 sec, 1.139444 sec)
Execution time upper ci : 1.929759 sec 95.0% CI: (1.929753 sec, 1.929759 sec)

Found 6 outliers in 60 samples (10.0000 %)
low-severe 1 (1.6667 %)
low-mild 5 (8.3333 %)
Variance from outliers : 84.1513 % Variance is severely inflated by outliers
nil
--8<---------------cut here---------------end--------------->8---

If I increase the numbers even more, then the vector-with-comp variant
enlarges its advance.

This suggests that while `comp*` is much faster in creating a function
composition, the function it created is much slower when being applied.
The following benchmark seems to support that claim.

--8<---------------cut here---------------start------------->8---
r-reduce> (let [f1 (apply comp* (take 1000000 (repeat inc)))
f2 (apply comp (take 1000000 (repeat inc)))]
(bench (f1 0) :verbose)
(println "---------------------------------------")
(bench (f2 0) :verbose))
amd64 Linux 3.4.0-gentoo 2 cpu(s)
OpenJDK 64-Bit Server VM 22.0-b10
Runtime arguments: -agentlib:jdwp=transport=dt_socket,server=y,suspend=n -XX:+TieredCompilation -Xmx1G -Dclojure.compile.path=/home/horn/Repos/clj/testi/target/classes -Dtesti.version=0.1.0-SNAPSHOT -Dclojure.debug=false
Evaluation count : 540
Execution time mean : 125.550362 ms 95.0% CI: (125.534153 ms, 125.565505 ms)
Execution time std-deviation : 1.539032 ms 95.0% CI: (1.524641 ms, 1.550026 ms)
Execution time lower ci : 123.563049 ms 95.0% CI: (123.539807 ms, 123.563049 ms)
Execution time upper ci : 128.757621 ms 95.0% CI: (128.757621 ms, 128.781272 ms)

Found 6 outliers in 60 samples (10.0000 %)
low-severe 5 (8.3333 %)
low-mild 1 (1.6667 %)
Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
---------------------------------------
amd64 Linux 3.4.0-gentoo 2 cpu(s)
OpenJDK 64-Bit Server VM 22.0-b10
Runtime arguments: -agentlib:jdwp=transport=dt_socket,server=y,suspend=n -XX:+TieredCompilation -Xmx1G -Dclojure.compile.path=/home/horn/Repos/clj/testi/target/classes -Dtesti.version=0.1.0-SNAPSHOT -Dclojure.debug=false
Evaluation count : 1260
Execution time mean : 48.581007 ms 95.0% CI: (48.563129 ms, 48.599636 ms)
Execution time std-deviation : 1.846413 ms 95.0% CI: (1.829196 ms, 1.860582 ms)
Execution time lower ci : 47.463785 ms 95.0% CI: (47.463785 ms, 47.463785 ms)
Execution time upper ci : 53.088105 ms 95.0% CI: (53.034291 ms, 53.088105 ms)

Found 12 outliers in 60 samples (20.0000 %)
low-severe 2 (3.3333 %)
low-mild 10 (16.6667 %)
Variance from outliers : 23.8733 % Variance is moderately inflated by outliers
nil
--8<---------------cut here---------------end--------------->8---

But my patch to CLJ-1010 which implements `comp*` bases the 4-or-more
arity version of the existing `comp` on `comp*`, i.e., it's literally

;; comp for arbitrary arity, i.e., [f1 f2 f3 & fs]
(apply comp* (reverse (list* f1 f2 f3 fs)))

Now how can it be that compositions created with `(apply comp ...)`
*evaluate* ~2.5 times faster than compositions created with `(apply
comp* ...)`?

Bye,
Tassilo, totally stunned...

[Yoshinori Kohyama]

Hi all,

To fold operations from right to left,

accumulate what calculations should be done in a list with cons in order (Thanks Tassilo) and

compose accumulated functions manually (Thanks Meikel, almost equivalent to using

Tassilo's comp* I think) without reverse.

First, the initial topic fold-right and its family reduce-right: https://gist.github.com/2893987

Next, my abstraction for folding-from-right-loops r-reduce: https://gist.github.com/2896939

Last, related function unfold: https://gist.github.com/2901487

Have changed not to need large stack.

Have become very faster.

Still need little bit of heap.

Regards,

Yoshinori Kohyama

[Yoshinori Kohyama]

Hi all,

I'm sorry such my frequent posts.

How stupid have I been!
The function 'f' doesn't vary in the chain of operations.
We only have to keep 1st operands of 'f' in reversed order in a list.

What I have to do is applying 'f' in the reversing order when stopping condition comes,

instead of reversing operands at the beggining of calculations and apply 'f's to them.

I've updated,

1) The initial topic fold-right and its family reduce-right: https://gist.github.com/2893987

2) An abstraction for folding-from-right-loops r-reduce: https://gist.github.com/2896939

3) Related function unfold: https://gist.github.com/2901487

They no longer need a large heap.

Regards,

Yoshinori Kohyama

[Tassilo Horn]

Tassilo Horn <tas...@member.fsf.org> writes:

> r-reduce> (let [f1 (apply comp* (take 1000000 (repeat inc)))
> f2 (apply comp (take 1000000 (repeat inc)))]
> (bench (f1 0) :verbose)
> (println "---------------------------------------")
> (bench (f2 0) :verbose))

Oh, in this benchmark probably lazyness bites back. In the `comp` case
the `reverse` call will create a realized seq whereas in the `comp*`
case the realization will take place not before the composition fn f1 is
applied. However, forcing the realization beforehand doesn't make it
much better.

--8<---------------cut here---------------start------------->8---
user> (let [coll (doall (take 1000000 (repeat inc)))
f1 (apply comp* coll)
f2 (apply comp coll)]

(bench (f1 0) :verbose)
(println "---------------------------------------")
(bench (f2 0) :verbose))

amd64 Linux 3.4.2-gentoo 2 cpu(s)

OpenJDK 64-Bit Server VM 22.0-b10
Runtime arguments: -agentlib:jdwp=transport=dt_socket,server=y,suspend=n -XX:+TieredCompilation -Xmx1G -Dclojure.compile.path=/home/horn/Repos/clj/testi/target/classes -Dtesti.version=0.1.0-SNAPSHOT -Dclojure.debug=false

Evaluation count : 600
Execution time mean : 112.324465 ms 95.0% CI: (112.247218 ms, 112.380682 ms)
Execution time std-deviation : 6.513809 ms 95.0% CI: (6.477450 ms, 6.553029 ms)
Execution time lower ci : 105.609401 ms 95.0% CI: (105.609401 ms, 105.622918 ms)
Execution time upper ci : 122.353763 ms 95.0% CI: (122.353763 ms, 122.405315 ms)
---------------------------------------
amd64 Linux 3.4.2-gentoo 2 cpu(s)

OpenJDK 64-Bit Server VM 22.0-b10
Runtime arguments: -agentlib:jdwp=transport=dt_socket,server=y,suspend=n -XX:+TieredCompilation -Xmx1G -Dclojure.compile.path=/home/horn/Repos/clj/testi/target/classes -Dtesti.version=0.1.0-SNAPSHOT -Dclojure.debug=false

Evaluation count : 1440
Execution time mean : 43.519663 ms 95.0% CI: (43.516732 ms, 43.524062 ms)
Execution time std-deviation : 492.299089 us 95.0% CI: (490.829889 us, 494.198137 us)
Execution time lower ci : 42.781398 ms 95.0% CI: (42.781398 ms, 42.781398 ms)
Execution time upper ci : 44.157311 ms 95.0% CI: (44.157311 ms, 44.158513 ms)

nil
--8<---------------cut here---------------end--------------->8---

Bye,
Tassilo