Pop At Index Induction Step

remaining elements after [ x, xs ] is popped at index idx and visited stack is v = remaining elements after xs is popped at index (idx - 1) and visited stack is [ x, v ]

This property allows us to do 3 things:

1. Pop the first element from the original list
2. Push the same element into the "visited" list
3. Decrease the index by one.

Using this property, we can add elements to the "visited" list one by one, until the index is 0.

Examples

remaining elements after [ 2, [ 4, [ 8, [ ] ] ] ] is popped at index 1 and visited stack is [ ] = remaining elements after [ 4, [ 8, [ ] ] ] is popped at index (1 - 1) and visited stack is [ 2, [ ] ]

remaining elements after [ Orange, [ "Tomato", [ ] ] ] is popped at index 2 and visited stack is [ "Apple", [ ] ] = remaining elements after [ "Tomato", [ ] ] is popped at index (2 - 1) and visited stack is [ Orange, [ "Apple", [ ] ] ]

remaining elements after [ True, [ True, [ False, [ ] ] ] ] is popped at index 0 and visited stack is [ ] = remaining elements after [ True, [ False, [ ] ] ] is popped at index (0 - 1) and visited stack is [ True, [ ] ]

Note that the elements are being added to the "visited" list in reverse. In example 2, "Apple" is originally before "Orange," but in the visited list, "Orange" is before "Apple."

Comments

Please log in to add comments