Write a Scheme predicate function that tests for the structural equality of two given lists. Two lists are structurally equal if they have the same list structure, although their atoms may be different.

The two lists are structurally equal if they have the same list structure, although their atoms may be different. So, we are going to write a program which checks if elements in both the list at same position are atoms or not. If yes then it should return true else false.

Program:

(define (structurally-equal l1 l2)

(cond ( ? ; if both lists are null  #t)

( ? ; if one of the lists is null but the other is not  #f)

( ? ; if the 'car' part of both lists is an atom

(structurally-equal (cdr l1) (cdr l2)))

( ? ; if the 'car' part of one of the lists is an atom but the other is not  #f)

(else

(and (structurally-equal ? ?)     ; recur over the 'car' of each list

(structurally-equal ? ? ; recur over the 'cdr' of each list

Explanation:

There are two ways of approaches. The first approach uses a function to generate an output that represents the list structure.

1. We could represent the structure of any list as a unique string or number, such that any lists with identical structure would have the same representation and no other list would generate the same output.

2. Write a function that analyses any list's structure and generates that output.

3. Run both lists through the function and compare the output. If the same, they have the same structure.

The second one, which is the approach Oscar has taken, is to recur through both lists at the same time. Here, you pass both lists to one function, which does this:

1. Is the first element of the first list identical (structurally) to the first element of the second? If not, return false.

2.Are these first elements lists? If so, return the result of (and (recur on the first element of both lists) (recur on the rest of both lists))

3. If not, return the result of (recur on the rest of both lists).

The second approach is more efficient in the simple circumstance where you want to compare two lists. It returns as soon as a difference is found, only having to process both lists in their entirety where both lists are, indeed, structurally identical.

so much for the extra points :