Weaving elements into a list

I have the following problem statement:

Modify a given list such that one specific element is "weaved" into that list.

Examples if the element is 'module':

• [] remains []
• ['a'] remains ['a']
• ['a', 'b'] becomes ['a', 'module', 'b']
• ['a', 'b', 'c'] becomes ['a', 'module', 'b', 'module', 'c']

I solved it using the following code in Python 3.4:

@staticmethod
def __weave_element_into_list(element, values: list) -> list:
"""
Weaves an element into a given list.

Examples if the element is 'module':
- Input [] remains [].
- Input ['a'] remains ['a'].
- Input ['a', 'b'] becomes ['a', 'module', 'b'].
- Input ['a', 'b', 'c'] becomes ['a', 'module', 'b', 'module', 'c'].
- etc.

:param element: The element to weave into the list
:param values:  The original list
:return:    The list with element weaved into it.
"""
copy_list = list(values)
if len(copy_list) <= 1:
return copy_list
i = 1
while i < len(copy_list):
copy_list.insert(i, element)
i += 2
return copy_list


Is there a better (more Pythonic?) solution to it and is "weaving" the correct operation here?

• Where's the rest of the class? What context is this used in? – jonrsharpe May 31 '15 at 12:33

The function could be replaced with this line:

return list(chain.from_iterable(zip(values, [element] * len(values))))[:-1]


Essentially, zipping values with another list of the same size containing element in all values, flattening the zip, and chopping off the end.

if len(copy_list) <= 1:
return copy_list


This is more Pythonic:

if not copy_list:
return copy_list


I'm also wondering if this needs to be a @staticmethod. Since it's a pure function, I'd just call it weave. Here's the complete implementation with doctests:

from itertools import chain

def weave(element, values: list) -> list:
"""
>>> weave('module', [])
[]
>>> weave('module', ['a'])
['a']
>>> weave('module', ['a', 'b'])
['a', 'module', 'b']
>>> weave('module', ['a', 'b', 'c'])
['a', 'module', 'b', 'module', 'c']

:param element: The element to weave into the list
:param values: The original list
:return: The list with element weaved into it.
"""
return list(chain.from_iterable(zip(values, [element] * len(values))))[:-1]


I see @jonrsharpe beat me to the doctests. To add something new, another way to run doctests:

python -m doctest yourfile.py


Update

Originally I proposed this one-liner:

return sum(zip(values, [element] * len(values)), ())[:-1]


But that turns out to be a bad idea. This other discussion is also illuminating.

• Using sum(lst, ()) instead of flatten borders on obfuscation – Caridorc May 31 '15 at 21:06
• @Caridorc you're absolutely right, thanks for picking on it. I updated my post with a different solution, and some related links at the bottom. – janos May 31 '15 at 21:30
• Consider zip_longest(values, repeat(element, max(len(values) - 1, 0))) — this avoids the unnecessary allocation of the list of elements, and it avoids the unnecessary copy due to the [:-1]. – Gareth Rees Jun 1 '15 at 13:44

Firstly, you can make the examples into doctests, so that you can actually run them to check the function works:

class Class:  # or whatever it's called

@staticmethod
def __weave_element_into_list(element, values: list) -> list:
"""
Weaves an element into a given list.

Examples:

>>> Class._Class__weave_element_into_list('module', [])
[]
>>> Class._Class__weave_element_into_list('module', ['a'])
['a']
>>> Class._Class__weave_element_into_list('module', ['a', 'b'])
['a', 'module', 'b']
>>> Class._Class__weave_element_into_list('module', ['a', 'b', 'c'])
['a', 'module', 'b', 'module', 'c']

:param element: The element to weave into the list
:param values: The original list
:return: The list with element weaved into it.
"""
copy_list = list(values)
if len(copy_list) <= 1:
return copy_list
i = 1
while i < len(copy_list):
copy_list.insert(i, element)
i += 2
return copy_list

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


Now, note how awkward it is to have to call Class._Class__weave_element_into_list, due to the "name mangling" invoked by the leading double underscore in the method name. Per the style guide, this should only be used:

To avoid name clashes with subclasses

instead if you want the method to be considered 'private':

Use one leading underscore only for non-public methods and instance variables.

Without seeing the rest of your code it's also hard to say why you've made this a method, rather than just a standalone function.

Your weave operation works exactly like the join method for str:

>>> ' module '.join('')
''
>>> ' module '.join('a')
'a'
>>> ' module '.join('ab')
'a module b'
>>> ' module '.join('abc')
'a module b module c'


so perhaps that would be a better term to adopt for it.

• I don't understand why you are bothering with a class at all... in Python, it is perfectly fine for a function to just be a function. – Adam Jun 1 '15 at 3:45
• @codesparkle that's a better comment for the OP than for me! – jonrsharpe Jun 1 '15 at 6:15

Haskell calls this function intersperse.

In Python, loops where you manually increment the index tend to be awkward. I propose the following solution:

import itertools

def intersperse(element, iterable):
def alternation():
for item in iterable:
yield element
yield item
return list(itertools.islice(alternation(), 1, None))


islice() is just a handy way to drop the first element of the result. You could also write it this way without itertools:

def intersperse(element, iterable):
def alternation():
for item in iterable:
yield element
yield item
result = alternation()
next(result, None)
return list(result)


Your __weave_element_into_list() has a scalability problem: inserting elements into the middle of a list requires a lot of work to shift all subsequent items. The weave() function proposed in Rev 2 of @janos's answer involved even more copying, since tuples are immutable; the revision in Rev 3 has much better performance characteristics.

Benchmark:

import timeit

functions = ('intersperse', 'weave2', 'weave3', '__weave_element_into_list')
print('length  ' + ' '.join('{:12s}'.format(f) for f in functions))
for length in [0, 1, 10, 100, 1000, 10000]:
print('{0:6d}  '.format(length) +
' '.join('{: >3.10f}'.format(
timeit.timeit("f('alligator', range({}))".format(length),
setup="from __main__ import {} as f".format(f),
number=100)) for f in functions))


Result:

length  intersperse  weave2       weave3       __weave_element_into_list
0  0.0002215109 0.0001669568 0.0002566511 0.0000781892
1  0.0002748552 0.0002680188 0.0003487850 0.0001115086
10  0.0003961320 0.0003857883 0.0004681549 0.0005727541
100  0.0019150120 0.0054596220 0.0015901779 0.0048249909
1000  0.0183790531 0.3636222179 0.0120774899 0.0711144698
10000  0.1597181219 41.7615168821 0.1375140301 3.6747105517