1

How could I convert this:

[a b c d e]

or this:

(e d c b a) ;(rseq [a b c d e])

to this:

[a[b[c[d[e]]]]]

I've been wracking my brain and I feel like there is a simple solution! :-\

Ultimately I want to do this:

[a b c d e]
[a b c x y]
[a b c d j k]

as this:

{a {b {c {d {e}
            {j {k}}
         {x {y}}}}

Which I think conj will help with

scape
  • 652
  • 12
  • 27

2 Answers2

4

(Update: added answer to the new question added in the edit below the answer to the original question.)

I've actually answered this very question in #clojure recently.

Here are two approaches: f is pretty much the spec directly transformed into code, which however creates a seq -- (next xs) -- which immediately gets poured into a new vector at each step; g is a much better version which only allocates objects which will actually occur in the output, plus a vector and the seq links to traverse it:

;; [1 2 3] -> [1 [2 [3]]]

;; naive, quadratic:
(defn f [xs]
  (if (next xs)
    [(first xs) (vec (f (next xs)))]
    (vec xs)))

;; only allocates output + 1 vector + a linear number of seq links,
;; linear overall:
(defn g [v]
  (reduce (fn [acc x]
            [x acc])
          [(peek v)]
          (rseq (pop v))))

NB. I'm overlooking the usual logarithmic factors arising from vector operations (so this is soft-O complexity).

As for producing a nested map, the above isn't particularly useful. Here's one approach:

(defn h
  ([v]
     (h nil v))
  ([m v]
     (assoc-in m v nil)))

(h [1 2 3 4])
;= {1 {2 {3 {4 nil}}}}

(def data
  '[[a b c d e]
    [a b c x y]
    [a b c d j k]])

(reduce h {} data)
;= {a {b {c {x {y nil}, d {j {k nil}, e nil}}}}}

I'm using nil as a "terminator", since {y} (as currently found in the answer text) is not a well-formed literal. true might be a more convenient choice if you plan to call these maps as functions to check for presence of keys.

Michał Marczyk
  • 83,634
  • 13
  • 201
  • 212
  • Funny enough I like the naive approach as I think it's possibly more idiomatic, to me at least. I had a funny feeling reduce was a solution, I'm going to have to look in to peek and pop more closely – scape Jul 11 '13 at 17:16
  • 1
    Going by the shape of the code alone, `f` and `g` are about equally idiomatic, with `g` having a possible edge in that it uses a well-understood library function (`reduce`) to drive the transformation, whereas `f` uses custom recursion. Taking semantics into account I'd only consider `g` idiomatic, since `f` uses completely the wrong data structures and transformations, contrary to the spirit of Clojure. As for complexity, `f` is quadratic, `g` is linear (overlooking the usual logarithmic factors resulting from vector lookups). – Michał Marczyk Jul 11 '13 at 17:22
  • what is "(fn [acc x] [x acc])" actually doing? – scape Jul 11 '13 at 17:30
  • It is taking two arguments, `acc` and `x`, and returning a vector with them in reverse order. (The first vector here is part of `fn` form syntax, the second vector is the only body expression.) – Michał Marczyk Jul 11 '13 at 17:31
  • If the input is a vector and `subvec`s are used instead, would it still be true that `f` is doomed to quadratic? I haven't invested the behavior of stacking `subvec`s. – A. Webb Jul 11 '13 at 17:35
  • True, it wouldn't be quadratic then, but `subvec` produces "view vectors" which prevent the original from becoming eligible for GC. The version of `subvec` from [core.rrb-vector](https://github.com/clojure/core.rrb-vector) doesn't have this problem, but the vectors it produces are somewhat slower; this is OK if the fast slicing is a big win, but here we can just use `g`, no reason to accept a slowdown. – Michał Marczyk Jul 11 '13 at 17:41
  • thanks for the map reduce example. I ended up using nil as well. trying to figure out how to put all this to use in my program now :) – scape Jul 11 '13 at 18:30
4

Simpler solution here (using destructuring and non-tail recursion):

http://ideone.com/qchXZC

(defn wrap
  ([[a & as]]
    (if-let [[b & cs] as]
      [a (wrap as)]
    [a])))
Display Name
  • 8,022
  • 3
  • 31
  • 66
  • Great answer, thank you! Is there a benefit of tail recursion and non-tail recursion in clojure? – scape Jul 11 '13 at 17:46
  • 2
    @scape Tail recursion doesn't push anything to stack and is faster. In Clojure, tail recursion can ONLY be done with `recur` special form. – Display Name Jul 11 '13 at 17:48
  • I tried a loop/recur but ultimately couldn't figure it out, thanks for the info! – scape Jul 11 '13 at 17:50