bug in clojure.zip when calling next on empty list node?

205 views
Skip to first unread message

Lee Spector

unread,
Dec 21, 2013, 11:49:33 AM12/21/13
to clo...@googlegroups.com

When I step through a zipper made from a nested list via seq-zip, I get extraneous nils after processing a nested ().

Is this somehow expected behavior, or a bug, or am I misunderstanding something fundamental?

The problem seems to arise only when an nested empty list is present, not other nested lists and not other nested empty sequences (see example at bottom for this bit).

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.

If I do this with a 1 in place of the () then it works as I expect:

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

produces:

(1 0)
1
0
:done

It also works as I expect if I put (1) in place of (), suggesting that it's not a problem with stepping over nested lists in general, but just with stepping over ():

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

produces:

((1) 0)
(1)
1
0
:done

However, if I use non-list sequences then things seem to work as I would expect:

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

produces:

([] 0)
[]
0
:done

This is with Clojure 1.5.1.

It's leading to null pointer exceptions in my application, so any explanations or fixes or pointers would be very much appreciated.

Thanks,

-Lee

Lee Spector

unread,
Dec 21, 2013, 5:59:16 PM12/21/13
to clo...@googlegroups.com

On Dec 21, 2013, at 11:49 AM, Lee Spector wrote:

>
> When I step through a zipper made from a nested list via seq-zip, I get extraneous nils after processing a nested ().
>
> Is this somehow expected behavior, or a bug, or am I misunderstanding something fundamental?
>
> The problem seems to arise only when an nested empty list is present, not other nested lists and not other nested empty sequences (see example at bottom for this bit).

I take it back about it working correctly with other nested empty sequences. I realize now that my example of that had a nested empty vector, not a sequence. Trying to reproduce that example with a nested empty sequence just confused me, because it turns out that (seq ()) = (seq []) = nil, and I'm not sure what that means... But this is all really a distraction from the case I care about, which is lists that contain (among other things) nested empty lists. For example, '(() 0). Here it seems to me that zip/next's behavior is clearly wrong and I'm not sure why or what to do about it.

Thanks,

-Lee

Micha Niskin

unread,
Dec 22, 2013, 12:02:35 PM12/22/13
to clo...@googlegroups.com

Also, what about this:

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

Which produces:

((nil) 0)
(nil)
nil
0
:done

Lee Spector

unread,
Dec 22, 2013, 12:26:01 PM12/22/13
to clo...@googlegroups.com

On Dec 22, 2013, at 12:02 PM, Micha Niskin wrote:

> Also, what about this:
>
> (loop [z (zip/seq-zip '((nil) 0))]
> (if (zip/end? z)
> :done
> (do (println (zip/node z))
> (recur (zip/next z)))))
>
> Which produces:
>
> ((nil) 0)
> (nil)
> nil
> 0
> :done

I think that's actually fine. The nil is visited and printed as any other element would be. Maybe you expect nil to be handled specially? I'm not sure why, but in any event this is not the issue that I raised.

The issue I was rasing is that, when traversing '(() 0) with zip/next, one should first visit the root, then (), and then 0. But what actually happens is that between then () and the 0 one lands on a non-existent nil node. So one ends up visiting 4 nodes when there are only 3, and the extra one is a nil.

As I mentioned previously this leads to null pointer exceptions in my application, and the only ways around it that I see are recoding everything without zippers or some nasty special case hackery.

It's also possible that I just don't understand something fundamental about zippers and that this is supposed to happen. But if that's not true -- if it's really a bug -- then it'd be great if this could be fixed.

Thanks,

-Lee

Micha Niskin

unread,
Dec 22, 2013, 2:50:34 PM12/22/13
to clo...@googlegroups.com

What I was getting at there was that it seems like nil could mean a leaf node with the value nil or the absence of leaf nodes, and the two situations can't be distinguished.

--
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient with your first post.
To unsubscribe from this group, send email to
clojure+u...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to a topic in the Google Groups "Clojure" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/clojure/8TL7IGmE7N0/unsubscribe.
To unsubscribe from this group and all its topics, send an email to clojure+u...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Cedric Greevey

unread,
Dec 23, 2013, 3:40:28 AM12/23/13
to clo...@googlegroups.com
On Sun, Dec 22, 2013 at 12:26 PM, Lee Spector <lspe...@hampshire.edu> wrote:
The issue I was rasing is that, when traversing '(() 0) with zip/next, one should first visit the root, then (), and then 0. But what actually happens is that between then () and the 0 one lands on a non-existent nil node. So one ends up visiting 4 nodes when there are only 3, and the extra one is a nil.

As I mentioned previously this leads to null pointer exceptions in my application, and the only ways around it that I see are recoding everything without zippers or some nasty special case hackery.

Point of order: I'm somewhat dubious of the contention that wrapping the output of the traversal in (filter identity ...) before passing it to whatever's throwing the NPEs quite qualifies as "nasty special case hackery". :)

Lee Spector

unread,
Dec 23, 2013, 8:26:05 AM12/23/13
to clo...@googlegroups.com
For one thing it wouldn't be quite that simple because in my application I'm not just collecting all of the nodes (from which I could indeed easily filter out nils), but rather doing things like getting or operating on the nth element of the tree, which I reach via n applications of zip/next, and I'd have to add a condition to check each result along the way and not count it if it's nil. And if I have "legitimate" nils in the tree somewhere then I'd have to do something more complicated to distinguish those (which should be counted) from the "phantom" nils that zip/next is inserting in certain circumstances.

The bigger point, though, is that if I'm right that this is a bug then I think it's a pretty fundamental one in a core Clojure data structure, and it shouldn't be something that one has to discover and work around.

-Lee

Lee Spector

unread,
Dec 29, 2013, 1:14:23 PM12/29/13
to clo...@googlegroups.com

I realize that many people are on holiday, but I'm hoping to get some clarity about how to proceed with respect to this issue in the near future.

Can anyone tell if I'm right that this is a bug in clojure.zip? If so, then is the right thing to do to post an issue on JIRA?

I've re-included the crux of the issue [slightly edited and recombined] below.

Thanks,

-Lee


On Dec 21, 2013, at 11:49 AM, Lee Spector wrote:
> When I step through a zipper made from a nested list via seq-zip, I get extraneous nils after processing a nested ().
>
> Is this somehow expected behavior, or a bug, or am I misunderstanding something fundamental?
>
> The problem seems to arise only when an nested empty list is present, not other nested lists [... deleted ...]
>
> 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.

> [That is,] when traversing '(() 0) with zip/next, one should first visit the root, then (), and then 0. But what actually happens is that between then () and the 0 one lands on a non-existent nil node. So one ends up visiting 4 nodes when there are only 3, and the extra one is a nil.

John Mastro

unread,
Dec 31, 2013, 7:45:06 AM12/31/13
to clo...@googlegroups.com
Hi Lee,

> Can anyone tell if I'm right that this is a bug in clojure.zip? If so, then is the right thing to do to post an issue on JIRA?

I don't have any insight regarding whether this is a bug (haven't yet had an opportunity to dig into clojure.zip or zippers in general). However, I think you're right that opening a ticket on JIRA is the next step.

- John

Armando Blancas

unread,
Dec 31, 2013, 5:08:01 PM12/31/13
to clo...@googlegroups.com
The implementation of seq-zip uses seq? as its branching predicate. As a result the zipper goes down on () thinking it can have children:

user=> (seq? ())
true
user=> (seq? {})
false
user=> (seq? #{})
false
user=> (seq? [])
false

Lee Spector

unread,
Dec 31, 2013, 6:15:49 PM12/31/13
to clo...@googlegroups.com

On Dec 31, 2013, at 5:08 PM, Armando Blancas wrote:

> The implementation of seq-zip uses seq? as its branching predicate. As a result the zipper goes down on () thinking it can have children:
>
> user=> (seq? ())
> true
> user=> (seq? {})
> false
> user=> (seq? #{})
> false
> user=> (seq? [])
> false

Does that mean that you think that the behavior is correct and expected?

It goes down () thinking it can have children -- fine -- but when there aren't any children shouldn't zip/next continue until it hits the next thing? Why should it "land" on a non-existent nil instead?

Compare:

Traversing '((1) 0) with zip/next we get 4 items: ((1) 0), (1), 1, 0

Traversing '(() 0) with zip/next we also get 4 items: (() 0), (), nil, 0

It seems to me that these shouldn't both give 4 things, since the second clearly contain one less thing. That alleged nil just isn't there. Note also that:

Traversing '((nil) 0)) with zip/next we also get 4 items: ((nil) 0), (nil), nil, 0

That one seems right to me -- there really IS a nil there this time. But the one with () doesn't.

If I'm alone in this then I guess I'll just write my own zip_really_next that does what I expect, but I'm curious if others also think that the current behavior is correct.

Thanks,

-Lee


Michał Marczyk

unread,
Dec 31, 2013, 6:53:29 PM12/31/13
to clojure
Ticket with patch at

http://dev.clojure.org/jira/browse/CLJ-1317

The problem is that seq-zip uses clojure.core/identity as the
"children" argument to zipper. Applied to (), this returns (), but
clojure.zip expects the "children" function to return nil when there
are no children. The patch attached to the ticket above changes
identity to seq inside seq-zip. This suffices to fix the behaviour
discovered by Lee.

Cheers,
Michał
> --
> --
> You received this message because you are subscribed to the Google
> Groups "Clojure" group.
> To post to this group, send email to clo...@googlegroups.com
> Note that posts from new members are moderated - please be patient with your first post.
> To unsubscribe from this group, send email to
> clojure+u...@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/clojure?hl=en
> ---
> You received this message because you are subscribed to the Google Groups "Clojure" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to clojure+u...@googlegroups.com.

Michał Marczyk

unread,
Dec 31, 2013, 6:56:52 PM12/31/13
to clojure
Oh, and of course you can use the amended version now to obtain the
expected results:

(defn seq-zip
"Returns a zipper for nested sequences, given a root sequence"
{:added "1.0"}
[root]
(zipper seq?
seq
(fn [node children] (with-meta children (meta node)))
root))

As noted in a comment on the ticket, clojure.zip/zipper's documetation
actuals asks that the children argument return a seq of nodes. The
rest of clojure.zip, however, expects nil when there are no children.
One could argue that it is that expectation that needs fixing, but I
think the current behaviour makes sense; perhaps the docstring should
be adjusted, though.

Cheers,
Michał

Lee Spector

unread,
Dec 31, 2013, 8:12:12 PM12/31/13
to clo...@googlegroups.com

On Dec 31, 2013, at 6:53 PM, Michał Marczyk wrote:

> Ticket with patch at
>
> http://dev.clojure.org/jira/browse/CLJ-1317

[and]
> Oh, and of course you can use the amended version now to obtain the
> expected results: ///


Thank you so much Michał!

-Lee

Michał Marczyk

unread,
Dec 31, 2013, 8:33:16 PM12/31/13
to clojure
No worries.

Incidentally, akhudek's fast-zip seems to have the same issue. Here's
a PR fixing it:

https://github.com/akhudek/fast-zip/pull/3

Cheers,
Michał
Reply all
Reply to author
Forward
0 new messages