Looking for a key in a nested dict


#1

Hello everyone,

I’m trying to search for a specific key in a deeply nested dict which can also contain arrays.
In a first step I import a yaml file which I parse using YAML.jl. This gives me a nested dict.
If we take the truncated example of the README file from the YAML.jl package:

# data.yml
receipt:     Oz-Ware Purchase Invoice
date:        2012-08-06
customer:
    given:   Dorothy
    family:  Gale

This would be parsed as

julia> using YAML

julia> data = YAML.load(open("data.yml"))
Dict{Any,Any} with 3 entries:
  "receipt"  => "Oz-Ware Purchase Invoice"
  "customer" => Dict{Any,Any}(Pair{Any,Any}("given", "Dorothy"),Pair{Any,Any}("…
  "date"     => 2012-08-06

How would I access in for instance the value of the “given” form the dict corresponding to “customer”?
I would like to achieve this in a general way, where there could be multiple levels of nesting.

I tried to translate the following python code which I found on StackExchange:

def retrieve_nested_value(mapping, key_of_interest):
    mappings = [mapping]
    while mappings:
        mapping = mappings.pop()
        try:
            items = mapping.items()
        except AttributeError:
            # we didn't store a mapping earlier on so just skip that value
            continue

        for key, value in items:
            if key == key_of_interest:
                yield value
            else:
                # type of the value will be checked in the next loop
                mappings.append(value)

where mapping is a dict.

This is my attempt to translate it to julia

function retreive_nested_value(dict, key_of_interest)
    dictv = [dict]
    while isempty(dictv) == false
        dict = pop!(dictv)
        for (key,value) in dict
            if key == key_of_interest
                return value
            else
                dictv = [dictv , [value]]
            end
        end
    end
end

But unfortunately, it gives me only the values of the first level (same as get(dict, key_of_interest,0)). I cannot fetch the values of the lower levels.

How would one do this in julia?
Many thanks in advance,
Olivier


#2

Wouldn’t this be a classic case of recursion? This code can be easily modified to push multiple positive results to an array.

function retrieve(dict, key_of_interest)
        for (key, value) in dict
        if key == key_of_interest
        	return value
        end
        if value isa Dict
            return  retrieve(value, key_of_interest)
        end
    end
end

#3

Nice, could possibly also descend into any AbstractDict.


#4

Thanks a lot for looking into this,

Unfortunately, the code does not return anything.
Should I do something extra to get the values?
I tried on both julia 0.6.4 and 0.7

Could you do it without recursion?

Thanks again


#5

It definitely returns something, provided the key is the Dict somewhere. Could you give a minimum working example? Recursion is definitely the default way to solve these kinds of problems.


#7

t definitely returns something, provided the key is the Dict somewhere.

Yes indeed. My bad. It works fine when the key occurs only once.
If it occurs multiple times, then nothing is returned.

I’m trying now to add multiple occurrences into an array as you said.

Thanks again!


#8

I’m not sure I understand what you mean.
Could you expand a little?


#9

If it ocurs multiple times, only the first appearance of the key is returned. Here is an implementation that takes into account multiple returns

function retrieve(dict, key_of_interest, output = []) # default value is an empty array
               for (key, value) in dict
               if key == key_of_interest
                       push!(output, value)
               end
               if value isa AbstractDict
                   retrieve(value, key_of_interest, output)
               end
           end
           return output
       end

#10

ok, great!

I just managed a similar solution, but yours is much more elegant.
Here is mine:

function retrieve2(dict, key_of_interest)
    values = Vector{Any}()
    for (key, value) in dict
        if key == key_of_interest
            append!(values,[value])
        end
        if value isa Dict
            val =  retrieve(value, key_of_interest)
        append!(values,val)
        end
     end
     return values   
end

Thanks again to all of you!


#11

This topic was automatically closed 12 days after the last reply. New replies are no longer allowed.