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
What's wrong with just using reverse?
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
And then there's (take-while #(not (stop-pred %)) (iterate f start)).
(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
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.
>> (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
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.
> 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. :-)
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
However, you have to reverse the list
of functions, which destroys the theoretical benefit.
But still my reverse-the-collection-and-then-reduce-it approach is still
much faster, although it has to iterate the collection twice.
I'm not exactly sure why, but I'd guess the allocation overhead for 2
million partial functions is rather expensive.
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.