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
  • Approval:
    Triaged

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
Alex Miller made changes -
Approval Triaged [ 10120 ]
Michał Marczyk made changes -
Assignee Michał Marczyk [ michalmarczyk ]
Hide
Alex Miller added a comment -

Michał, can I ask why you assigned this to yourself - was there something you planned to add?

Show
Alex Miller added a comment - Michał, can I ask why you assigned this to yourself - was there something you planned to add?
Hide
Michał Marczyk added a comment -

Hey Alex, I was going to attach a separate patch with a proposal for a docstring adjustment along the lines suggested above (will do that tonight). No change to the code, though, and I guess not worth assigning the ticket – sorry about the unnecessary ping.

Show
Michał Marczyk added a comment - Hey Alex, I was going to attach a separate patch with a proposal for a docstring adjustment along the lines suggested above (will do that tonight). No change to the code, though, and I guess not worth assigning the ticket – sorry about the unnecessary ping.
Hide
Alex Miller added a comment -

No worries, just wanted to know if something was still pending - I will wait to prescreen it.

Show
Alex Miller added a comment - No worries, just wanted to know if something was still pending - I will wait to prescreen it.

People

Vote (1)
Watch (1)

Dates

  • Created:
    Updated: