Mapping first element only: how to preserve vectors

[Bojan]

Hi!

I'm a beginner at clojure and enjoying the learning process. While writing my first nontrivial program, I noticed that I'm transforming only first elements in the list, so I factored this transformation out by writing next function:

(defn map-first [f coll]
  (map #(cons (f (first %)) (rest %)) coll))

And it almost works as expected:

Clojure> (map-first #(* 2 %) '((2) (3 3) (3 [2 4]) [4 10]))

((4) (6 3) (6 [2 4]) (8 10))

Note that the last element of the list is a vector, but ends up as a list. Sure, my program doesn't complain and I don't see a scenario where this might be a problem, but I wondered if there is some way to preserve vectors.
Second question that is less academic: how about performance? Would it be much better, where possible, to start mapping these values separately and only then build the whole structure or is there not much to be gained?

Thank you very much for attention!

[Cedric Greevey]

On Mon, Mar 19, 2012 at 9:40 AM, Bojan <bojand...@hotmail.com> wrote:
> Hi!
>
> I'm a beginner at clojure and enjoying the learning process. While writing
> my first nontrivial program, I noticed that I'm transforming only first
> elements in the list, so I factored this transformation out by writing next
> function:
>
> (defn map-first [f coll]
>   (map #(cons (f (first %)) (rest %)) coll))
>
> And it almost works as expected:
> Clojure> (map-first #(* 2 %) '((2) (3 3) (3 [2 4]) [4 10]))
> ((4) (6 3) (6 [2 4]) (8 10))
>
> Note that the last element of the list is a vector, but ends up as a list.
> Sure, my program doesn't complain and I don't see a scenario where this
> might be a problem, but I wondered if there is some way to preserve vectors.

Cons returns lists. (Well, seqs. For the most part the distinction is
unimportant.)

Doing what you ask is tricky. Changing cons to conj doesn't help (as
rest returns a seq too).

This:

(defn map-first [f coll]
(map #(into (empty %) (cons (f (first %)) (rest %))) coll))

reverses all the non-vectors.

I doubt it can be done without the ugliness of introducing a
conditional that checks for vector-ness or seq-ness.

[Rasmus Svensson]

On Mon, Mar 19, 2012 at 2:40 PM, Bojan <bojand...@hotmail.com> wrote:
> Hi!
>
> I'm a beginner at clojure and enjoying the learning process. While writing
> my first nontrivial program, I noticed that I'm transforming only first
> elements in the list, so I factored this transformation out by writing next
> function:
>
> (defn map-first [f coll]
>   (map #(cons (f (first %)) (rest %)) coll))

If coll is always a collection of vectors, then you can simply use
'assoc' since vectors support near-constant-time random access. Also,
the name "map-first" is a bit misleading in my opinion, since it does
not map f over the first element in coll, but over the first element
of each collection in coll.

Here's an example using assoc:

(defn map-first [f v]
(assoc v 0 (f (nth v 0))))

(defn map-firsts [f coll]
(map #(map-first f %) coll))

(map-firsts #(* 2 %) [[2] [3 3] [3 [2 4]] [4 10]])
;=> ([4] [6 3] [6 [2 4]] [8 10])

The complexity of map-firsts is O(log_32(n) * m). The log_32(n) part
comes from assoc, which creates a new updated vector with n elements.
(log_32 is practically close to constant. log_32 of four billion is
about 6 or 7) The m part comes from
mapping over the outer collection (of size m). The complexity can be
approximated to just O(m) if you approximate log_32 as constant time.
The 'assoc' here is very cheap.

// raek