Signal Processing View

Learning Objectives

At the end of this sub-unit, students should

• understand the signal processing view.
• know to solve problems with signal processing view.

Listening to Music

Given map and filter, we are going to look at problem solving in a slightly different way. This approach takes advantage on the fact that there are many common operations involving sequence. To see this approach called signal processing view, we will need to learn from the music industry.

For music afficionados, listening to music is a serious business. There are many gadgets that can be used to maximize their enjoyment. These gadgets work on signal, because music can be represented as superposition of signals. It can start from the music source (e.g., radio), to equalizer, to amplifier, and to speaker before finally the sound reach you.

Basic SetupAdd FilterChange Source

¹

¹

¹

Some of the advantages of this arrangement is the following.

1. Modularity: Each gadgets are independent of other gadgets and may be reused.
2. Clarity: Separates data (i.e., signal) from processes (i.e., the operations of the gadgets).
3. Flexibility: New components can be added, some components can be swapped with others when needed.

In other words, if the connections between gadgets are correct, it can be a simple plug and play.

Signal in Programming

To use the signal processing view of programming, we need to first identify what is a signal. Let us take a look more closely at a signal. Consider a signal represented as a sine graph. It is typically an analog and continuous.

But this is difficult to use because computer works in discrete steps so it cannot process continuous signal. We then label points at some discrete interval. Finally, we discard the rest and only keep these points. If we need a finer details then we need to decrease our interval.

ContinuousLabelDiscrete

If we have a discrete signal, we can store them easily in a list (or tuple). So in signal processing view, a signal is simply a list of values. Now that we know what a signal is supposed to be in programming, we can categorize functions based on this view. These functions are the equivalent of the gadgets.

Name	Description
Producer	Creates the initial signal
Filter	Removes some elements from the signal
Mapper	Modifies the elements in the signal
Consumer	Consumes the signal and may produce a result

We already have the filter and mapper gadgets which are our filter and map functions respectively. What about producer and consumer?

Producer

We can look at some simple way we can produce a list. What we do not want is to have the list already being the solution. So our initial list must be simple. The simplest producer is really just a producer of constant values. Is this useful? Maybe. But we will create them anyway.

Constant

def constant(val, size):
  return [val] * size   # repetition operation!

Now, if we are dealing with integers, then there are simple sequences we can work with. This sequence is range. But it may be difficult with range. So we want to at least work with list. There is another simple way to convert and that is to use the list(...) constructor.

If we are going to use this for quite a number of times, we might as well abstract this further and create a function called an enumerator(start, stop) that produces a list of numbers [start, start + 1, start + 2, ..., stop]. The difference with range(start, stop) is that we include the stop. Why include? This is merely our convention.

The next question is why not include step? We will show that it is not relevant because we can process them afterwards to mimic the behavior of having a step. Remember, we want the producer to be simple so that it can be used in a lot more places.

Enumerator

def enumerator(start, stop):
  return list(range(start, stop + 1))

For other kinds of producers, we may have to think further. Say, for example, we want an alternating inputs or we want something like the sine graph above, we may need our own custom producers.

Consumer

The next thing we need to know is the consumers. What are some example of a simple consumer? The simplest is probably simply counting the number of elements in the signal that are still present. This is simply the len(...) function. So we will not be creating a function for this.

Other simple consumers are called aggregation functions. There are many ways to aggregate signals as shown below.

• Finding the maximum element.
• Finding the minimum element.
• Finding the sum of all elements.
• Finding the product of all elements.
• Finding the average of the elements.

For the first two, we also have the built-in functions max and min respectively. Similarly for the third aggregation function, we have sum. We will show a code for product as there is no built-in function for this without importing external modules.

Product

def product(lst):
  res = 1
  for elem in lst:
    res = res * elem
  return res

As for the last one, believe it or not, we can use the pre-existing aggregation functions to compute this. The average is simply the sum divided by the count. There is unfortunately cases where it may fail. If the count is 0, then we will be dividing by 0. The same difficulty is also present in max and min.

Average

def avg(lst):
  return sum(lst) / len(lst)

Recap that we have generalized the idea of sum and product into an accumulator. We can use the concept of an accumulator for our consumer as well. However, using what we know so far, we can try to use functions instead of blanks for some operations.

We show the code for accumulator below. This accumulator is now catered for list. Additionally, we give the recursive variant of it using the idea of inductive list. We will assume that there is a function op(x, y) that is a straightforward function.

Accumulator for List

Iterative

def accumulator(lst):
  res = ░░░░
  for elem in lst:
    res = op(res, elem)
  return res

Recursive

def accumulator(lst):
  if len(lst) == 0:
    return ░░░░
  else:
    return op(accumulator(lst[1:]), lst[0])

Can we actually remove the blank completely? Yes, this blank can be lifted to parameters. So now, it can be supplied by the caller.

Accumulator for List

Iterative

def accumulator(lst, base):
  res = base
  for elem in lst:
    res = op(res, elem)
  return res

Recursive

def accumulator(lst, base):
  if len(lst) == 0:
    return base
  else:
    return op(accumulator(lst[1:]), lst[0])

Workflow

The workflow in signal processing view of programming is shown below. We start with a single producer. Then we pass the signal (i.e., list) through the series of filters and mappers. There may be many filters and many mappers. These filters and mappers can also be alternating. Finally, at the end, we consume the signal to produce the solution.

What the workflow above also shows is that we only have a single producer and a single consumer. If this workflow does not map to a single problem, we will still need to decompose the problem into smaller subproblems. We may find out that in the end we can share some producers and we may need to integrate the output of the consumers. So divide and conquer should still be the default first step in problem solving.

As a quick summary, let us show the gadgets that we have excluding filter and map.

Summary of Gadgets

Category	Function	Description
Producer	constant(val, size)	Returns a list with size number of val
Producer	enumerate(start, stop)	Returns a list of consecutive integer from start to stop inclusive of stop
Consumer	len(lst)	Returns the number of elements in the sequence lst
Consumer	max(lst)	Returns the largest element in the sequence lst
Consumer	min(lst)	Returns the smallest element in the sequence lst
Consumer	sum(lst)	Returns the sum of the sequence lst
Consumer	product(lst)	Returns the product of the sequence lst
Consumer	avg(lst)	Returns the average of the elements in the sequence lst
Consumer	accumulator(lst, base)	Returns the accumulation of the elements in the sequence lst by specifying op(x, y)

Putting It All Together

We will now illustrate the idea of solving problems with signal processing view.

Sum of Squares of Odd

Sum of Squares of Odd

Problem Description

Given a positive integer \(m\), we want to find the sum of the first \(m\) non-negative odd numbers.

Task

Write the function sum_squares_odd(m) that accepts an integer m. The function returns the sum of of squares of the first m non-negative odd numbers.

Assumptions

• m is a positive integers (i.e., m > 0).

Restrictions

• You are to use signal processing view to solve the problem.

Looking at our gadget, we will need to specify the gadgets we will be using to solve this problem. There are two ways to do this.

• 2m Number Filter Odd

  ---

  

• m Numbers Map to Odd

  ---

  

We can see that the list going into the consumer is a list with the following pattern. We can be sure that this gives us the solution regardless of how it is produced.

[1 ** 2, 3 ** 2, 5 ** 2, ..., (2 * m - 1) ** 2]

We now need to think carefully about which producer we use as we are already set on which consumer to use. Additionally, we have already designed our lambdas for filter and mapper. What we need to be careful of is to always convert the result of filter and map to list to avoid further complication. It is not necessary in this case, but it is always good to do.

The advantage of our enumerate is that we can simply look at the first and last value. Then we let the start and stop be the first and last value respectively. In both versions below, lst1 and lst2 acts as our "signals" between the gadgets (i.e., enumerate, filter, map, and sum).

Sum of Squares of Odd

• 2m Number Filter Odd

  ---

  def sum_squares_odd(m):
    lst1 = enumerate(1, 2 * m)
    lst2 = list(filter(lambda n: n % 2 == 1,
                       lst1))
    lst3 = list(map(lambda n: n * n, lst2))
    return sum(lst3)
  

• m Numbers Map to Odd

  ---

  def sum_squares_odd(m):
    lst1 = enumerate(1, m)
    lst2 = list(map(lambda n: 2 * n - 1,
                    lst1))
    lst3 = list(map(lambda n: n * n, lst2))
    return sum(lst3)
  

Chaining

We can also chain the operations and make it into a single line code. We provide the code for one of the variant. Try to construct the one line solution for the other variant.

def sum_squares_odd(m):
  return sum(list(map(lambda n: n * n, list(filter(lambda n: n % 2 == 1, enumerate(1, 2 * m))))))

Highest Paid Programmer

Let us try with a slightly more complicated problem.

Highest Paid Programmer

Problem Description

A personnel record (denoted personnel) is an ADT with the following set of functions.

• is_programmer(personnel) returns True if the personnel is a programmer and False otherwise.
  • The type annotation is (personnel::personnel) -> bool.
• get_name(personnel) returns the name of the personnel.
  • The type annotation is (personnel::personnel) -> str.
• get_salary(personnel) returns the salary of the personnel.
  • The type annotation is (personnel::personnel) -> float.

We want to find the personnel with the highest salary given a list of personnel records.

Task

Write the function highest_paid(personnels) that accepts a list of personnel records personnels and returns the salary of the highest paid personnel.

Assumptions

• personnels[i] is a personnel.
• personnels is a non-empty list (i.e., len(personnels) > 0).

Restrictions

• You are to use signal processing view to solve the problem.
• You are NOT allowed to break abstraction.

In this case, we do not have any producer because the parameter is already the first signal. So there is nothing to do for producer. Instead, what we need to do is to first remove any non-programmers. Once we have only programmers, we retrieve the salary. Afterwards, we have a signal comprising only of salaries of programmers. The consumer will then simply find the largest salary. The function get_name is there only to cause confusion.

---

1. Images by Athok at thenounproject. ↩↩↩