Clojure : Quel est le problème avec mon implémentation de flatten ?

Question

J'ai travaillé sur des problèmes sur 4Clojure aujourd'hui, et j'ai eu des problèmes sur Problème 28 en mettant en œuvre l'aplatissement.

Il y a quelques problèmes évidents avec mon 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)))

J'aurais besoin de quelques conseils sur la façon de penser à certains problèmes.

1. Comment m'assurer que je ne change pas l'ordre de la liste résultante ? cons y conj Les deux ajoutent des éléments là où c'est le plus efficace (au début pour les listes, à la fin pour les vecteurs, etc.), je ne vois donc pas comment je suis censé avoir un quelconque contrôle sur ce point lorsque je travaille avec une séquence générique.

2. Comment gérer les séquences imbriquées de différents types ? Par exemple, une entrée de '(1 2 [3 4]) produira ([3 4] 2 1) tandis qu'une entrée de [1 2 '(3 4)] produira (4 3 2 1)

3. Est-ce que j'aborde la question sous le "bon" angle ? Devrais-je utiliser une fonction interne récursive avec un accumulateur pour faire cela, ou est-ce que je rate quelque chose d'évident ?

Answer 1

Vous devriez essayer d'utiliser les HOF (fonctions d'ordre supérieur) autant que possible : cela communique votre intention plus clairement et vous évite d'introduire de subtils bogues de bas niveau.

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

Answer 2

En ce qui concerne vos questions sur les listes et les vecteurs. Comme vous pouvez le voir dans les tests, la sortie est une liste. Il suffit de faire une abstraction correcte. Heureusement, clojure en a déjà une, appelée séquence .

Tout ce dont vous avez besoin est premièrement , reste et une solution récursive.

Answer 3

Une approche possible :

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

Answer 4

Voici comment le faire de manière optimisée, en une seule itération et en utilisant le moins de code possible de Clojure.core :

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