Sequence operations

In the following exercises, you can treat sequences as lists or tuples, unless explicitly stated otherwise.

Define a function mysum(seq) that returns the sum of all numbers in the list seq.

def mysum(seq):
    """Return the sum of all numbers in seq.
    In:
        seq - a sequnce of summable items
    Out:
        sum of all items in seq
    """

Solutions

With while:

def mysum(seq):
total = 0
while seq:
    total += seq[0]
    seq = seq[1:]
return total

With for

def mysum(seq):
    total = 0
    for x in seq:
        total += x
    return total

With proc:

from funcutils import proc
mysum = lambda seq: proc((0,seq),
                         lambda s: s[1],
                         lambda s: (s[0]+s[1][0], s[1][1:]))[0]

or

mysum = lambda seq: proc([0]+seq, lambda s: len(s)>1, lambda s: [s[0]+s[1]]+s[2:])[0]

With funcutils.reduce, which is I think as short as you get:

from functools import reduce
from operator import add

mysum = lambda seq: reduce(add, seq)

Another thing that the reduce solution is superior to the others, including Python’s built-in sum, is that it can project the generality of addition. You cannot find the “sum” of a list of lists with sum, but with mysum defined with reduce you can do it:

>>> mysum([[1,2],[3],[4,6,7]])
[1, 2, 3, 4, 6, 7]

One drawback is that reduce-based solution cannot handle empty sequences. For that, you need to specify 0 as a third argument for arithmetic addition and [] for list concatenation.

Library

x = [1,2,3,4]
sum = sum(x)
print(sum) # Output: 10

Define a function myinsert(seq,index,item) that inserts item at position index of the list seq and returns the new list.

def myinsert(seq, index, item):
    """Insert item at index of seq.

    >>> myinsert([1, 2, 3], 1, 4)
    [1, 4, 2, 3]
    >>> myinsert([1, 2, 3], 5, 4)
    [1, 2, 3]
    >>> myinsert([True, False], 2, None)
    [True, False, None]
    >>> myinsert([],0,1)
    [1]
    >>> myinsert([1,4],1,[2,3])
    [1, [2, 3], 4]
    """

Define a function myreverse that reverses a given list. Write 3 versions: using while,for, and proc from funcutils.

Define a function takewhile(alive, seq) that takes elements from the front of the sequence seq as long as the predicate function alive returns True. The function should return a new list containing the taken elements.

Also define the dropwhile(alive, seq) variant that drops elements from the front of the sequence as long as alive returns True, returning the remaining elements as a new list.

def takewhile(alive, seq):
        """Take elements from seq while alive returns True.

        >>> takewhile(lambda x: x < 3, [1, 2, 3, 4, 1])
        [1, 2]
        >>> takewhile(lambda x: x != 0, [1, 2, 3])
        [1, 2, 3]
        >>> takewhile(lambda x: x > 0, [-1, 2, 3])
        []
        >>> takewhile(lambda x: True, [1, 2, 3])
        [1, 2, 3]
        """

Solutions

With proc:

def takewhile(alive, seq):
    return proc(([],seq),
                lambda s: s[1] and alive(s[1][0]),
                lambda s: (s[0] + [s[1][0]], s[1][1:]))[0]

Library

itertools.takewhile

Define a function mymap(func, seq) that applies the function func to each element of the sequence seq and returns a new list containing the results.

def mymap(func, seq):
    """Map func over seq.

    >>> mymap(lambda x: x * 2, [1, 2, 3])
    [2, 4, 6]
    >>> mymap(str, [1, 2, 3])
    ['1', '2', '3']
    """

Criteria

numbers = [1, 2, 3, 4, 5]
squared = list(map(lambda x: x ** 2, numbers))
print(squared)  # Output: [1, 4, 9, 16, 25]

Define a function myfilter(test, seq) that removes items in seq that return False for test.

def myfilter(test, seq):
        """Filter seq by test.

        >>> myfilter(lambda x: x % 2 == 0, [1, 2, 3, 4, 5, 6])
        [2, 4, 6]
        """

Notes

• Solve it with while and also with proc_seq or proc from funcutils.
• The sequence can be implemented as a tuple or a list.
• If you use tuples, you can only manipulate them using slicing and concatenation (+).
• Lists allow for in-place manipulation.
• You can try versions with in-place manipulation (for list based solutions), but make sure you can solve the problem wihhout in-place manipulation.

Library

numbers = [1, 2, 3, 4, 5, 6]
even_numbers = list(filter(lambda x: x % 2 == 0, numbers))
print(even_numbers)  # Output: [2, 4, 6]

Define a function myreduce(seq, func, initial) that reduces the elements of seq using the binary function func, starting with the value initial.

def myreduce(func, seq, initial):
    """Aggregate elements of seq using func starting with initial.

    >>> myaggregate(lambda x, y: x + y, [1, 2, 3], 0)
    6
    >>> myaggregate(lambda x, y: x * y, [1, 2, 3, 4], 1)
    24
    >>> myaggregate(lambda x, y: x + y, [], 10)
    10
    >>> myaggregate(lambda x, y: x - y, [2, 3, 4], 20)
    11
    """

Library

from functools import reduce
numbers = [1, 2, 3, 4]
total = reduce(lambda x, y: x + y, numbers, 0)
print(total)  # Output: 10

Define a function myenumerate(seq) that takes a sequence seq and returns a list of tuples, where each tuple contains an index and the corresponding element from the sequence.

def myenumerate(seq):
    """Enumerate seq into a list of (index, item) tuples.

    >>> myenumerate(['a', 'b', 'c'])
    [(0, 'a'), (1, 'b'), (2, 'c')]
    >>> myenumerate([10, 20, 30, 40])
    [(0, 10), (1, 20), (2, 30), (3, 40)]
    """

Library

items = ['a', 'b', 'c']
enumerated_items = list(enumerate(items))
print(enumerated_items)  # Output: [(0, 'a'), (1, 'b'), (2, 'c')]

Define a function myzip(seq1, seq2) that takes two sequences seq1 and seq2 and returns a list of tuples, where each tuple contains one element from seq1 and the corresponding element from seq2. The length of the returned list should be equal to the length of the shorter input sequence.

def myzip(seq1, seq2):
        """Zip seq1 and seq2 into a list of tuples.

        >>> myzip([1, 2, 3], ['a', 'b', 'c'])
        [(1, 'a'), (2, 'b'), (3, 'c')]
        >>> myzip([1, 2], ['a', 'b', 'c'])
        [(1, 'a'), (2, 'b')]
        >>> myzip([], [1, 2, 3])
        []
        >>> myzip([1, 2, 3], [])
        []
        """

Library

list1 = [1, 2, 3]
list2 = ['a', 'b', 'c']
zipped = list(zip(list1, list2))
print(zipped)

Define a function shuffle(seq) that returns a randomly shuffled version of the input sequence seq without modifying the original sequence. Use the random module.

import random

def shuffle(seq):
        """Return a randomly shuffled version of seq.

        >>> shuffle([1, 2, 3])
        [2, 1, 3]  # example output; actual output will vary
        >>> shuffle(['a', 'b', 'c', 'd'])
        ['c', 'a', 'd', 'b']  # example output; actual output will vary
        """

Notes and criteria

• You cannot use any built-in randomization functions that directly shuffle or sample from sequences.
• You are allowed to use the random module to generate random numbers.
• All auxiliary functions, e.g. for removing an element from a sequence, must be implemented by yourself.
• Solve it with while and with proc from funcutils.

Solutions

With proc:

def shuffle(seq):
    """Non-mutating shuffle of seq"""
    from funcutils import proc
    from random import randint

    return proc(([], seq),
                lambda s:s[1],
                lambda s: (lambda r:
                           (s[0]+[s[1][r]], s[1][0:r]+s[1][r+1:]))
                           (randint(0, len(s[1])-1)))[0]

The above code is cryptic on purpose. If you can work out how my update function works, you are getting well adapted to functional programming. With a separate remove_at function like:

remove_at = lambda seq, index: seq[0:index] + seq[index+1:]

the update function becomes a little clearer:

lambda s: (lambda r:
           (s[0]+[s[1][r]], remove_at(s[1], r)))
           (randint(0, len(s[1])-1))

But still the lambda-in-lambda may be perplexing. We will deal with this kind of constructs later. You can simply use def:

def update(s):
    r = randint(0, len(s[1])-1)
    return (s[0]+[s[1][r]], remove_at(s[1], r))

Library

import random
items = [1, 2, 3, 4, 5]
shuffled_items = random.sample(items, len(items))
print(shuffled_items)  # Output: A randomly shuffled version of items

Define a function freqcount(seq) that takes a sequence seq and returns a dictionary mapping each unique element in the sequence to its frequency of occurrence.

def freqcount(seq):
    """Count frequencies of items in seq.

    >>> freqcount(['a', 'b', 'a', 'c', 'b', 'a'])
    {'a': 3, 'b': 2, 'c': 1}
    >>> freqcount([1, 2, 2, 3, 1, 1, 4])
    {1: 3, 2: 2, 3: 1, 4: 1}
    """

Solutions

A non-mutating solution with reduce would look like:

from functools import reduce

def update_count(fdict, item):
    """Update the frequency dictionary with the given item."""
    return fdict | {item: fdict.get(item, 0) + 1}

def compute_frequencies(token_list):
    """Compute frequency distribution of tokens in the list."""
    return reduce(update_count, token_list, {})

The problem with this solution is that as the update_count function updates the dictionary by creating a new dictionary each time, it is not very efficient.

One remedy for this efficiency problem is to mutate the frequency dictionary in place:

def update_count(fdict, item):
    """Update the frequency dictionary with the given item."""
    fdict[item] = fdict.get(item, 0) + 1
    return fdict

def compute_frequencies(token_list):
    """Compute frequency distribution of tokens in the list."""
    return reduce(update_count, token_list, {})

If we want to avoid the assignment statement in update_count, we need to switch to a third-party library for persistent data structures that make functional updates efficient. Here is a solution with immutables.Map:

from immutables import Map
def update_count(fdict, item):
    """Update the frequency dictionary with the given item."""
    return fdict.set(item, fdict.get(item, 0) + 1)

def compute_frequencies(token_list):
    """Compute frequency distribution of tokens in the list."""
    return reduce(update_count, token_list, Map())

Library

from collections import Counter

def freqcount(seq):
    """Count frequencies of items in seq.
    return dict(Counter(seq))