如何在Clojure中递归压平任意嵌套的向量和映射？

Question

我试图使用递归来遍历Clojure中任意嵌套的向量和映射树，并返回一个只包括关键字（包括顶部）的向量。以下示例数据应该返回: [:top :top :top :top :top :top :top :top :bottom :bottom :bottom :bottom :bottom :bottom :bottom :bottom :bottom :bottom :bottom :bottom]，但没有特定的顺序。

请问是否有人可以帮我正确地实现这个功能? 以下是我目前的代码。

(def sample [{:top {:top {:top [:bottom {:top {:top [:bottom :bottom :bottom]}} :bottom :bottom :bottom]}}}, 
                        {:top {:top [:bottom :bottom :bottom]}}, 
                        {:top [:bottom :bottom]}])

(defn make-flat [graph]
  (loop [graph graph]
    (if (every? keyword? graph) graph
      (recur (into graph (flatten (seq (first (filter #(not (keyword? %)) graph)))))))))

(make-flat sample)

- kurofune

---

你为什么要拥有这样任意嵌套的序列呢？通常而言，最好的做法是直接生成正确形状的数据，而不是对其进行奇怪的修复。 - amalloy

这是一个编码挑战 :) - kurofune

如果这是一个编程挑战，我给你答案，那么我是否会得到解决编程挑战的信用？ - Mars

我已经解决了这个挑战，但我个人正在寻找一个更一般的解决方案来解决我上面概述的问题。如果你的答案可行，我会给你以认可。 - kurofune

Answer 1

如果你的数据没有嵌套得太深（比如数百层），你可以简单地使用递归：

(defn my-flatten [x]
  (if (coll? x)
    (mapcat my-flatten x)
    [x]))

在REPL中：

user> (my-flatten sample)
(:top :top :top :bottom :top :top :bottom :bottom :bottom 
 :bottom :bottom :bottom :top :top :bottom :bottom 
 :bottom :top :bottom :bottom)

否则我会同意tree-seq在这里是非常好的变体：

user> (filter keyword? (tree-seq coll? seq sample))
(:top :top :top :bottom :top :top :bottom :bottom 
 :bottom :bottom :bottom :bottom :top :top :bottom 
 :bottom :bottom :top :bottom :bottom)

- leetwinski

---

我也非常喜欢tre-seq解决方案，它可以处理大型、深度嵌套的输入，但递归解决方案才是我所需要的。谢谢！ - kurofune

Answer 2

看一下flatten的源代码：

(defn flatten
  "Takes any nested combination of sequential things (lists, vectors,
  etc.) and returns their contents as a single, flat sequence.
  (flatten nil) returns an empty sequence."
  {:added "1.2"
   :static true}
  [x]
  (filter (complement sequential?)
          (rest (tree-seq sequential? seq x))))

现在你可以将 sequential? 更改为 coll? 以包含映射。此外，如果您只想获取关键字，还可以添加 every-pred :

(defn flatten' [x]
  (filter (every-pred (complement coll?) keyword?)
          (rest (tree-seq coll? seq x))))

- ClojureMostly

Answer 3

我怀疑在Clojure的基本库clojure.clj中已经有一个可以实现这个功能的函数。

确实如此，有这个函数。

https://clojuredocs.org/clojure.core/flatten

然而，如果您这样做是为了了解它实际发生的方式，您可以查看Github上函数（flatten stuff）的源代码，其中stuff是您想要展平的内容。

请注意，对于地图，您必须通过调用seq来使用一个解决方法。

 (seq the-map-you-wanna-flatten-eventually)

用户=> (flatten {:name "Hubert" :age 23})

; Workaround for maps

user=> (flatten (seq {:name "Hubert" :age 23}))
(:name "Hubert" :age 23) 

- sova

---

flatten 只能用于序列，而映射不是序列。你可以使用 (flatten (seq my-map)) 作为解决方法，但它只能展开一层... - kurofune

@kurofune 这并不完全正确；flatten适用于任何sequential?的东西，包括可能不一定是序列的向量等内容。 - Sam Estep

@SamEstep 感谢你的小贴士。 - kurofune

Answer 4

你可能想要查看这里的 postwalk：http://clojuredocs.org/clojure.walk/postwalk

还可以参考 postwalk-demo：http://clojuredocs.org/clojure.walk/postwalk-demo

这是一个可用的程序：

(ns clj.core
  (:use tupelo.core)
  (:require [clojure.walk :refer [postwalk]] )
)

(def result (atom []))

(defn go [data]
  (postwalk (fn [it]
              (spyx it)
              (when (keyword? it)
                (swap! result append it))
              it)
            data))

(newline)
(spyx (go {:a 1 :b {:c 3 :d 4}}))
(spyx @result)

带有结果：

it => :a
it => 1
it => [:a 1]
it => :b
it => :c
it => 3
it => [:c 3]
it => :d
it => 4
it => [:d 4]
it => {:c 3, :d 4}
it => [:b {:c 3, :d 4}]
it => {:a 1, :b {:c 3, :d 4}}
(go {:a 1, :b {:c 3, :d 4}}) => {:a 1, :b {:c 3, :d 4}}
(clojure.core/deref result) => [:a :b :c :d]

使用您的数据，最终输出为：

(clojure.core/deref result) => [:top :top :top :bottom :top :top :bottom :bottom :bottom :bottom :bottom :bottom :top :top :bottom :bottom :bottom :top :bottom :bottom]

这里是一个简单的递归解决方案：

(def mm {:a 1 :b {:c 3 :d 4}})

(defn accum 
  [it]
  (spy :msg "accum" it)
  (when (keyword? it)
    (swap! result append it)))

(defn walk [data]
  (spy :msg "walk" data)
  (cond
    (coll?  data)  (mapv walk data)
    :else          (accum data)))

(newline)
(reset! result [])
(walk mm)
(spyx @result)

输出结果为：

walk => {:a 1, :b {:c 3, :d 4}}
walk => [:a 1]
walk => :a
accum => :a
walk => 1
accum => 1
walk => [:b {:c 3, :d 4}]
walk => :b
accum => :b
walk => {:c 3, :d 4}
walk => [:c 3]
walk => :c
accum => :c
walk => 3
accum => 3
walk => [:d 4]
walk => :d
accum => :d
walk => 4
accum => 4
(clojure.core/deref result) => [:a :b :c :d]

- Alan Thompson

---

这是一个很好的工作解决方案，但我实际上正在尝试使用递归来解决问题。我相信有一种非常简单的方法来做到这一点。 - kurofune