CODEWITHSUNDEEP
clojurefunctional-programming
Brendon Roberto
Brendon Roberto

Reputation: 428

Clojure: What is wrong with my implementation of flatten?

I've been working through problems on 4Clojure today, and I ran into trouble on Problem 28, implementing flatten.

There are a couple of definite problems with my code.

(fn [coll]
  ((fn flt [coll res]
    (if (empty? coll)
        res
        (if (seq? (first coll))
            (flt (into (first coll) (rest coll)) res)
            (flt (rest coll) (cons (first coll) res))))) coll (empty coll)))

I could use some pointers on how to think about a couple of problems.

  1. How do I make sure I'm not changing the order of the resulting list? cons and conj both add elements wherever it is most efficient to add elements (at the beginning for lists, at the end for vectors, etc), so I don't see how I'm supposed to have any control over this when working with a generic sequence.

  2. How do I handle nested sequences of different types? For instance, an input of '(1 2 [3 4]) will will output ([3 4] 2 1), while an input of [1 2 '(3 4)] will output (4 3 2 1)

  3. Am I even approaching this from the 'right' angle? Should I use a recursive inner function with an accumulator to do this, or am I missing something obvious?

Upvotes: 3

Views: 914

Answers (4)

Didier A.
Didier A.

Reputation: 4816

Here's how to do it in a tail call optimised way, within a single iteration, and using the least amount of Clojure.core code as I could:

#(loop [s % o [] r % l 0]
   (cond
    (and (empty? s) (= 0 l))
    o
    (empty? s)
    (recur r
           o
           r
           (dec l))
    (sequential? (first s))
    (recur (first s)
           o
           (if (= 0 l)
             (rest s)
             r)
           (inc l))
    :else
    (recur (rest s)
           (conj o (first s))
           r
           l)))

Upvotes: 1

cgrand
cgrand

Reputation: 7949

You should try to use HOF (higher order functions) as much as possible: it communicates your intent more clearly and it spares you from introducing subtle low-level bugs.

(defn flatten [coll]
  (if (sequential? coll)
    (mapcat flatten coll)
    (list coll)))

Upvotes: 8

Ankur
Ankur

Reputation: 33657

One possible approach:

(defn flatten [[f & r]]
  (if (nil? f)
    '()
    (if (sequential? f)
      (concat (flatten f) (flatten r))
      (cons f (flatten r)))))

Upvotes: 1

mishadoff
mishadoff

Reputation: 10789

Regarding your questions about lists and vectors. As you might see in tests, output is list. Just make correct abstraction. Fortunately, clojure already has one, called sequence.

All you need is first, rest and some recursive solution.

Upvotes: 2

Related Questions