comparing two lists recrusively

Question

my professor gave me a python assignment to compare 2 two dimensional lists, return True if all objects in the lists are similar and False if they are not. the lists are of type- list[list[int]]. this must be done using recursion. I am not allowed to use loops or slicing. (but can access a specific index in the list) the inner division of the lists may be different but as long as all elements in similar places in the list are similar the function will return True. for example- [[1], [2, 3, 4]] , [[1, 2], [3, 4]] - the function will return true. I hope the details are clear, thank you!

my question is to find a solution to this problem :)

user_9690090 · Answer

Usually you do l[0] and l[1:] for car and cdr (first and rest) of the list.

The biggest challenge of this task is the forbidding of slicing.

But with

first, *rest = your_list

It works! Not only without slicing but also without indexing.

def first(l):        # traditionally in Lisp languages `CAR`
    car, *cdr = l
    return car
    
def rest(l):         # traditionally in Lisp languages `CDR`
    car, *cdr = l
    return cdr

def comp(lol1, lol2):
    if len(lol1) == len(lol2) == 0:  # recursion end condition
        return True
    # if first elements are lists, `comp`are the firsts and the rests
    elif type(first(lol1)) == type(first(lol2)) == list:
        return comp(first(lol1), first(lol2)) and \
               comp(rest(lol1), rest(lol2))
    # if first elements are atoms (non-lists), `==` the firsts and `comp`are the rest
    else: # then the firsts are atoms!
        return first(lol1) == first(lol1) and \
               comp(rest(lol1), rest(lol2))
    
# traditionally in Lisp languages, you test not for list
# but for `atom` (whether the first elements of the lists are
# non-lists -> atomar). But `atom` is not that easy test in Python.
# so it is must more easy to ask whether both first elements are lists - and 
# if not - then it is clear that the first elements of non-empty lists must be non-lists => atoms.

This works with Python3 but not with Python2.

For Python2 and Python3, you can use the function definitions:

def first(l):
    return (lambda x, *y: x)(*l)

def rest(l):
    return (lambda x, *y: y)(*l)

With single indexing and `.pop()`

Perhaps what your teacher thought of was:

def first(l):
    return l[0]
    
def rest(l):
    if l != []:
        l.pop()
        return l
    else:
        return []

# For definition of the `comp()` function see above

But this solution is problematic, because it changes the input list, since Python does call-by-reference and not call-by-value. To avoid this, one has to deep-copy the list first. One can shallow-copy a list with slicing, but slicing is not allowed ...

Like:

q = [1, 2, [3, 4], [5, 6, 7], 8]
comp(q, q)
## True
# so far so good, but:
q
## []

user_15897202 · Answer

a1 = [[1], [2, 3, 4]]
a2 = [[1, 2], [3, 4]]

def get_next_indexes(i, j, a):  # function for getting next indexes based on previous
    return (i + 1, 0)if j >= len(a[i]) - 1 else (i, j + 1)

def compare_lists(i1, j1, i2, j2):  # i1 and j1 - indexes for first array; i2 and j2 - indexes for second array
    if i1 >= len(a1) or i2 >= len(a2):
        print("Two lists are equal.")
        exit(0)
    if a1[i1][j1] != a2[i2][j2]:
        print("Two lists are not equal.")
        exit(0)
    print(get_next_indexes(i1, j1, a1))
    compare_lists(*get_next_indexes(i1, j1, a1), *get_next_indexes(i2, j2, a2))

compare_lists(0, 0, 0, 0)

comparing two lists recrusively

2 Answers

With single indexing and .pop()

With single indexing and `.pop()`