Deep/recursive join, all, any, sum, len

Question

I keep forgetting that the standard join() can only take a single iterable, so I made a few functions that act recursively on any passed arguments. Somewhat ironically, the deep version of join() isn't called by the user, but only within the deep version of sum() - the standard sum() breaks and tells you to use join() if you try to sum() strings, but this one just calls the deep join() automatically.

Several questions prompted me to post this here:

1. Is this a good idea? Why didn't Google turn up any results for such a thing (i.e., why doesn't anyone seem to have tried it)?
2. Could anything particularly bad happen with these, like system instability or silent failures?
3. And, of course, how could they be improved? I'd like equal parts readability and speed.

It's 100 lines total, including comments, but each function is between 4 and 12 lines (plus the definition). Feel free to comment on all or any of them.

def _djoin(*args, s=''):
    """
    Executes a recursive string join on all passed arguments and their contents.
    Parameters:
        *args (tuple): An unrolled tuple of arguments.
        s (string): Optional. Separates each element with the given string.
    """
    if len(args) == 1:
        try:
            iter(args[0])
            if type(args[0]) == str:
                raise TypeError
            return s.join(_djoin(arg, s=s) for arg in args[0])
        except TypeError:
            return str(args[0])
    return s.join(_djoin(arg, s=s) for arg in args)

def dall(*args):
    """
    Executes a recursive all() on all passed arguments and their contents.
    Parameter:
        *args (tuple): An unrolled tuple of arguments.
    """
    if len(args) == 1:
        try:
            iter(args[0])
            if type(args[0]) == str or not len(args[0]):
                raise TypeError
            return all(dall(arg) for arg in args[0])
        except TypeError:
            return bool(args[0])
    return all(dall(arg) for arg in args)

def dany(*args):
    """
    Executes a recursive any() on all passed arguments and their contents.
    Parameter:
        *args (tuple): An unrolled tuple of arguments.
    """
    if len(args) == 1:
        try:
            iter(args[0])
            if type(args[0]) == str or not len(args[0]):
                raise TypeError
            return any(dany(arg) for arg in args[0])
        except TypeError:
            return bool(args[0])
    return any(dany(arg) for arg in args)

def dsum(*args, s=0):
    """
    Executes a recursive sum() on all passed arguments and their contents.
    If s is a string, _djoin(args, s) is returned.
    Parameters:
        *args (tuple): An unrolled tuple of arguments.
        s: An initial value to which all other values will be added.
    """
    if type(s) == str:
        return _djoin(*args, s=s)
    if len(args) == 1:
        try:
            iter(args[0])
            if type(args[0]) == str:
                raise TypeError
            return sum((dsum(arg, s=s) if arg else s for arg in args[0]), s)
        except TypeError:
            if type(s) == list:
                return [args[0]]
            return (args[0])
    return sum((dsum(arg, s=s) for arg in args), s)

def ssum(*seq):
    """
    Executes a sum() on the given seq, automatically determining a reasonable start value.
    Parameter:
        *seq (tuple): An unrolled tuple of arguments.
    """
    n = next(iter(seq))
    if len(seq) == 1:
        return sum(n, type(next(iter(n)))())
    return sum(seq, type(n)())

def dlen(*args, deep=False):
    """
    Executes a recursive len() on all passed arguments and their contents.
    Parameters:
        *args (tuple): An unrolled tuple of arguments.
        deep (bool): An initial value to which all other values will be added (with type conversions if necessary).
    """
    if len(args) == 1:
        try:
            iter(args[0])
            if type(args[0]) == str:
                raise TypeError
            return sum((dlen(arg, deep=deep) for arg in args[0]))
        except TypeError:
            if deep and type(args[0]) == str:
                return len(args[0])
            return 1
    return sum((dlen(arg, deep=deep) for arg in args))

This is what I used to test them. Each line prints function results and intended results, successfully thus far. New, more strenuous tests to expose bugs would be welcome.

from deep import *
import datetime as dt

print(_djoin('foo', 'bar', 123, s=' '), '#### foo bar 123')
print(_djoin(['foo', 'bar', 123], s=' '), '#### foo bar 123')
print(_djoin('foo', 'bar', [123,456,789,'baz'], s=' '), '#### foo bar 123 456 789 baz')
print(_djoin(['foo', 'bar', [123,456,789,'baz']], s=' '), '#### foo bar 123 456 789 baz')
print(_djoin([10,11,12, 0.0000000000003], s=' '), '#### 10 11 12 3e-13')
print(' '.join(_djoin([10,11,12, 0.0000000000003])), '#### 1 0 1 1 1 2 3 e - 1 3')

print(dall([1],[1],[[],[]]), False)
print(dall([0],), False)
print(dall(0), False)
print(dall(1), True)
print(dall(1,2,[3]), True)
print(dall([1],), True, '\n')

print(dany([],[0],[[],[]]), False)
print(dany([0],), False)
print(dany(0), False)
print(dany(1), True)
print(dany([0,0],[3]), True)
print(dany([],[1]), True, '\n')

print(dsum(1,2,3), 6)
print(dsum([1,2,3]), 6)
print(dsum(1,[2,3]), 6)
print(dsum([1,2],[3,4],5), 15)
print(dsum([1,2],[3,4], s=[]), [1,2,3,4])
print(dsum([1,2],[3,4],5, s=[]), [1,2,3,4,5])
print(dsum(1,2,3,[4,[5,6]]), 21)
print(dsum('a','b',s='-'), 'a-b')
print(dsum(1,2,3, s='-'), '1-2-3')
print(dsum(1,2,3), 6)
print(dsum(dt.timedelta(3), dt.timedelta(4), s=dt.timedelta()), "7 days, 0:00:00")
print(dsum(1,2,3,[[],[3,0]]), 9, '\n')

print(dlen([1,2,3]), 3)
print(dlen([1,2],[3]), 3)
print(dlen([[1,2],[0],[2,[2,[2]]]]), 6)
print(dlen([['hello',2],[0],[2,[2,[2]]]]), 6)
print(dlen([['hello',2],[0],[2,[2,[2]]]], deep=True), 10, '\n')

print(ssum([[1,2],[3]]), [1,2,3])
print(ssum([1,2,3]), 6)
print(ssum(1,2,3), 6)
print(ssum([1,2],[3]), [1,2,3])

Answer 1

You have a lot of duplication here - the code for flattening the *args tuple appears multiple times. I would factor that out to a single function, _flatten, which could be a generator to deal with large inputs:

def _flatten(iter_):
    if isinstance(iter_, str):
        yield iter_
    else:
        try:
            for obj in iter_:
                yield from _flatten(obj)
        except TypeError:
             yield iter_

(Note that yield from is only available from Python 3.3.) This will neatly unroll your tuple of arguments:

>>> list(_flatten(('foo', 'bar', [123,456,789,'baz'])))
['foo', 'bar', 123, 456, 789, 'baz']

Now e.g. _djoin becomes:

def _djoin(*args, s=''):
    return s.join(map(str, _flatten(args)))

and works just the same:

>>> _djoin('foo', 'bar', [123,456,789,'baz'], s=' ')
'foo bar 123 456 789 baz'

Similarly e.g. dall becomes return all(_flatten(args)).

---

Note that in the above _flatten implementation I've used isinstance, rather than type(iter) == str. This will deal appropriately with inheritance (i.e. subclasses of str will also be handled correctly). dsum should also use this:

def dsum(*args, s=0):
    if isinstance(s, str):
        return _djoin(*args, s=s)
    ...

See e.g. "Differences between isinstance() and type() in python"

---

Your current test suite requires you to read each line to validate whether the outputs were as expected. Life would be much simpler if you used assert for this, for example:

assert _djoin('foo', 'bar', 123, s=' ') == 'foo bar 123'

This will give no output if everything is OK, but raise an error if a test fails:

>>> assert _djoin('foo', 'bar', 123, s=' ') == 'foo bar 123'
>>> assert _djoin('foo', 'bar', 123, s=' ') == 'derp'
Traceback (most recent call last):
  File "<pyshell#18>", line 1, in <module>
    assert _djoin('foo', 'bar', 123, s=' ') == 'derp'
AssertionError

Alternatively, you could consider implementing doctests, e.g.:

def _djoin(*args, s=''):
    """Flatten the arguments and join them together as strings.

        >>> _djoin('foo', 'bar', 123, s=' ')
        'foo bar 123'

    """
    ...

Then at the bottom of deep.py you can easily run all tests with:

if __name__ == '__main__':
    import doctest
    doctest.testmod(verbose=True)

and you will get useful outputs on what was tested, what worked and what didn't. For example, a failing output from my development of ssum below:

...
Trying:
    ssum(1, 2, 3)
Expecting:
    6
ok
Trying:
    ssum('foo', 'bar', 'baz')
Expecting:
    'foobarbaz'
**********************************************************************
File "C:/Python34/deep.py", line 49, in __main__.ssum
Failed example:
    ssum('foo', 'bar', 'baz')
Expected:
    'foobarbaz'
Got:
    'foofoobarbaz'
1 items had no tests:
    __main__
3 items passed all tests:
   2 tests in __main__._djoin
   3 tests in __main__._flatten
   1 tests in __main__.dsum
**********************************************************************
1 items had failures:
   1 of   2 in __main__.ssum
8 tests in 5 items.
7 passed and 1 failed.
***Test Failed*** 1 failures.

(I had passed seq instead of iter_ to _djoin - d'oh!)

---

The ssum implementation seems a bit odd; the repeated use of iter and next makes the code difficult to read and is unlikely to be efficient. Instead, consider something like:

def ssum(*seq):
    """Sum over the sequence, determining a sensible start value.

        >>> ssum(1, 2, 3)
        6
        >>> ssum('foo', 'bar', 'baz')
        'foobarbaz'

    """
    iter_ = _flatten(seq)
    first = next(iter_)
    if isinstance(first, str):
        return _djoin(first, iter_)
    return sum(iter_, first)

This makes it clear that the logic is based on evaluating the type of the first object to determine a "sensible start value".

Answer 2

The reason you have so much code is that you haven't decomposed the problem well. For example, dsum() is responsible for flattening, type-checking, and summing. The flattening work is common to a lot of your functions, and should be delegated to its own function. You'll find that a similar problem has been solved before.

def flatten(*sequence):
    for item in sequence:
        if isinstance(item, str) or not hasattr(item, '__iter__'):
            yield item
        else:
            for i in item:
                yield from flatten(i)
                # yield from is a Python 3.3 feature
                # https://docs.python.org/3/whatsnew/3.3.html#pep-380

def dall(*sequence):
    return all(flatten(*sequence))

def dany(*sequence):
    return any(flatten(*sequence))

# I would just inline _djoin() within dsum().
def _djoin(*sequence, s=''):
    return s.join(str(item) for item in flatten(*sequence))

def dsum(*sequence, s=0):
    if isinstance(s, str):
        return _djoin(*sequence, s=s)
    try:
        return sum(flatten(*sequence), s)
    except TypeError:
        return s + list(flatten(*sequence))

def dlen(*sequence, deep=False):
    def length(item):
        return len(item) if deep and isinstance(item, str) else 1
    return sum(length(item) for item in flatten(*sequence))

These implementations agree with your test cases, with the exception that dall([1],[1],[[],[]]) returns True instead of False as you wanted. This is due to a difference in interpretation. Note that all([]) is True and bool([]) is False. The question is, how deeply do you take the recursion? If you recurse fully into the empty lists, then the result is True. Otherwise, if you treat empty lists as False, then the result is False. The way you have written your dall() with so many special cases, though, I'm inclined to say that your interpretation is artificial.

The function that I haven't reimplemented is ssum(). You say that it "automatically determines a reasonable start value". It isn't at all clear to me what is considered reasonable — it all sounds very arbitrary to me, so basically the function's implementation serves as its own specification.

Answer 3

If you look at your functions, you'll see that they all have almost identical common code:

if len(args) == 1:
    try:
        iter(args[0])
        if type(args[0]) == str or not len(args[0]):
            raise TypeError
        return A(B(arg) for arg in args[0])
    except TypeError:
        return C(args[0])
return A(B(arg) for arg in args)

except for the sections I've replaced with A, B, and C. But even though these parts differ from one function to another, B is always a recursive call to the containing function, A implements the "combining" logic, and C computes the result for a single item.

So you could simplify your code by extracting this common code into a function, for example like this:

def map_reduce_tree(f, r, *args):
    """Apply f to each leaf element of the tree args and combine the
    results by calling r.

    """
    if len(args) == 1:
        try:
            iter(args[0])
            if type(args[0]) == str or not len(args[0]):
                raise TypeError
            return r(map_reduce_tree(f, r, a) for a in args[0])
        except TypeError:
            return f(args[0])
    else:
        return r(map_reduce_tree(f, r, a) for a in args)

Now dall becomes:

map_reduce_tree(bool, all, *args)

and dany becomes:

map_reduce_tree(bool, any, *args)

and dsum becomes:

identity = lambda x:x
map_reduce_tree(identity, sum, *args)

and djoin becomes:

map_reduce_tree(identity, ''.join, *args)

and so on. In case you're wondering why I've called this map_reduce_tree, it's because "map–reduce" is a well-known data processing model, and a tree is the recursive data structure that we're operating on.

Now, we can simplify map_reduce_tree as follows:

1. Instead of calling iter and catching a TypeError if the value doesn't support the iteration interface, we could use the abstract base class collections.abc.Iterable and write isinstance(x, Iterable).

2. Combine the two instances of r(map_reduce_tree(f, r, a) for a in ...) into one.

3. Omit the test not len(args[0]) — it's better for r to handle an empty sequence of arguments, then for f to try to handle it.

That results in:

from collections.abc import Iterable

def map_reduce_tree(f, r, args):
    """Apply f to each leaf element of the tree args and combine the
    results by calling r.

    """
    if isinstance(args, Iterable) and type(args) != str:
        return r(map_reduce_tree(f, r, a) for a in args)
    else:
        return f(args)

But we can decompose the functionality even further. There are really three steps here: (i) walking over the tree recursively finding the leaves, (ii) applying f to each leaf element; (iii) combining the results by calling r. So we can split that into three parts, using the leaves function below for step (i), using the built-in map for step (ii), and just calling r for step (iii).

def leaves(tree):
    """Generate the leaf elements of tree."""
    if isinstance(tree, Iterable) and type(tree) != str:
        for t in tree:
            yield from leaves(t)
    else:
        yield tree

Now dall becomes:

all(leaves(args))

(we don't need to apply bool to the leaves—all does that already). Similarly, dany becomes:

any(leaves(args))

and dsum becomes:

sum(leaves(args))

(since f was the identity function we can just omit the mapping step) and djoin becomes:

''.join(leaves(args))

which I hope you'll agree is a lot shorter and a lot easier to understand than the original.