Weaving elements into a list

Question

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?

• jonrsharpe: Where's the rest of the class? What context is this used in?

Answer 1

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.

About your original implementation, instead of this:

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.

• Caridorc: Using sum(lst, ()) instead of flatten borders on obfuscation
• janos: @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.
• Gareth Rees: 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].

Answer 2

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.

• Adam: 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.
• jonrsharpe: @codesparkle that's a better comment for the OP than for me!

Answer 3

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