3

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?

1
  • 1
    seq? does not check for datastructures that can be iterated over, it checks for actual sequences. You need to use sequential? for that instead.
    – Didier A.
    Commented May 19, 2016 at 20:29

4 Answers 4

8

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)))
4
  • I think I need more experience with the standard library, I didn't even know about mapcat or sequential? until your answer. Commented Apr 24, 2013 at 18:46
  • 1
    Maybe I am just not understanding how mapcat works, but I don't see where coll is being reduced with each recursive call to flatten. Obviously it works, but the terseness of this function hides the complexity. I am trying to install the trace utility (I wish this came standard in Clojure implementation) to try and understand this voodoo.
    – dtg
    Commented May 29, 2013 at 1:49
  • 1
    The function passed to mapcat takes 1 value and return a seq of values, it is called for each value of the original coll and then all seqs are concatenated. So if coll is really a coll we flatten each element and concatenates teh results, if it's not a collection, we wrap it in a list, just to return a seq.
    – cgrand
    Commented May 29, 2013 at 12:21
  • i'd trouble understand this until i realize the line with mapcat is apply the function to each element in the coll var
    – fast tooth
    Commented Jul 4, 2017 at 2:32
2

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.

1

One possible approach:

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

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)))

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.