7

Supposing I had a list as follows:

mylist = ['a','b','c','d']

Is it possible to create, from this list, the following dict without using recursion/a recursive function?

{
  'a': {
    'b': {
      'c': {
        'd': { }
      }
    }
  }
}
Óscar López
  • 232,561
  • 37
  • 312
  • 386
Phillip B Oldham
  • 18,807
  • 20
  • 94
  • 134
  • Well, recursion === iteration, so yes. Do you have any code to show what you've tried? Perhaps an answer can build off of that. – Makoto Nov 05 '12 at 18:41
  • you can use simply `map`, `reduce` – Dmitry Zagorulkin Nov 05 '12 at 18:42
  • @Makoto there's no specific use case I have in mind. I was simply reviewing a number of FOSS projects and noticed that most, if not all, used recursion (not incorrectly). It just got me thinking as to whether there was an alternative to recursion. Óscar López's answer is rather insightful (specifically the link), too. – Phillip B Oldham Nov 06 '12 at 19:15

5 Answers5

11

For the simple case, simply iterate and build, either from the end or the start:

result = {}
for name in reversed(mylist):
    result = {name: result}

or

result = current = {}
for name in mylist:
    current[name] = {}
    current = current[name]

The first solution can also be expressed as a one-liner using reduce():

reduce(lambda res, name: {name: res}, reversed(mylist), {})
Martijn Pieters
  • 1,048,767
  • 296
  • 4,058
  • 3,343
3

For this simple case at least, yes:

my_list = ['a', 'b', 'c', 'd']
cursor = built_dict = {}
for value in my_list:
    cursor[value] = {}
    cursor = cursor[value]
Silas Ray
  • 25,682
  • 5
  • 48
  • 63
3

Or for fancyness and reduced readability:

dict = reduce(lambda x, y: {y: x}, reversed(myList), {})
Jesse the Game
  • 2,600
  • 16
  • 21
1

It's worth mentioning that every recursion can be converted into iteration, although sometimes that might not be so easy. For the particular example in the question, it is simple enough, it's just a matter of accumulating the expected result in a variable and traversing the input list in the appropriate order. This is what I mean:

def convert(lst):
    acc = {}
    for e in reversed(lst):
        acc = {e: acc}
    return acc

Or even shorter, the above algorithm can be expressed as a one-liner (assuming Python 2.x, in Python 3.x reduce was moved to the functools module). Notice how the variable names in the previous solution correspond to the lambda's parameters, and how in both cases the initial value of the accumulator is {}:

def convert(lst):
    return reduce(lambda acc, e: {e: acc}, reversed(lst), {})

Either way, the function convert works as expected:

mylist = ['a','b','c','d']
convert(mylist)

=> {'a': {'b': {'c': {'d': {}}}}}
Community
  • 1
  • 1
Óscar López
  • 232,561
  • 37
  • 312
  • 386
0
mydict = dict()
currentDict = mydict
for el in mylist:
  currentDict[el] = dict()
  currentDict = currentDict[el]
user711413
  • 761
  • 5
  • 12