Stream: helpdesk (published)

Topic: Searching A Tree

John Honaker (Jun 22 2021 at 14:53):

This might be a naive question, but is this a good way of structuring a tree search? If this were Lisp (or I didn't care about type stable return values) I'd just return false if the key wasn't found, the data if it was found.

As it stands I basically have:

struct Tree
    name::Symbol
    data
    children::Vector{Tree}
end

function getindex(t::Tree, s::Symbol)
    if isleaf(t)
        if s == name(t)
            return t.data
        else
            throw(KeyError(s))
        end
    else
        for child in children(t)
            try
                return getindex(child, s)
            catch e
                if !(e isa KeyError)
                    throw(e)
                end
            end
        end
        throw(KeyError(s))
    end
end

John Honaker (Jun 22 2021 at 14:56):

Also, I know I only return data if it's a leaf, as of right now only leaves have data, but I'm not sure I'm going to keep it that way.

Jameson Nash (Jun 22 2021 at 15:42):

Usually Base APIs return Some{T} or Nothing

Jameson Nash (Jun 22 2021 at 15:43):

false is a weird option, that depends on lisp assuming anything that isn't false is true

John Honaker (Jun 22 2021 at 16:47):

Well, they do usually. Either they use nil, #false or something else and then checks like

(define answer (some-or-false-func data))
(if (answer)
    answer ; return answer if some
    (error "Nothing found")) ; throw an error if false

And Some/Nothing totally slipped my mind. Thanks!

Last updated: Nov 06 2024 at 04:40 UTC