doseq, dotimes & loop/recur
verec
one" than anything else ...
If I got this right, there are two forms of iterations: internal and
external.
`map' is an "internal iterator", `doseq' is an "external iterator".
An "internal iterator" does the iteration "by itself" and applies some
provided fn to the collection, possibly resulting into some new
collection.
An "external iterator" provides you with the "closest access" to the
collection, allowing you to decide for yourself what you want to do
"inline" on an element by element basis, possibly deciding on a course
of actions depending on the values seen so far, which would be more
difficult to do with an "internal iterator" such as `map', because the
fn would need to be passed those "previous values of interest" as
arguments each time.
Now, if I summarize the set of clojure provided iterations forms I get
the internal ones such as `map' or 'reduce', the external ones such as
`doseq' or `dotimes', plus, via loop/recur the means by which to
implement my own "internal iterators" in the `map'/`reduce' vein.
The question then is: is this all there is to iteration? And if any
external iterator beyond `doseq' and `dotimes` is missing, what would
they be?
Graham Fawcett
On Sat, Nov 8, 2008 at 11:20 AM, verec
<jeanfrancoi...@googlemail.com> wrote:
>
> More of an inquiry into the "fp mindset as opposed to the procedural
> one" than anything else ...
>
> If I got this right, there are two forms of iterations: internal and
> external.
> `map' is an "internal iterator", `doseq' is an "external iterator".
I see where you're going there, but I wouldn't put too fine a point on
the distinction between internal and external. Really they're just
different syntax for expressing the same thing.
The intention behind the "do" forms isn't about "externality" but
evaluation strategy. As you know, sequences in Clojure are lazy. The
"do" forms force evaluation of a sequence's elements to be done
immediately, rather than lazily as needed. A common reason you'd want
to do that is because your do-expression has side-effects (I/O) and
you want the effects to happen "now" rather than spread out across a
set of future time points (or possibly not at all, if the sequence is
never evaluated to its end).
Ignoring laziness for a moment, all of these iteration constructs can
be expressed in terms of loop/recur, since any iteration form can be
expressed in terms of recursion. They can also be built up from
reduce, which is a form called a "fold" in other functional languages,
and is the "internal" equivalent of loop/recur, to borrow your
terminology. Using (doall) in conjunction with either of these would
let you express the non-lazy "do" forms.
The benefit of map, reduce, filter isn't that they are inherently
different from loop/recur, but that they concisely express a notion of
transforming one sequence into another using a transformation
function. If the expression you're trying to build up naturally fits
that pattern, then map, reduce, filter are a good fit. (Note, reduce
is more general than map/filter, in that it can transform a sequence
into something other than another sequence.)
Since reduce is the "internal" equivalent to loop/recur, you might
consider writing some expressions in both styles until the equivalence
makes sense. For example, here are two simple functions described
using loop and reduce.
(defn add-up [numbers]
(loop [nums numbers accumulator 0]
(if (nil? nums)
accumulator
(recur (rest nums) (+ (first nums) accumulator)))))
(defn add-up-reducing [numbers]
(reduce + 0 numbers))
(defn sum-and-product [numbers]
(loop [nums numbers sum 0 product 1]
(if (nil? nums)
[sum product]
(recur (rest nums)
(+ (first nums) sum)
(* (first nums) product)))))
(defn sum-and-product-reducing [numbers]
(reduce (fn [[sum prod] frst] [(+ sum frst) (* prod frst)])
[0 1]
numbers))
In short, if you can figure out how to write your expression using
reduce rather than a loop, it can lead to more compact code. But more
complex reduce expressions can be hard to follow, and loop will make
for better readability.
Hope this helps,
Graham
verec
Thank you for the post.
Questions of laziness apart, I know that recursion has been proven to
be equivalent to iterations (expect to weed out interview candidates,
as per Steve Yege's remarks :-)
But then why would we want any of `doseq', `dotimes' or `doall', and
if we do, is that set complete, and with respect to what design
principle?
For example, CL provides `do-symbols', `do-all-symbols' or `with-
package-iterator' as "external" iterators.
Clojure decided that anything that could be expressed as a `seq' could
be iterated over using `doseq', so I can express the equivalent of
CL's (do-symbols ...) using clojure (doseq [n all-ns] ....)
To rephrase the question differently, what could exist that is not a
clojure `seq' that we would want to iterate over?
Clojure already answers this (partially?) by providing (dotimes ...)
(as CL does) to iterate over a zero based consecutive and finite
sequence of numbers. Though the same (dotimes ...) could be _used_ to
iterate over any finite range)
What are the things that one could iterate over, for which clojure
does not, currently, provide special cases à la `doseq' or 'dotimes' ?
I can't think of any, but that's just my poor lack of imagination :-)
Many thanks.
Graham Fawcett
On Sat, Nov 8, 2008 at 2:39 PM, verec
<jeanfrancoi...@googlemail.com> wrote:
> But then why would we want any of `doseq', `dotimes' or `doall', and
> if we do, is that set complete, and with respect to what design
> principle?
Well, given loop/recur as a fundamental iteration form, and doall as a
mechanism for forcing evaluation of the spine of a sequence, I'd say
that loop/recur + doall could be used to build all the other forms.
(I realize I mis-spoke in my earlier message by saying that loop/recur
and reduce could be equated. That's not true, since loop/recur allows
for short-circuiting, and does not require a sequence as one of its
"arguments". So loop/recur is more general than reduce. Sorry about
that.)
I think we want a variety of forms for the same reason Common Lispers
want DOTIMES, LOOP, etc. -- pragmatism.
> For example, CL provides `do-symbols', `do-all-symbols' or `with-
> package-iterator' as "external" iterators.
>
> Clojure decided that anything that could be expressed as a `seq' could
> be iterated over using `doseq', so I can express the equivalent of
> CL's (do-symbols ...) using clojure (doseq [n all-ns] ....)
Yes, exactly -- abstract sequences are a super idea, and make a lot of
special-case procedures unnecessary.
> To rephrase the question differently, what could exist that is not a
> clojure `seq' that we would want to iterate over?
>
> Clojure already answers this (partially?) by providing (dotimes ...)
> (as CL does) to iterate over a zero based consecutive and finite
> sequence of numbers. Though the same (dotimes ...) could be _used_ to
> iterate over any finite range)
I'd argue that dotimes iterates, but doesn't iterate *over* anything
-- there's no Clojure sequence involved.
> What are the things that one could iterate over, for which clojure
> does not, currently, provide special cases à la `doseq' or 'dotimes' ?
Not special cases -- dotimes doesn't traverse a sequence, and doseq
can be thought of as a "map" that is evaluated immediately, for
side-effects, and which discards the result of the map. (Like for-each
in Scheme, compared with map in Scheme -- the former is for
side-effects, the latter to produce a transformed list.)
Clojure's concept of the 'seq' as the object of traversal, rather than
a literal type (list, vector, etc.) is its fundamental genius, IMHO.
Best,
Graham
verec
> > clojure `seq' that we would want to iterate over?
>
> > Clojure already answers this (partially?) by providing (dotimes ...)
> > (as CL does) to iterate over a zero based consecutive and finite
> > sequence of numbers. Though the same (dotimes ...) could be _used_ to
> > iterate over any finite range)
>
> I'd argue that dotimes iterates, but doesn't iterate *over* anything
> -- there's no Clojure sequence involved.
Everything that can be interpreted as a `seq', clojure's `doseq' takes
care of it.
What I am after are the "special cases" for things one could somehow
enumerate but are not a `seq'.
A number range is one such thing, and clojure provides 'dotimes' to
handle this case.
What could be the XYZ that are neither a `seq' nor a number range, for
which we would want a `doXYZ' ?
In other words, is the set `doseq', `dotimes' and `doall' complete,
and if not, what is missing?
Many thanks
Graham Fawcett
<jeanfrancoi...@googlemail.com> wrote:
> Everything that can be interpreted as a `seq', clojure's `doseq' takes
> care of it.
>
> What I am after are the "special cases" for things one could somehow
> enumerate but are not a `seq'.
>
> A number range is one such thing, and clojure provides 'dotimes' to
> handle this case.
>
> What could be the XYZ that are neither a `seq' nor a number range, for
> which we would want a `doXYZ' ?
>
> In other words, is the set `doseq', `dotimes' and `doall' complete,
> and if not, what is missing?
Of course, dotimes could be implemented in terms of doseq, e.g.
(dotimes i n ...)
(doseq i (take n (iterate inc 0)) ...)
so really there aren't any special cases in Clojure. I can't think of
anything that is sequence-like but couldn't be represented as a seq,
so I think the bases are covered. :-)
Best,
Graham