Answered: Define a recursive function removeAll…

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Question

Define a recursive function removeAll that expects an item and a Lisp-like list as arguments. This function returns a Lisp-like list with all of the instances of the item removed.

In the lisplist.py file, make sure to include the insert() and equal() methods from Programming exercise 9.7 and Programming exercise 9.8.

Hint: Keep on removing the item if it equals the list’s first item.

Here is an example of its use:

>>> lyst = cons(2, cons(2, (cons 3, THE_EMPTY_LIST))) >>> lyst (2 2 3) >>> removeAll(2, lyst) (3) >>> removeAll(3, lyst) (2 2)

File: lisplist.py

Project 9.9

Adds a removeAll function for Lisp lists.

Add the insert() and equal() methods from Programming Exercise 9.7 and 9.8

"""

class Node(object):

"""Represents a singly linked node."""

def __init__(self, data, next = None):

self.data = data

self.next = next

def __repr__(self):

"""Returns the string representation of a nonempty lisp list."""

def buildString(lyst):

if isEmpty(rest(lyst)):

return str(first(lyst))

else:

return str(first(lyst)) + " " + buildString(rest(lyst))

return "(" + buildString(self) + ")"

THE_EMPTY_LIST = None

# Basic functions

def isEmpty(lyst):

"""Returns True if lyst is empty or False otherwise."""

return lyst is THE_EMPTY_LIST

def first(lyst):

"""Returns the item at the head of lyst.

Precondition: lyst is not empty."""

return lyst.data

def rest(lyst):

"""Returns a list of items in lyst, after the first one.

Precondition: lyst is not empty."""

return lyst.next

def cons(item, lyst):

"""Adds item to the head of lyst and

returns the resulting list."""

return Node(item, lyst)

# Auxiliary functions

def contains(item, lyst):

"""Returns True if item is in lyst or

False otherwise."""

if isEmpty(lyst):

return False

elif item == first(lyst):

return True

else:

return contains(item, rest(lyst))

def get(index, lyst):

"""Returns the item at position index in lyst.

Precondition: 0 <= index < length(lyst)"""

if index == 0:

return first(lyst)

else:

return get(index - 1, rest(lyst))

def length(lyst):

"""Returns the number of items in lyst."""

if isEmpty(lyst): return 0

else: return 1 + length(rest(lyst))

def buildRange(lower, upper):

"""Returns a list containing the numbers from

lower through upper.

Precondition: lower <= upper"""

if lower == upper:

return cons(lower, THE_EMPTY_LIST)

else:

return cons(lower, buildRange(lower + 1, upper))

def remove(index, lyst):

"""Returns a list with the item at index removed.

Precondition: 0 <= index < length(lyst)"""

if index == 0:

return rest(lyst)

else:

return cons(first(lyst),

remove(index - 1, rest(lyst)))

def insert(index, item, lyst):

"""Returns a list with the item inserted at index.

Precondition: 0 <= index < length(lyst)"""

#Add from exercise 7

def equals(lyst1, lyst2):

"""Returns True if list1 equals lyst2."""

#Add from exercise 8

def main():

"""Create a list with 9..0 and print it."""

lyst = THE_EMPTY_LIST

for i in range(10):

lyst = cons(i, lyst)

print("List =", lyst)

print("Length =", length(lyst))

if __name__ == "__main__":

main()

Expert Solution

Step by step

Solved in 2 steps

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions