<SYSTEM_TASK:>
Solve the following problem using Python, implementing the functions described below, one line at a time
<END_TASK>
<USER_TASK:>
Description:

def template_ds(basedir, varname, vars, lookup_fatal=True, depth=0):
    ''' templates a data structure by traversing it and substituting for other data structures '''

    if isinstance(varname, basestring):
        m = _varFind(basedir, varname, vars, lookup_fatal, depth)
        if not m:
            return varname
        if m['start'] == 0 and m['end'] == len(varname):
            if m['replacement'] is not None:
                return template_ds(basedir, m['replacement'], vars, lookup_fatal, depth)
            else:
                return varname
        else:
            return template(basedir, varname, vars, lookup_fatal)
    elif isinstance(varname, (list, tuple)):
        return [template_ds(basedir, v, vars, lookup_fatal, depth) for v in varname]
    elif isinstance(varname, dict):
        d = {}
        for (k, v) in varname.iteritems():
            d[k] = template_ds(basedir, v, vars, lookup_fatal, depth)
        return d
    else:
        return varname