Looking into conso's documentation, it seems that maps are not being properly considered as collections:

```
user> (coll? {:a 1}) ; Just for context
true
user> (first {:a 1})
[:a 1]
user> (run* [p q] (conso p q {:a 1})) ; This is the surprising part
()
user> (run* [p q] (conso p q [[:a 1]])) ; For comparison
([[:a 1] ()])
user> (doc conso) ; Docs talk about collection as expected input
-------------------------
clojure.core.logic/conso
([a d l])
A relation where l is a collection, such that a is the first of l
and d is the rest of l. If ground d must be bound to a proper tail.
nil
```

EDIT: Also doesn't work for sets:

```
user> (run* [p q] (conso p q #{1 3}))
()
user> (first #{1 3})
1
user> (coll? #{1 3})
true
```