2

This is my iterative solution:

def exists(key, arg):
    if not arg:
        return False
    else:
        for element in arg:
            if  isinstance(element,list):
                for i in element:
                    if i==key:
                        return True
            elif element==key:
                return True
    return False
print(exists("f", ["a", ["h", "e", "j"], ["t", "e", "s", "c", "o"]]))

However, my L.A. wants a double recursive function to solve this.

my attempt:

def exists(key, arg):
    if not arg: //base case
        return False
    elif arg[0]==key: //if we find the key from the first trial
        return True
    else:
        return (exists(arg[0:],key))

This doesn't work; it shouldn't, because there is no stop. Also, it does not account for lists of lists; I don't know how to do that.

Any answer, comment, etc. is appreciated

Improve this question
2
  • 1
    arg[0:] == arg. Your recursive call needs to be on arg[1:] Commented Sep 22, 2016 at 14:18
  • Why does your LA want double recursion? This is easy enough to solve with single recursion? As you can see, 3 of the 4 solutions so far have only one recursion. Commented Sep 22, 2016 at 15:44

5 Answers 5

Reset to default
3

If we consider these cases:

  • my_list is empty: the key isn't found
  • my_list is not a list: the key isn't found
  • my_list is a non-empty list (two cases):
    • my_list[0] is the key: it was found
    • otherwise, look for the key in both my_list[0] and my_list[1:]

the code would be

def exists(key, my_list):
    if not isinstance(my_list, list) or not my_list:
        return False

    return (my_list[0] == key
            or exists(key, my_list[0]) 
            or exists(key, my_list[1:]))

or even

def exists(key, my_list):
    return (isinstance(my_list, list)
            and len(my_list) > 0 
            and (my_list[0] == key
                 or exists(key, my_list[0])
                 or exists(key, my_list[1:])))
Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

@Leowahyd Oops, I left a couple of parentheses in that one. (Edited.)
3 
def exists(k, l):
    if not isinstance(l, list):
        return False
    if k in l:
        return True
    return any(map(lambda sublist: exists(k, sublist), l))
Improve this answer

Comments

2

The logic is to iterate each element in your list and check:

  • if list: call the function again with the sub-list.
  • if equals the key: return True
  • else: return False

Below is sample code to find whether key exists or not in nested list

def exists(key, my_list):
    for item in my_list:
        if isinstance(item, list):
            if exists(key, item):  # <--Recursive Call
                return True
        elif item == key:
            return True
    return False

# Example
>>> my_list = [[[1, 2, 3, 4, 5], [6, 7,]], [8, 9], 10]
>>> exists(2, my_list)
True
>>> exists(6, my_list)
True
>>> exists(8, my_list)
True
>>> exists(10, my_list)
True
>>> exists(11, my_list)
False
Improve this answer

1 Comment

Sorry, you're right.I think the OP is looking for a solution with no loops, though (thus the doubly-recursive question).
2

You are close. You only have to check if arg[0] is a sublist and if make a new call. Next you are missing a loop to run through all items of the list. This should work.

def exists(key, arg):
    for item in arg:
        if isinstance(item, list):
            # Recursive call with sublist
            if exists(key, item):
                return True
        else:
            if item == key:
                return True
    return False
Improve this answer

Comments

2

Thanks everyone for your help, here is the answer that I have figured out. While it does not look as elegant as most of the answers that were already provided, this answer is the only answer that my lab instructor will accept as it is a pure functional programming method meaning no side effects or for loops:

def exists(key, seq):
    if not seq:
        return False
    elif seq[0]==key:
        return True
    if isinstance(seq[0],list):
        return(exists(key,seq[0]) or exists(key,seq[1:]))

    else:
        return exists(key,seq[1:])
    return False
print(findkey("s", ["g","t", "e", ["s"], ["l","k","s",["d","f"],"w"], "o"]))
Improve this answer

3 Comments

Glad you found a solution that works! I'm curious if you could advise as to why my answer would not be considered functional programming.
@CraigBurgler Thanks again man! Sorry it was really hard to choose who to give the best answer to, as most of the answers were awesome and informative. Apperntly or at least according our L.I functional programming means that a function shouldnt change any variable so when you call if key in list you are using the built in iterator in python which essentially is changing variables while doing that! I am not sure if that is an answer, but i am more of an imprative programmer and dont usually care about such details which appearntly matter a lot in functional programming
Thanks for your reply! I was just curious about your statement that none of the solutions were purely functional. It seems to me that 3 of the 4 contributed solutions neither use loops nor change variables, other than assigning to function parameters which yours does as well. I was just interested in learning what specifically makes the three solutions not functional and how your solution is different.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.