iteration idioms

[Brian Will]

A very large chunk of iteration is done for the sake of producing a
new collection based on an existing collection, hence functional
constructs like list comprehensions and map. However, I'm not sure
about how to functionally handle cases of iteration which seem to
require:

1) keeping around values from previous iterations
2) producing a collection of more values than exist in the original
(or sometimes fewer values, though such cases usually require just
straight forward filtering)

For (1), it seems you generally resort to some kind of recursion with
loop/recur. Say we wish to find the max value in a list (without using
'max'):

(def foo [35 -7 8 2 100 56])
(loop [max (first foo)
nums (rest foo)]
(if (nil? nums)
max
(recur
(if (> (first nums) max) (first nums) max)
(rest nums))))

For (2), say I want to insert 3 before every item less than or equal
to 5 in a seq:

(def bar [24 6 5 5 7 5 8 2])
(defn prepend3 [s val] (if (<= val 5) (concat s [3 val]) (concat s
[val])))
(loop [old (rest bar)
new (prepend3 [] (first bar))]
(if (nil? old)
new
(recur (rest old) (prepend3 new (first old)))))

user=> (24 6 3 5 3 5 7 3 5 3 2)

Again, hardly elegant. Maybe there's a cleaner way to use loop in
these cases, or maybe I'm just forgetting some function(s) to use.
Hopefully someone can demonstrate better idioms to handle these common
cases.

--Brian Will

[Mark Fredrickson]

>
> For (1), it seems you generally resort to some kind of recursion with
> loop/recur. Say we wish to find the max value in a list (without using
> 'max'):

I can do this with reduce:
user=> (defn my-max [lst] (reduce (fn [x a] (if (> x a) x a)) (first
lst) (rest lst)))
#'user/my-max
user=> (my-max '(2 4 12 3 4))
12

For more complex data that you need to bring along, use a list or map.

> For (2), say I want to insert 3 before every item less than or equal
> to 5 in a seq:

Again reduce to the rescue:

(reduce into (map (fn [i] (if (<= i 5) [3 i] [i])) [24 6 5 5 7 5 8 2]))

This is still O(n) - though it needs to iterate the vector twice. The
second version shows off Clojure's nice improvement to reduce (vis-a-
vis fold in Scheme): grabbing the first item from the head of the list/
vec/seq. The down side is I can't write multi-sequence reduce calls
like Scheme, but c'est la vie.

I could write O(n) versions with continuations in Scheme, but I think
loop/recur would be required in Clojure.

Cheers,
-Mark

[Brian Will]

Thanks, Mark.

I don't suppose (reduce into ...) is a common enough idiom that it
deserves its own function? Perhaps (into x) should do (reduce into x),
e.g. (into [[3 5] [6 7]]) => [3 5 6 7]. This makes sense to me, but
maybe it's too semantically different from (into x y). If not, though,
you could do the same with concat.

On Dec 12, 3:10 pm, Mark Fredrickson <mark.m.fredrick...@gmail.com>
wrote:

[Stephen Parker]

On 12 Dec 2008, at 23:10, Mark Fredrickson wrote:
>> For (2), say I want to insert 3 before every item less than or equal
>> to 5 in a seq:
>
> Again reduce to the rescue:
>
> (reduce into (map (fn [i] (if (<= i 5) [3 i] [i])) [24 6 5 5 7 5 8
> 2]))

Could use mapcat:

(def bar [24 6 5 5 7 5 8 2])

(defn insert-before-if [pred ins lst]
(mapcat #(if (pred %) [ins %] [%]) lst))

(insert-before-if #(<= 5 %) 3 bar)

=> (3 24 3 6 3 5 3 5 3 7 3 5 3 8 2)

stephen

[Dave Newton]

--- On Sat, 12/13/08, Stephen Parker wrote:
> On 12 Dec 2008, at 23:10, Mark Fredrickson wrote:

>> [...] insert 3 before every item less than or equal to 5 in a seq:

>
> (def bar [24 6 5 5 7 5 8 2])

> (insert-before-if #(<= 5 %) 3 bar)
>
> => (3 24 3 6 3 5 3 5 3 7 3 5 3 8 2)

Er...

Dave

[Stephen Parker]

Must have been asleep:

(def bar [24 6 5 5 7 5 8 2])

(defn insert-before-if [pred ins lst]

(mapcat #(if (pred %) [ins %] [%]) lst))

(insert-before-if #(<= % 5) 3 bar)

stephen