Clojure

clojure.zip/seq-zip returns spurious nils during traversal

Details

  • Type: Defect Defect
  • Status: Open Open
  • Priority: Minor Minor
  • Resolution: Unresolved
  • Affects Version/s: None
  • Fix Version/s: None
  • Component/s: None
  • Labels:
  • Patch:
    Code

Description

Problem reported by Lee Spector on the mailing list:

https://groups.google.com/d/msg/clojure/8TL7IGmE7N0/u1xfgTOLDRgJ

Here's a quote from Lee's post describing the problem:

Here's an illustration, stepping through '(() 0) with next and printing the node at each step: 

(loop [z (zip/seq-zip '(() 0))] 
  (if (zip/end? z) 
    :done 
    (do (println (zip/node z)) 
      (recur (zip/next z))))) 

That produces: 

(() 0) 
() 
nil 
0 
:done 

I don't expect the nil to be there. 

The underlying cause is that seq-zip passes identity as the children argument to zipper. Applied to (), this returns (), which is truthy, leading zipper to descend into a non-existent subtree.

One natural solution would be to use seq in place of identity:

(defn seq-zip [root]
  (zipper seq?
          seq  ;; changed
          (fn [node children] (with-meta children (meta node)))
          root))

With this change, no nil is produced in the example above. Patch with this change forthcoming.

Activity

Michał Marczyk made changes -
Field Original Value New Value
Attachment 0001-CLJ-1317-fix-seq-zip-to-avoid-spurious-nils.patch [ 12579 ]
Michał Marczyk made changes -
Patch Code [ 10001 ]
Michał Marczyk made changes -
Description Problem reported by Lee Spector on the mailing list:

https://groups.google.com/d/msg/clojure/8TL7IGmE7N0/u1xfgTOLDRgJ

Here's a quote from Lee's post describing the problem:

{noformat}
Here's an illustration, stepping through '(() 0) with next and printing the node at each step:

(loop [z (zip/seq-zip '(() 0))]
  (if (zip/end? z)
    :done
    (do (println (zip/node z))
      (recur (zip/next z)))))

That produces:

(() 0)
()
nil
0
:done

I don't expect the nil to be there.
{noformat}

The underlying cause is that {{seq-zip}} passes {{identity}} as the {{children}} argument to {{zipper}}. Applied to {{()}}, this returns {{()}}, which is truthy, leading {{zipper}} to descend into a non-existent subtree.

One natural solution would be to use {{seq}} in place of {{identity}}:

{noformat}
(defn seq-zip [root]
  (zipper seq?
          seq ;; changed
          (fn [node children] (with-meta children (meta node)))
          root))
{noformat}

With this change, no {{nil}} is produced in the example above. Patch with this change forthcoming.
Problem reported by Lee Spector on the mailing list:

https://groups.google.com/d/msg/clojure/8TL7IGmE7N0/u1xfgTOLDRgJ

Here's a quote from Lee's post describing the problem:

{noformat}
Here's an illustration, stepping through '(() 0) with next and printing the node at each step:

(loop [z (zip/seq-zip '(() 0))]
  (if (zip/end? z)
    :done
    (do (println (zip/node z))
      (recur (zip/next z)))))

That produces:

(() 0)
()
nil
0
:done

I don't expect the nil to be there.
{noformat}

The underlying cause is that {{seq-zip}} passes {{identity}} as the {{children}} argument to {{zipper}}. Applied to {{()}}, this returns {{()}}, which is truthy, leading {{zipper}} to descend into a non-existent subtree.

One natural solution would be to use {{seq}} in place of {{identity}}:

{noformat}
(defn seq-zip [root]
  (zipper seq?
          seq ;; changed
          (fn [node children] (with-meta children (meta node)))
          root))
{noformat}

NB. {{seq}} does act as the identity function when applied to seqs (with the additional side effect of forcing lazy seqs).

With this change, no {{nil}} is produced in the example above. Patch with this change forthcoming.
Michał Marczyk made changes -
Description Problem reported by Lee Spector on the mailing list:

https://groups.google.com/d/msg/clojure/8TL7IGmE7N0/u1xfgTOLDRgJ

Here's a quote from Lee's post describing the problem:

{noformat}
Here's an illustration, stepping through '(() 0) with next and printing the node at each step:

(loop [z (zip/seq-zip '(() 0))]
  (if (zip/end? z)
    :done
    (do (println (zip/node z))
      (recur (zip/next z)))))

That produces:

(() 0)
()
nil
0
:done

I don't expect the nil to be there.
{noformat}

The underlying cause is that {{seq-zip}} passes {{identity}} as the {{children}} argument to {{zipper}}. Applied to {{()}}, this returns {{()}}, which is truthy, leading {{zipper}} to descend into a non-existent subtree.

One natural solution would be to use {{seq}} in place of {{identity}}:

{noformat}
(defn seq-zip [root]
  (zipper seq?
          seq ;; changed
          (fn [node children] (with-meta children (meta node)))
          root))
{noformat}

NB. {{seq}} does act as the identity function when applied to seqs (with the additional side effect of forcing lazy seqs).

With this change, no {{nil}} is produced in the example above. Patch with this change forthcoming.
Problem reported by Lee Spector on the mailing list:

https://groups.google.com/d/msg/clojure/8TL7IGmE7N0/u1xfgTOLDRgJ

Here's a quote from Lee's post describing the problem:

{noformat}
Here's an illustration, stepping through '(() 0) with next and printing the node at each step:

(loop [z (zip/seq-zip '(() 0))]
  (if (zip/end? z)
    :done
    (do (println (zip/node z))
      (recur (zip/next z)))))

That produces:

(() 0)
()
nil
0
:done

I don't expect the nil to be there.
{noformat}

The underlying cause is that {{seq-zip}} passes {{identity}} as the {{children}} argument to {{zipper}}. Applied to {{()}}, this returns {{()}}, which is truthy, leading {{zipper}} to descend into a non-existent subtree.

One natural solution would be to use {{seq}} in place of {{identity}}:

{noformat}
(defn seq-zip [root]
  (zipper seq?
          seq ;; changed
          (fn [node children] (with-meta children (meta node)))
          root))
{noformat}

NB. {{seq}} does act as the identity function when applied to non-empty seqs (with the additional side effect of forcing lazy seqs).

With this change, no {{nil}} is produced in the example above. Patch with this change forthcoming.
Michał Marczyk made changes -
Description Problem reported by Lee Spector on the mailing list:

https://groups.google.com/d/msg/clojure/8TL7IGmE7N0/u1xfgTOLDRgJ

Here's a quote from Lee's post describing the problem:

{noformat}
Here's an illustration, stepping through '(() 0) with next and printing the node at each step:

(loop [z (zip/seq-zip '(() 0))]
  (if (zip/end? z)
    :done
    (do (println (zip/node z))
      (recur (zip/next z)))))

That produces:

(() 0)
()
nil
0
:done

I don't expect the nil to be there.
{noformat}

The underlying cause is that {{seq-zip}} passes {{identity}} as the {{children}} argument to {{zipper}}. Applied to {{()}}, this returns {{()}}, which is truthy, leading {{zipper}} to descend into a non-existent subtree.

One natural solution would be to use {{seq}} in place of {{identity}}:

{noformat}
(defn seq-zip [root]
  (zipper seq?
          seq ;; changed
          (fn [node children] (with-meta children (meta node)))
          root))
{noformat}

NB. {{seq}} does act as the identity function when applied to non-empty seqs (with the additional side effect of forcing lazy seqs).

With this change, no {{nil}} is produced in the example above. Patch with this change forthcoming.
Problem reported by Lee Spector on the mailing list:

https://groups.google.com/d/msg/clojure/8TL7IGmE7N0/u1xfgTOLDRgJ

Here's a quote from Lee's post describing the problem:

{noformat}
Here's an illustration, stepping through '(() 0) with next and printing the node at each step:

(loop [z (zip/seq-zip '(() 0))]
  (if (zip/end? z)
    :done
    (do (println (zip/node z))
      (recur (zip/next z)))))

That produces:

(() 0)
()
nil
0
:done

I don't expect the nil to be there.
{noformat}

The underlying cause is that {{seq-zip}} passes {{identity}} as the {{children}} argument to {{zipper}}. Applied to {{()}}, this returns {{()}}, which is truthy, leading {{zipper}} to descend into a non-existent subtree.

One natural solution would be to use {{seq}} in place of {{identity}}:

{noformat}
(defn seq-zip [root]
  (zipper seq?
          seq ;; changed
          (fn [node children] (with-meta children (meta node)))
          root))
{noformat}

With this change, no {{nil}} is produced in the example above. Patch with this change forthcoming.
Hide
Michał Marczyk added a comment - - edited

Note that the docstring of clojure.zip/zipper asks that the children argument return a seq of children. The rest of clojure.zip, however, expects nil to be returned when there are no children, as evidenced by this problem.

One could argue that this behaviour of the rest of clojure.zip should be fixed, but I think it makes sense and is convenient. Perhaps the docstring should be adjusted, though.

Show
Michał Marczyk added a comment - - edited Note that the docstring of clojure.zip/zipper asks that the children argument return a seq of children. The rest of clojure.zip, however, expects nil to be returned when there are no children, as evidenced by this problem. One could argue that this behaviour of the rest of clojure.zip should be fixed, but I think it makes sense and is convenient. Perhaps the docstring should be adjusted, though.
Alex Miller made changes -
Labels zip

People

Vote (1)
Watch (1)

Dates

  • Created:
    Updated: