Clojure中的链接列表实现

Question

背景

链接列表是一个众所周知的数据结构，所以我不会在它们上浪费太多的细节。只要说链接列表由“单元格”组成就足够了。每个单元格包含某种值和对下一个单元格的引用(最后一个单元格除外，后者包含一个空引用)。

我在Clojure中实现了一个链接列表，作为一个练习。

代码

(ns linked-list.core)

(defn create-linked-list [] {})

(defn add-to-linked-list [{:keys [value next-node] :as linked-list} new-value] 
      (let [new-node {:value new-value :next-node nil}]
      (if (= {} linked-list)
          new-node
          (let [new-tail (if (nil? next-node) new-node (add-to-linked-list next-node new-value))]
              (assoc-in linked-list [:next-node] new-tail)))))

(defn contains-linked-list? [{:keys [value next-node] :as linked-list} query-value]
      (if (empty? linked-list)
          false
          (or (= value query-value) (recur next-node query-value))))

(defn get-nth-linked-list [{:keys [value next-node] :as linked-list} n]
      (if (< n 1)
          value
          (recur next-node (dec n))))

(defn without-element-linked-list [linked-list n]
      (loop [{:keys [value next-node] :as act-node} linked-list counter 0 linked-list-accum (create-linked-list)]
          (let [new-linked-list (if (= counter n) linked-list-accum (add-to-linked-list linked-list-accum value))] 
               (if (nil? next-node) new-linked-list
                   (recur next-node (inc counter) new-linked-list)))))

The test

(ns linked-list.core-test
  (:require [clojure.test :refer :all]
            [linked-list.core :refer :all]))

(deftest create-linked-list-test
  (testing "create linked list"
    (is (= {} (create-linked-list)))))

(def empty-linked-list (create-linked-list))

(deftest add-to-linked-list-test
  (testing "add to linked list"
    (is (= {:value 10 :next-node nil} (add-to-linked-list empty-linked-list 10)))
    (is (= {:value 10 :next-node {:value 20 :next-node nil}} (add-to-linked-list (add-to-linked-list empty-linked-list 10) 20)))
    (is (= {:value 10 :next-node {:value 20 :next-node {:value 30 :next-node nil}}} (add-to-linked-list (add-to-linked-list (add-to-linked-list empty-linked-list 10) 20) 30)))))

(def one-element-linked-list (add-to-linked-list empty-linked-list 10))
(def two-element-linked-list (add-to-linked-list one-element-linked-list 20))

(deftest contains-linked-list-test
  (let [one-element-linked-list (add-to-linked-list empty-linked-list 10)
        two-element-linked-list (add-to-linked-list one-element-linked-list 20)]
    (testing "does a linked list contain a value"
      (is (false? (contains-linked-list? empty-linked-list 10)))
      (is (true?  (contains-linked-list? one-element-linked-list 10)))
      (is (true?  (contains-linked-list? two-element-linked-list 20)))
      (is (false?  (contains-linked-list? two-element-linked-list 30))))))

(deftest get-nth-linked-list-test
  (testing "get the nth element of linked list"
    (is (nil? (get-nth-linked-list empty-linked-list 0)))
    (is (= 10 (get-nth-linked-list one-element-linked-list 0)))
    (is (= 20 (get-nth-linked-list two-element-linked-list 1)))))

(def three-element-linked-list (add-to-linked-list two-element-linked-list 30))

(deftest without-element-linked-list-test
  (testing "remove the nth element of linked list"
    (is (= empty-linked-list (without-element-linked-list empty-linked-list 0)))
    (is (= empty-linked-list (without-element-linked-list one-element-linked-list 0)))
    (is (= {:value 20 :next-node nil} (without-element-linked-list two-element-linked-list 0)))
    (is (= one-element-linked-list (without-element-linked-list two-element-linked-list 1)))
    (is (= {:value 10 :next-node {:value 30 :next-node nil}} (without-element-linked-list three-element-linked-list 1)))))

审查目标

• 您对所选的数据结构(嵌套字典)有什么看法？是否有一种更有效地在Clojure中实现这一功能的方法？
• 是否有一种方法可以重写add-to-linked-list (或者可能是create-linked-list)，以便在添加新元素时不需要检查特定情况下的空列表？
• 是否有可能使without-element-linked-list变得不那么复杂？
• 有什么地方可以改进Clojure的良好实践吗？
• 您能想到单元测试没有涵盖的任何(边缘)情况吗？

GitHub

这个问题的来源是可用的这里。

Answer 1

您对所选的数据结构(嵌套字典)有什么看法？是否有一种更有效地在Clojure中实现这一功能的方法？

从概念上讲，它是可行的。不过，我不会在这里用普通地图。您知道列表中的每个节点都应该只包含键:value和:next-node。在这种情况下，我会用一张唱片来代替：

(defrecord Node [value, next-node])

(defn new-node [value]
  (->Node value nil))

这带来了轻微的性能好处，只是一般更有意义。如果您需要在Java中创建一个对象，并且知道它只需要两个特定的字段，那么您是将该对象表示为Map，还是表示为class？我可以说是一堂课。如果不需要具有可变字段数的对象，则不要将其表示为具有可变字段数的对象。是的，记录基本上只是映射，但我认为它们在这里更合适，因为它们应该包含哪些键是明确的。

这就提出了什么是空列表的问题。nil在这里工作，并且应该可以很好地处理递归(稍后会有更多的介绍)。

是否有一种方法可以重写添加到链接列表(或者可能是创建链接列表)，以便在添加新元素时不需要检查特定情况下的空列表？

你总是需要在某种程度上处理基本情况检查，所以我看不出有什么办法能把它完全去掉。你可以用multimethods来“模式匹配”，就像你在哈斯克尔那样，但这会增加大量的内容，而不是很清晰。但是，可以通过其他方法对整个功能进行显著调整：

(defn add-to-linked-list2 [node new-value]
  ; An empty list is now nil, which is falsey
  (if node
    ; Using update frees us from needing to destructure the node
    (update node :next-node #(add-to-linked-list2 % new-value))
    ; This also be written as (update node :next-node add-to-linked-list2 new-value)
    ;  thanks to update's overloads, which is even nicer

    (new-node new-value)))

主要变化如下：

• 因为空列表现在是nil，所以不必担心空列表是{}，而是空:next-node是nil。这大大简化了递归行。
• 与其检查列表是否等于空映射，我们还可以直接检查它的真实性。
• 我在这里使用我的new-node。我知道一个新节点将有一个nil的下一个节点，所以我最好从这段代码中删除这个事实，并让一个单独的函数来处理这个事实。

当然，这两种实现的主要问题是它们不能使用recur编写，这意味着它们很容易受到堆栈溢出的影响。我试着用loop来编写一个解决方案，但是它变得非常混乱，而且实际上，用例还是没有意义的。只是为了附加一个元素而迭代整个列表是不合理的。如果您要使用链接列表，只需在前面加上，这就完全消除了添加迭代的需要。看看Haskell，以及它的标准链接列表与递归的匹配程度。每个操作都是在头部完成的，这就简化了(并加快了)添加。

有没有可能让没有元素链接的列表不那么复杂？

首先，您的loop累加器是以一种非常混乱的方式编写的。至少用逗号分隔每个绑定，或者理想情况下，将每个绑定放在自己的行上：

(loop [{:keys [value next-node] :as act-node} linked-list
       counter 0
       linked-list-accum (create-linked-list)]

与我前面关于使用未优化递归的说法相反，我能找到的最好的方法是未优化的：

(defn without-element-linked-list2 [{:keys [next-node] :as node} n]
  (cond
    ; We hit the end of the list without finding it. Throw an error?
    ;  Apparently n was out of bounds.
    (nil? node) nil

    ; We found the element to delete. Just "skip" over it.
    (zero? n) next-node

    ; Very similar to the add method. We're part way through the list, so keep iterating.
    :else (update node :next-node without-element-linked-list2 (dec n))))

为了避免第二个计数器，我决定在迭代时减少n。

我知道你可能纯粹是作为一个练习来做这件事，但是得到一个优化的解决方案是非常困难的，这应该是一个错误的迹象。在我写Clojure的这两年里，我从来没有写过我自己的基本结构。在大多数其他语言中，这是一个非常常见的练习。然而，在Clojure中，使用的结构的底层实现最好藏在某个地方，只使用语言的基本结构就更常见了。如果需要链接列表行为，请使用普通列表。如果需要数组行为，请使用向量。有时需要更多的自定义结构，但倾向于首先使用本地结构，因为它们几乎总是足够的，并且已经有了广泛的API。

有什么地方可以改进Clojure的良好实践吗？

在contains-linked-list?中，您很好地利用了or。尽管如此，它仍然可以改进：

(defn contains-linked-list?2 [{:keys [value next-node] :as node} query-value]
  (when node
    (or (= value query-value) (recur next-node query-value))))

when很棒。它很好地整理了代码。如果您发现自己有条件地返回了falsey值，可以考虑只忽略该条件，并使用when隐式返回nil。或者，您可以使用when-not，而不是像我在这里那样否定这个条件。