recursion depth exceeded when trying to use a list length relation

[rvadhavk]

I tried writing a list length function, but when computing lists that have a given length, it errors out with RecursionError: maximum recursion depth exceeded in comparison. I tried using Zzz per #30 but am still getting a recursion depth error. Does anyone have advice on how to properly implement a list length function in miniKanren?

Here's my code so far:

from kanren import run, eq, var, conde, conso
from kanren.term import applyo
from operator import add
from kanren.core import Zzz

# a relation between a list l and its length n
def length(l, n):
  empty_case = [eq(l, []), eq(n, 0)]
  tail = var()
  tail_length = var()
  non_empty_case = [conso(var(), tail, l), Zzz(length, tail, tail_length), applyo(add, (tail_length, 1), n)]
  return conde(empty_case, non_empty_case)

x = var()
print(
  run(1, [x], 
    length(x, 2)
  )
)

[brandonwillard]

I can't say exactly what the problem is right now, but one potential issue I can see is that the goal Zzz(length, tail, tail_length) precedes the goal that could potentially ground tail_length.

In general, it's better to ground the logic variables as much as possible before recursing.

[brandonwillard]

Take a look at the implementation of kanren.graph.eq_length.

Also, be careful when using applyo; I believe it's missing some logic that would make applyo(add, (1, 1), 2) succeed.

[majidaldo]

right. got out of a similar situation by just moving Zzz to another 'slot' while still remaining logically equivalent.