关于匿名“自参照”的建议/讨论数据结构 [英] Advice/discussion on anonymous "self referential" data structures

问题描述

对任何错误的术语抱歉，我对计算机科学很新，我几乎只知道Clojure（但我想我会说我知道这很好）。

所以，我没有做过大量的研究，但我有时发现，当编写Clojure代码能够引用一些中间版本我在这个数据结构中的任何数据结构（很像在 let 中）。快速示例：

  => （self-ish {：a 10 
：b（inc（this：a））
：c（count（vals this））}）
 => {：a 10，：b 11，：c 3} 
 => （self-ish [ab（reduce str this）]）
 => [abab] 
 //适用于任何嵌套位
 => （self-ish [1 2 3 [4 5（first this）] 6 [7 [8（cons（second this）（nth this 3））]]]）
 => [1 2 3 [4 5 1] 6 [7 [8（2 4 5 1）]]] 
  

这个想法是，结构以递增方式构建，并且在任何阶段都能够引用当前中间结构 this 。下面是我当前实现的代码：

  //随机简单但有用的定义
 （def map-entry？[obj] 
（instance？clojure.lang.AMapEntry obj））
（def Map clojure.lang.IPersistentMap）
（def Vector clojure.lang.IPersistentVector） 
（def List clojure.lang.IPersistentList）
（def Set clojure.lang.IPersistentSet）
 
（defn append 
 [x coll] 
 if-not coll x 
（condp instance？coll 
 Map（if（empty？x）coll 
（assoc coll（first x）（second x）））
 Vector conj（x）
设置（conj coll x）
列表（应用列表（concat coll [x]））
（concat coll [x]）））
 
（defn build-this 
 [acc-stack acc] 
（ - >>（cons acc acc-stack）
 drop-while（every-pred empty？identity））
（reduce append）））
 
（defn self-indulge 
 [acc-stack acc form] 
 ; //取消注释以下内容以查看它打印中间处理阶段
 #_（printlnthis：（build-this acc-stack acc）\\\
 at：form）
 （append（cond 
（coll？形式）
（if（map-entry？form）[] 
（空格式））
形式）
 b（=（quote this）form）（build-this acc-stack acc）
：else form）
 acc））
 
（defmacro self-ish 
 [form] 
（self-indulge（）nil form））
  

$ c> append 函数将一个项附加到一个集合上，并返回相同类型的集合。 自我放置函数有一个标准的类似reduce的累加器，它只是构建了形式的元素。它还有一个累加器堆栈，每次自我放置自身递归时会变长。这是为了跟踪其他较高的累加器，因此这个将是整个结构，而不只是一个本地片。 self-ish 宏只是很好地包装自我放置（它调用自己使用 partial

编辑：示例用例
对我来说，这个宏是为了提高代码可读性，而不是真正扩展功能。我发现这有用的情况下，我有手写结构与部分冗余数据 - 或者依赖是一个更好的词。它可以更容易地读取代码，并看到数据结构的不同部分保存，如果我修改结构的一部分中的数据值，并希望该更改反映在其他部分，它也可以是有用的。例如：

  => （self-ish {：喜欢的书（列表犯罪和处罚Dalloway夫人）
：喜欢的东西（列表*冰淇淋吊床 b $ b => {：favorite-things（Ice CreamHammocksCrime and PunishmentDalloway夫人），
： ）} 
  

它也可能在有人可能真的想包括烘焙到数据，而不是使用一些函数派生的，这些情况可能是很少见的，我认为这是一个坏主意，不必要的纠结数据，当你可以有很好的干净的函数操作它。

我的主要问题：

1. 这实际上是有用的， ？我想象我不是一个人想要/使用这种类型的宏。这里的其他人的经验是什么？你使用这样的东西吗？你发现更好的解决方法吗？有什么像这样的事情不是在任何Clojure库？


2. 有没有更好的命名约定，我可以使用 - 而不是 self-ish 和 this ？例如，可能这是太负载OOP含义，我不知道，我基本上只熟悉Clojure。


3. 我对计算机科学很新鲜，有与这种类型的东西相关的可访问和信息资源 - 我想我会称之为匿名自我参照（也许反射是更好的词？）数据结构？


4. 有没有更好的方法来编写 self-ish 宏？上面，我已经包括我当前的版本，但我不能动摇的感觉，可能有一个更简单的方法。



5. 我有各种问题，什么可能是最聪明的实施细节。

   
   
   
   
   
   • 遍历 ：应该是广度优先还是深度优先？如果深度优先，预订，后序，或者不是？现在，我相信它是深度优先的预订，这对我有意义，但也许它有一些我没有注意到的缺点。
   
   

   • 订购问题：（在这里查看我的相关先前问题 ）在 {} （即用手写的映射）中，不可能正确地维护顺序（高于8个映射条目），而不使用 array-map 或 sorted-map - 换句话说，在8个地图条目之上， {} 。也许不是手写的命令，宏可以做一些奇妙的魔法来处理项目在一些理想的顺序？或者也许最好将（array-map ...）中的所有映射包裹起来，而不是令人眼花缭乱的 {} ？

       //显示9个条目的地图失败
      => （self：ish {：a 1 
     ：b（inc（this：a））
     ：c（inc（this：b））
     ：d 
     ：e（inc（this：d））
     ：f（inc（this：e））
     ：g （this：g））
     ：i（inc（this：h））}）
      => NullPointerException clojure.lang.Numbers.ops（Numbers.java:942）
      // 8工作正常
      => （self：ish {：a 1 
     ：b（inc（this：a））
     ：c（inc（this：b））
     ：d 
     ：e（inc（this：d））
     ：f（inc（this：e））
     ：g （this：g））}）
      => {：h 8，：g 7，：f 6，：e 5，：d 4，：c 3，：b 2，：a 1} 
       

   
   
   Serial ：正如我写的那样，宏通过连续处理它的元素避免了无限递归，类似于 let ，但这会产生潜在的奇怪行为。例如，在我上面的快速示例中，（reduce str this）返回ab，因为此在该步骤中为 [ab] 。也许有时会创建某种无限延迟序列有用吗？
   
   
   • 映射条目：现在，地图条目被视为向量，但由于这个可以在任何中间步骤被调用，完全有可能从一个键还有一个 nil 已分配值。这就是为什么在我的第一个快速示例中，：c 最终映射到3 - 因为中间有一个 nil 对应于：c ，并且被计数。
   ：使用自我放纵在宏的上下文之外，但是这可能是有用的吗？
   



感谢阅读，任何帮助是赞赏：）

解决方案

这种方法感觉 m不太清楚为什么。也许我不喜欢地图构造的依赖顺序的想法....

有人说，这是一个很容易写的宏，你有效地想要的东西展开为：

 （let [this {} 
 this（assoc this：a 1）
 （assoc this：b（+（this：a）3））] 
 this）
  

因此，一个合适的宏将是类似于（对于地图情况）：

 （defmacro self-ish [bindings] 
`（let [〜'this {} 
〜@（mapcat 
〜 ））] 
〜'this））
 
（self-ish [：a 1 
：b（+（this：a）3）]）
 = > {：b 4，：a 1} 
  

请注意，我将绑定表单作为向量一个地图绑定形式是无序的。

仍然不知道我多么喜欢这个成语。我喜欢的方式通常是用let形式定义一个结构，并给临时计算提供有意义的名字，例如：

  -foo（something）
 significance-bar（something-else）] 
 {：foo significance-foo 
：bar significance-bar 
：baz（some-calculation meaning-foo significance-bar）}）
  

Apologies for any mistaken terminology--I'm quite new to computer science, and I pretty much only know Clojure (but I guess I'd say I know it pretty well).

So, I haven't done a ton of research on this, but I've sometimes found it useful when writing Clojure code to be able to refer to some "intermediate version of whatever data structure I'm in" from within that data structure (a lot like in a let). Quick examples:

=> (self-ish {:a 10
              :b (inc (this :a))
              :c (count (vals this))})
=> {:a 10, :b 11, :c 3}
=> (self-ish ["a" "b" (reduce str this)])
=> ["a" "b" "ab"]
//Works in any nested bits too
=> (self-ish [1 2 3 [4 5 (first this)] 6 [7 [8 (cons (second this) (nth this 3))]]])
=> [1 2 3 [4 5 1] 6 [7 [8 (2 4 5 1)]]]

The idea is that the structure builds itself up incrementally, and at any stage has the ability to refer to the current intermediate structure as this. Here's the code for my current implementation:

//Random straightforward but helpful definitions
(defn map-entry? [obj]
  (instance? clojure.lang.AMapEntry obj))
(def Map clojure.lang.IPersistentMap)
(def Vector clojure.lang.IPersistentVector)
(def List clojure.lang.IPersistentList)
(def Set clojure.lang.IPersistentSet)

(defn append
  [x coll]
  (if-not coll x
    (condp instance? coll
      Map (if (empty? x) coll
            (assoc coll (first x) (second x)))
      Vector (conj coll x)
      Set (conj coll x)
      List (apply list (concat coll [x]))
      (concat coll [x]))))

(defn build-this
  [acc-stack acc]
  (->> (cons acc acc-stack)
       (drop-while list?)
       (drop-while (every-pred empty? identity))
       (reduce append)))

(defn self-indulge
  [acc-stack acc form]
  ;//Un-comment the following to see it print intermediate stages of processing
  #_(println "this:" (build-this acc-stack acc) "\n  at:" form)
  (append (cond
            (coll? form) (reduce (partial self-indulge (cons acc acc-stack))
                                 (if (map-entry? form) []
                                   (empty form))
                                 form)
            (= (quote this) form) (build-this acc-stack acc)
            :else form)
          acc))

(defmacro self-ish
  [form]
  (self-indulge () nil form))

The append function appends an item onto a collection and returns the same type of collection. The self-indulge function has a standard reduce-like accumulator, which just builds up elements of form. It also has a accumulator stack, which gets longer every time self-indulge recurs upon itself. The point of this is to keep track of other "higher up" accumulators, so that this will be the entire structure, not just a local piece. The self-ish macro just nicely wraps up self-indulge (which calls itself using partial, so it can't wear the macro pants).

Edit: example use case To me, this macro is about trying to increase code readability, not truly extending functionality. Where I have found this useful is in cases where I have hand-written structures with partially redundant data--or maybe "dependent" is a better word. It can be easier to read the code and see what different parts of the data structure hold, and it can also be useful if I modify data values in one part of a structure and want that change to be reflected in other parts. For example:

=> (self-ish {:favorite-books (list "Crime and Punishment" "Mrs. Dalloway")
              :favorite-things (list* "Ice Cream" "Hammocks" (this :favorite-books)})
=> {:favorite-things ("Ice Cream" "Hammocks" "Crime and Punishment" "Mrs. Dalloway"),
    :favorite-books ("Crime and Punishment" "Mrs. Dalloway")}

It could also be useful in times where one might really like to include something baked into the data, as opposed to derived on the fly using some function. These cases are probably much rarer, and I think it would be a bad idea to tangle the data unnecessarily when you could just have nice clean functions manipulating it.

My main questions:

1. Is this actually useful, or would the ambiguity/complexity incurred be too much? I imagine I'm not alone in wanting/using this type of macro. What are others' experiences here? Do you use something like this? Have you found better workarounds? Are there reasons something like this isn't in any Clojure libraries? Or is there something that I haven't yet seen?
2. Are there better naming conventions I might use--as opposed to self-ish and this? For example, maybe this is too loaded with OOP meaning, I'm not sure, I am basically only familiar with Clojure.
3. I am pretty new to computer science, are there accessible and informative resources related to this type of thing--I guess I would call it anonymous self referential (maybe reflexive is a better word?) data structures? I haven't found anything both approachable and informative yet.
4. Is there a better way to write the self-ish macro? Above, I've included my current version of it, but I can't shake the feeling there may be a simpler way.

5. I have various questions about what might be the "wisest" implementation details.

   • Traversal: Should it be breadth first or depth first? If depth first, preorder, postorder, or inorder? Right now, I believe it's depth first preorder, which makes sense to me, but maybe it has some drawbacks I haven't noticed.

   • Order problems: (See here for a related previous question of mine) Within {} (i.e. maps written by hand) it's impossible to maintain order properly (above 8 map entries) without using array-map or sorted-map--in other words, above 8 map entries, {} usage is unsafe. Maybe instead of hand-written order, the macro could do some fancy magic to process items in some "ideal" order? Or perhaps it would be better to wrap all maps within (array-map ...) instead of the eye-pleasing {}?

     //Showing maps with 9 entries failing
     => (self-ish {:a 1
                   :b (inc (this :a))
                   :c (inc (this :b))
                   :d (inc (this :c))
                   :e (inc (this :d))
                   :f (inc (this :e))
                   :g (inc (this :f))
                   :h (inc (this :g))
                   :i (inc (this :h))})
     => NullPointerException   clojure.lang.Numbers.ops (Numbers.java:942)
     //8 works fine
     => (self-ish {:a 1
                   :b (inc (this :a))
                   :c (inc (this :b))
                   :d (inc (this :c))
                   :e (inc (this :d))
                   :f (inc (this :e))
                   :g (inc (this :f))
                   :h (inc (this :g))})
     => {:h 8, :g 7, :f 6, :e 5, :d 4, :c 3, :b 2, :a 1}
     

   • Serial: As I've written it, the macro avoids infinite recursion by dealing with its elements serially, similar to let, but that does produce potentially odd behavior. For example, in my above quick example, (reduce str this) returns "ab" because this is ["a" "b"] at that step. Maybe it would be useful sometimes to create some sort of infinite lazy sequence instead? If so, how might that be implemented?

   • Map entries: Right now, map entries are treated like vectors, but because of how this could be invoked at any intermediate step, it is totally possible to get a nil value from a key that has "not yet" been assigned a value. That is why in my first quick example, :c ended up mapped to 3--because intermediately there was a nil corresponding to :c, and that got counted as well. Do you think this warrants fixing?
   • Non-macro utility: It would be trivial to use just self-indulge outside of the macro context, but could this ever be useful?

Thanks for reading, any help is appreciated :)

解决方案

This approach "feels" a bit wrong to me, though I'm not quite sure why. Maybe I don't like the idea of map construction being dependent on order....

Having said that it's a pretty easy macro to write, you effectively want something that expands to:

(let [this {}
      this (assoc this :a 1)
      this (assoc this :b (+ (this :a) 3))]
  this)

Hence an appropriate macro would be something like (for the map case):

(defmacro self-ish [bindings]
  `(let [~'this {}
         ~@(mapcat 
           #(do `(~'this (assoc ~'this ~@%)) )    
           (partition 2 bindings) )]
    ~'this))

(self-ish [:a 1
           :b (+ (this :a) 3)])
=> {:b 4, :a 1}

Note that I'm made the binding form a vector as a map binding form is unordered.

Still not sure how much I like this idiom. My preferred way is usually to define a structure with a let form and give meaningful names to interim calculations e.g.:

(let [meaningful-foo (something)
      meaningful-bar (something-else)]
   {:foo meaningful-foo
    :bar meaningful-bar
    :baz (some-calculation meaningful-foo meaningful-bar)})

这篇关于关于匿名“自参照”的建议/讨论数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！