"Deep length" of a list

A list that contains one or more lists as elements is called a deep
list. For example, [1, [2, 3], 4] is a deep list.


Write a function deep_len that takes a list and returns its deep
length. See the doctests for the function's behavior.


Hint: you can check if something is a list by using the built-in
type function. For example,

>>> type(3) == list
False
>>> type([1, 2, 3]) == list
True

My solution:

def deep_len(lst):
    """Returns the deep length of the list.

    >>> deep_len([1, 2, 3])     # normal list
    3
    >>> x = [1, [2, 3], 4]      # deep list
    >>> deep_len(x)
    4
    >>> x = [[1, [1, 1]], 1, [1, 1]] # deep list
    >>> deep_len(x)
    6
    """
    if not lst:
        return 0
    if type(lst[0]) != list:
        return 1 + deep_len(lst[1:])
    else:
        return deep_len(lst[0]) + deep_len(lst[1:])

Can we improve this recursive code?

I would write that simply:

def deep_len(lst):
    """Returns the deep length of the list.

    >>> deep_len([1, 2, 3])     # normal list
    3
    >>> x = [1, [2, 3], 4]      # deep list
    >>> deep_len(x)
    4
    >>> x = [[1, [1, 1]], 1, [1, 1]] # deep list
    >>> deep_len(x)
    6
    """
    return sum(deep_len(el) if isinstance(el, list) else 1 for el in lst)

Note that:

• This doesn't create lots of new lists with slices, so I would expect it to be more efficient;

• isinstance is a much more Pythonic way to check types than type, despite what the "hint" says, as it handles inheritance better; and

• There's no need to special-case an empty lst, as the result is already zero in that case.

StackExchange Code Review Q#97217, answer score: 8