## Posts Tagged ‘Higher-Order Functions’

### Function composition via folding

December 2, 2012

Let us suppose that we are given a list of functions. We would like to compose the functions in this list (if they are composable, of course) in the order in which they are arranged in the list, i.e., we would like to create a higher-order function compose such that

$\text{compose} \,\, [f_0, f_1, \dots, f_{n-1}] = f_0 \circ f_1 \circ \dots \circ f_{n-1}$

Here is one of many possible implementations in Haskell:

compose :: [(a -> a)] -> (a -> a)
compose = foldr (.) (\x -> x)

where we use a right-fold to compute the composition. Note that the identity function is defined anonymously. What happens if we apply compose to the empty list? We should obtain the identity function. Let us see if this is the case:

compose [] = foldr (.) (\x -> x) [] = (\x -> x)

Indeed, it is the case: if we apply compose to the empty list, we obtain the identity function. What is the type of this identity function? We load the two-line script above into GHCi and experiment a bit:

*Main> let id = compose []
*Main> :t id
id :: a -> a
*Main> map id [0..9]
[0,1,2,3,4,5,6,7,8,9]
*Main> map id ['a'..'z']
"abcdefghijklmnopqrstuvwxyz"

We thus obtain a polymorphic identity function that merely outputs its input, regardless of the type of the input. So far, so good. What happens if we apply compose to a non-empty list? Here is some more equational reasoning:

compose [f0,f1,f2] = foldr (.) (\x -> x) [f0,f1,f2]
= foldr (.) (\x -> x) (f0 : f1 : f2 : [])
= f0 . (f1 . (f2 . (\x -> x)))

A couple of days ago, we saw how to compose a function with itself $n$ times. This is a special case of composing a list of functions, of course. Using function replicate, we can compose a function f with itself $n$ times in the following manner:

compose (replicate n f) = foldr (.) (\x -> x) (replicate n f)

as suggested by Reid Barton. Let us now repeat the experiment we did perform a couple of days ago, but using the new compose:

*Main> let f =  (\n -> (n+1) mod 64)
*Main> let h = compose (replicate 64 f)
*Main> map h [0..63]
[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,
16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,
32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,
48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63]

In the next posts, we will do some interesting things with this compose.

### Composing an endofunction with itself

November 30, 2012

Suppose we are given an endofunction $f : \mathcal{X} \to \mathcal{X}$. Let us introduce a new function $f^{(n)}$, where $n \geq 0$, which we define recursively as follows

$f^{(k)} = f \circ f^{(k-1)}, \qquad{} f^{(0)} = \text{id}$

where $\text{id} : \mathcal{X} \to \mathcal{X}$ is the identity function on $\mathcal{X}$, i.e., $\text{id} (x) = x$ for all $x \in \mathcal{X}$. In Haskell, it is easy to create a higher-order function compose that composes an endofunction $f$ with itself $n$ times:

compose :: (a -> a) -> Integer -> (a -> a)
compose f 0 = (\x -> x)
compose f k = f . (compose f (k-1))

where the identity function is defined anonymously. If you happen to dislike anonymity in your functions, here is another implementation:

compose :: (a -> a) -> Integer -> (a -> a)
compose f 0 = identity
compose f k = f . (compose f (k-1))

identity :: a -> a
identity x = x

There are many other alternatives. Take a look at this Stack Overflow thread. I particularly liked Reid Barton‘s elegant solution using a right-fold:

compose f n = foldr (.) id (replicate n f)

where id = (\x -> x). Beautiful, isn’t it? If this one-liner does not convert you to Haskell, then nothing will.

__________

Example

Let $\mathbb{Z}_{64} := \{0, 1,\dots,63\}$, and let function $f$ be defined by

$\begin{array}{rl} f : \mathbb{Z}_{64} &\to \mathbb{Z}_{64}\\ n &\mapsto n+1 \pmod{64}\end{array}$

This function corresponds to a cyclic shift. Therefore, we expect to have $f^{(64)} = \text{id}$. Let $g := f^{(32)}$ and $h := f^{(64)}$. We load the script above into GHCi, and voilà, we have the session:

*Main> let ns = [0..63]
*Main> let f =  (\n -> (n+1) mod 64)
*Main> map f ns
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,
17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,
33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,
49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,0]

So far, so good! Let us take a look at $g$ and $h$:

*Main> let g = compose f 32
*Main> let h = compose f 64
*Main> map g ns
[32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,
48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,
0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,
16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31]
*Main> map h ns
[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,
16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,
32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,
48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63]

Indeed, as we expected, we have $f^{(64)} = \text{id}$.

__________

Everything in this post is elementary. But now that the elements are solid, we can dare to attempt more sophisticated things. Like what? Like composing lists of (distinct) functions. I am thinking of permutations. I am thinking of perfect shuffles.

### Generating all words over an alphabet

October 1, 2012

An alphabet $\Sigma$ is a finite set of symbols. A word $w$ of length $n$ over an alphabet $\Sigma$ is a sequence of symbols from $\Sigma$, i.e.,

$w : \{0,1,\dots,n-1\} \to \Sigma$

Alternatively, we can view a word $w$ of length $n$ over the alphabet $\Sigma$ as an $n$-tuple (i.e., an ordered list with $n$ elements) over $\Sigma$, i.e., $w \in \Sigma^n$. The set of all finite words over $\Sigma$, including the empty word $\varepsilon$, is denoted by $\Sigma^*$, where $*$ is the Kleene star.

We thus encounter the following problem:

Problem: Given an alphabet $\Sigma$, how do we generate all the words over $\Sigma$? In other words, given $\Sigma$, how do we generate the Kleene closure $\Sigma^*$?

The following Haskell script solves this problem:

g :: [a] -> [[a]] -> [[a]]
g alphabet = concat . map (\xs -> [ xs ++ [s] | s <- alphabet])

allwords :: [a] -> [[a]]
allwords alphabet = concat $iterate (g alphabet) [[]] where alphabet must be a finite list, otherwise the execution of the script won’t ever terminate. The script above, although short, uses a lot of machinery: list comprehension, higher-order functions map and iterate, concatenation of lists of lists, and partial function application. Let us test this script. First, we load it into GHCi. Then we can run a GHCi session: *Main> -- define alphabet *Main> let alphabet = [0,1] *Main> -- define function f *Main> let f = g alphabet *Main> -- check type *Main> :t f f :: [[Integer]] -> [[Integer]] *Main> -- apply f to several lists of lists *Main> f [[]] [[0],[1]] *Main> (f . f) [[]] [[0,0],[0,1],[1,0],[1,1]] *Main> (f . f . f) [[]] [[0,0,0],[0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1]] So far, so good. Suppose that we would like to find all words over alphabet $\Sigma_2 := \{0,1\}$ whose length is less than or equal to $4$. How many such words are there? There are $|\Sigma_2|^k = 2^k$ words of length $k$. Hence, there are $\displaystyle\sum_{k=0}^n 2^k = \frac{2^{n+1} -1}{2-1} = 2^{n+1} - 1$ binary words of length less than or equal to $n$. Hence, if we make $n = 4$, then we obtain $2^{n+1}-1 = 31$. Continuing our GHCi session: *Main> take 31$ allwords alphabet
[[],[0],[1],
[0,0],[0,1],[1,0],[1,1],
[0,0,0],[0,0,1],[0,1,0],[0,1,1],
[1,0,0],[1,0,1],[1,1,0],[1,1,1],
[0,0,0,0],[0,0,0,1],[0,0,1,0],[0,0,1,1],
[0,1,0,0],[0,1,0,1],[0,1,1,0],[0,1,1,1],
[1,0,0,0],[1,0,0,1],[1,0,1,0],[1,0,1,1],
[1,1,0,0],[1,1,0,1],[1,1,1,0],[1,1,1,1]]

Very nice! We could use this in Coding Theory! For example, suppose that we would like to find all binary words of length $8$ whose Hamming weight is equal to $5$. There are

$\displaystyle\binom{8}{5} = \frac{8!}{3! 5!} = 56$

such words. We can find them as follows:

*Main> -- take all words of length less than or equal to 8
*Main>  let words = take 511 \$ allwords alphabet
*Main> -- filter out binary words of length 8
*Main> let wordsL8 = filter (\xs -> length xs == 8) words
*Main> length wordsL8
256
*Main> -- filter out binary words of length 8
*Main> -- and also of Hamming weight equal to 5
*Main> let wordsL8H5 = filter (\xs -> sum xs == 5) wordsL8
*Main> length wordsL8H5
56
*Main> wordsL8H5
[[0,0,0,1,1,1,1,1],[0,0,1,0,1,1,1,1],[0,0,1,1,0,1,1,1],
[0,0,1,1,1,0,1,1],[0,0,1,1,1,1,0,1],[0,0,1,1,1,1,1,0],
[0,1,0,0,1,1,1,1],[0,1,0,1,0,1,1,1],[0,1,0,1,1,0,1,1],
[0,1,0,1,1,1,0,1],[0,1,0,1,1,1,1,0],[0,1,1,0,0,1,1,1],
[0,1,1,0,1,0,1,1],[0,1,1,0,1,1,0,1],[0,1,1,0,1,1,1,0],
[0,1,1,1,0,0,1,1],[0,1,1,1,0,1,0,1],[0,1,1,1,0,1,1,0],
[0,1,1,1,1,0,0,1],[0,1,1,1,1,0,1,0],[0,1,1,1,1,1,0,0],
[1,0,0,0,1,1,1,1],[1,0,0,1,0,1,1,1],[1,0,0,1,1,0,1,1],
[1,0,0,1,1,1,0,1],[1,0,0,1,1,1,1,0],[1,0,1,0,0,1,1,1],
[1,0,1,0,1,0,1,1],[1,0,1,0,1,1,0,1],[1,0,1,0,1,1,1,0],
[1,0,1,1,0,0,1,1],[1,0,1,1,0,1,0,1],[1,0,1,1,0,1,1,0],
[1,0,1,1,1,0,0,1],[1,0,1,1,1,0,1,0],[1,0,1,1,1,1,0,0],
[1,1,0,0,0,1,1,1],[1,1,0,0,1,0,1,1],[1,1,0,0,1,1,0,1],
[1,1,0,0,1,1,1,0],[1,1,0,1,0,0,1,1],[1,1,0,1,0,1,0,1],
[1,1,0,1,0,1,1,0],[1,1,0,1,1,0,0,1],[1,1,0,1,1,0,1,0],
[1,1,0,1,1,1,0,0],[1,1,1,0,0,0,1,1],[1,1,1,0,0,1,0,1],
[1,1,1,0,0,1,1,0],[1,1,1,0,1,0,0,1],[1,1,1,0,1,0,1,0],
[1,1,1,0,1,1,0,0],[1,1,1,1,0,0,0,1],[1,1,1,1,0,0,1,0],
[1,1,1,1,0,1,0,0],[1,1,1,1,1,0,0,0]]

where we used function take (again) and higher-order function filter. The two predicates were built using anonymous functions.

I am happy with this script. Please let me know in case you are not.

__________

Related:

### Computing state trajectories using scans

January 15, 2012

Consider a class of dynamical systems of the form

$x_{k+1} = f (x_k, u_k )$

where $x_k$ is the state, $u_k$ is the input, and $f : \mathcal{X} \times \mathcal{U} \to \mathcal{X}$ is the state-transition function, where $\mathcal{X}$ and $\mathcal{U}$ are the state set and input set, respectively.

Given an initial state $x_0$ and a (possibly infinite) input sequence $(u_0, u_1, u_2, \dots)$, we would like to compute the state trajectory $(x_0, x_1, x_2, x_3, \dots)$. Iterating, we obtain

$\begin{array}{rl} x_1 &= f (x_0, u_0)\\ x_2 &= f (x_1, u_1) = f (f (x_0, u_0), u_1)\\ x_3 &= f (x_2, u_2) = f (f (x_1, u_1), u_2) = f (f (f (x_0, u_0), u_1), u_2)\end{array}$

and so on. Let us pause to take a look at the following equation

$x_3 = f (f (f (x_0, u_0), u_1), u_2)$.

If you happen to be acquainted with functional programming, you will probably recognize this pattern. It is a left fold!! Hence, for every integer $N \geq 1$, we can compute $x_N$ in Haskell using function foldl, as follows

$\text{foldl} \, f \, x_0\, [u_0, u_1, \dots, u_{N-1}]$.

However, we would like to obtain the intermediate states $x_1, x_2, \dots, x_{N-1}$ as well. We can compute the entire state trajectory using function scanl instead

$\text{scanl} \, f \, x_0\, [u_0, u_1, \dots, u_{N-1}]$

which returns a (finite) list of states $[ x_0, x_1, \dots, x_N]$. Amazingly (or perhaps not), since Haskell is lazy, we can obtain a state trajectory of infinite length corresponding to a given initial state and a given input sequence of infinite length!

__________

Example

Consider the logistic map with a control input

$x_{k+1} = r x_k (1 - x_k) + u_k$

where we will use $r = 3.8$, for which the dynamics (of the unforced system) are chaotic. Let the initial state be $x_0 = 0$ (note that $x = 0$ is a fixed-point of the unforced logistic map), and let the input sequence be a discrete-time sinusoid of infinite length

$u_k = \displaystyle\frac{1}{5} \sin \left(\frac{\pi}{10} k\right)$

whose period is $20$. The following Haskell program computes the infinite-length state trajectory using the aforementioned scanl trick:

-- define logistic map with control input
f :: Floating a => a -> a -> a
f x u = (3.8 * x * (1 - x)) + u

-- frequency of the input sinusoid
omega :: Floating a => a
omega = pi / 10

-- generate sinusoidal control input
us :: Floating a => [a]
us = map ((0.2*) . sin . (omega*) . fromIntegral) [0..]

-- initial state
x0 :: Floating a => a
x0 = 0.0

-- compute the state trajectory
xs :: Floating a => [a]
xs = scanl f x0 us

where we used map, function composition, and an infinite list of non-negative integers to generate the sinusoidal input.

To be more precise, the program above does not quite compute the state trajectory, it merely “promises” to compute it when needed. After running the program in GHCi, we can obtain the first 20 values of the input sequence and the first 21 values of the state sequence using function take, as follows

*Main> take 20 us
[0.0,6.180339887498948e-,0.11755705045849463,
0.1618033988749895,0.1902113032590307,0.2,
0.19021130325903074,0.1618033988749895,
0.11755705045849466, 6.180339887498951e-2,
2.4492127076447546e17,-6.180339887498946e2,
-0.11755705045849461,-0.16180339887498948,
-0.1902113032590307,-0.2,-0.19021130325903074,
-0.1618033988749895,-0.11755705045849468,
-6.180339887498953e-2]
*Main> take 21 xs
[0.0,0.0,6.180339887498948e-2,0.33789525775595064,
1.0119471985345525,0.14426955372699996,
0.6691322284587664,1.031509602586003,
3.8294059838691885e-2,0.2575020247735924,
0.7883433805171414,0.6340607606653986,
0.8199019084343063,0.44356147166584237,
0.7760924326990134,0.4701259774450641,
0.7466086625502713,0.5286885334506017,
0.7850690797091344,0.5236383047578965,
0.8860732772080671]

In other words, the input and state sequences are only computed when the expressions with take are evaluated by the interpreter. We can plot these sequences in MATLAB:

Last but not least, here is the MATLAB code that generates the plot:

figure; hold on;
stem([0:1:19],u,'b');
stem([0:1:20],x,'r');
legend('input','state');
xlabel('k (time)'); ylabel('amplitude');
axis([0 21 -0.25 1.20]);


where (row) vectors $u$ and $x$ are the lists produced by GHCi.

__________

Lastly, please do note that the class of dynamical systems we have considered in this post is extremely broad. It encompasses difference equations obtained from the time-discretization of differential equations, IIR filters, finite and infinite automata, etc.

September 5, 2011

Given two finite sequences, $x$ and $y$, of length $n$, their $n$-point circular convolution can be written in matrix form [1] as follows

$\left[\begin{array}{c} z_0\\ z_1\\ z_2\\ \vdots\\ z_{n-2}\\ z_{n-1}\end{array}\right] = \left[\begin{array}{cccccc} y_0 & y_{n-1} & y_{n-2} & \ldots & y_2 & y_1\\ y_1 & y_0 & y_{n-1} & \ldots & y_3 & y_2\\ y_2 & y_1 & y_0 & \ldots & y_4 & y_3\\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ y_{n-2} & y_{n-3} & y_{n-4} & \ldots & y_0 & y_{n-1}\\ y_{n-1} & y_{n-2} & y_{n-3} & \ldots & y_1 & y_0\end{array}\right] \left[\begin{array}{c} x_0\\ x_1\\ x_2\\ \vdots\\ x_{n-2}\\ x_{n-1}\end{array}\right]$

where $z$ is also a sequence of length $n$. Note that the $n \times n$ matrix above is a circulant matrix, as each row is a circularly right-shifted version of the previous one. Each $z_k$ is obtained by taking the inner product of the $k$-th row of the matrix with the $x$ vector.

In Digital Signal Processing (DSP), we often think of finite sequences as vectors, which allows us to compute convolutions using matrix operations. Taking a more Computer Science-ish approach, one can think of finite sequences as finite lists, and compute convolutions using list operations. The matrix above can be thought of as a list of lists (where each row is a list). We know how to multiply a matrix by a vector, but how do we “multiply” a list of lists by a list?

I started teaching myself Haskell this Summer, and I am (obviously) looking for interesting problems at which to throw some functional firepower. Solutions looking for a problem. But, first, let us “begin at the beginning”…

__________

Reverse

Take another look at the matrix above and note that its last row, when viewed as a list, is the reversal of list $y$, which means that we need a function that reverses lists. Fortunately, we do not need to implement such a function, as there is the function reverse in Prelude that uses foldl and flip:

reverse :: [a] -> [a]
reverse = foldl (flip (:)) []

__________

Circular shifts

Yet once again, let us look at the matrix at the top of this post. Note that the 2nd row is a circularly right-shifted version of the 1st one, and that the 3rd row is a circularly right-shifted version of the 2nd one, et cetera. Also, note that the $(n-1)$-th row is a circularly left-shifted version of the $n$-th row, and so and so on. Thus, we need to implement functions that perform circular shifts.

The following function circularly right-shifts a list:

circShiftR :: [a] -> [a]
circShiftR [] = []
circShiftR x = last x : init x

This function merely takes the last element of the list and moves it to the beginning. We can circularly left-shift a list using the function:

circShiftL :: [a] -> [a]
circShiftL [] = []
circShiftL xs = (tail xs) ++ [head xs]

which moves the first element of a list to the end. Let us now test these functions on some simple lists using the GHCi interpreter:

*Main> circShiftR [0..9]
[9,0,1,2,3,4,5,6,7,8]
*Main> circShiftR (circShiftR [0..9])
[8,9,0,1,2,3,4,5,6,7]
*Main> (circShiftR . circShiftR) [0..9]
[8,9,0,1,2,3,4,5,6,7]
*Main> circShiftL [0..9]
[1,2,3,4,5,6,7,8,9,0]
*Main> (circShiftL . circShiftL) [0..9]
[2,3,4,5,6,7,8,9,0,1]

Note that in the 3rd and 5th inputs we composed the circular shifting functions to perform double right- and left-shifts.

__________

Iterate

Since each row of the matrix is a right-shifted version of the previous one or a left-shifted version of the next one, we can generate the matrix from its first or last rows. Putting it in terms of lists, we can generate a list of lists that represents the matrix from a single list using the iterate function in Prelude:

iterate :: (a -> a) -> a -> [a]
iterate f x =  x : iterate f (f x)

and the circular shifting functions we implemented before. To make things concrete, we can generate all four circular right-shifts of a list of length 4, as follows:

*Main> take 4 (iterate circShiftR [0..3])
[[0,1,2,3],[3,0,1,2],[2,3,0,1],[1,2,3,0]]

A word of caution is in order. Note that we take the first four lists, as

iterate f x

does generate an infinite list containing $x$, $f (x)$, $(f \circ f ) (x)$, $(f \circ f \circ f ) (x)$, et cetera. We do not need an infinite list of lists.

We now know how to generate a list of lists representing the matrix.

__________

Inner product

To obtain the circular convolution of $x$ and $y$, we multiply a matrix by a (column) vector, which consists of computing $n$ inner products. However, in this post we are thinking in terms of lists. We thus need to implement a function that computes the inner product of two (finite) lists, as follows:

innerProd :: Num a => [a] -> [a] -> a
innerProd xs ys = sum(zipWith (*) xs ys)

where we first use zipWith to obtain a list of the $x_i y_i$ products, and then use sum to compute the sum $\sum_i x_i y_i$. Let us test the inner product function:

*Main> let xs = [1..4]
*Main> let ys = [0..3]
*Main> zipWith (*) xs ys
[0,2,6,12]
*Main> sum(zipWith (*) xs ys)
20

__________

Circular convolution

We finally have all we need to compute the circular convolution.

For example, suppose we want to compute the circular convolution of two 4-point sequences, say, $x = (1,1,1,1)$ and $y = (0,1,2,3)$. Using matrix-vector multiplication, we obtain:

$\left[\begin{array}{cccc} 0 & 3 & 2 & 1\\ 1 & 0 & 3 & 2\\ 2 & 1 & 0 & 3\\ 3 & 2 & 1 & 0\end{array}\right] \left[\begin{array}{c} 1\\ 1\\ 1\\ 1\end{array}\right] = \left[\begin{array}{c} 6\\ 6\\ 6\\ 6\end{array}\right]$

Alternatively, we can compute the circular convolution by representing sequences by lists and using the functions we have implemented before:

*Main> -- define lists
*Main> let xs = [1,1,1,1]
*Main> let ys = [0,1,2,3]
*Main> -- reverse and right-shift ys
*Main> let ys' = (circShiftR . reverse) ys
*Main> ys'
[0,3,2,1]
*Main> -- compute list of lists representing the matrix
*Main> let yss = take 4 (iterate circShiftR ys')
*Main> yss
[[0,3,2,1],[1,0,3,2],[2,1,0,3],[3,2,1,0]]
*Main> -- compute inner product of xs with each list in yss
*Main> map (innerProd xs) yss
[6,6,6,6]

Note that I wrote comments on the GHCi command line in order to improve readability. We are now ready to implement the function that computes the circular convolution:

circConv :: Num a => [a] -> [a] -> [a]
circConv xs ys = map (innerProd xs) yss
where
n   = length xs
ys' = (circShiftR . reverse) ys
yss = take n (iterate circShiftR ys')

How does it work? We first take sequence $y$, reverse and right-shift it (to obtain the 1st row of the matrix), generate the remaining rows by right-shifting the previous ones, and finally compute the inner product of each row with sequence $x$ using map. Note that

innerProd xs

is a partial application of the inner product function, as we provide only the first argument. We could define a function $g$ as follows:

*Main> let g = innerProd [1,1,1,1]
*Main> :type g
g :: [Integer] -> Integer
*Main> g [0..3]
6

Note that $g$ takes a list of integers and returns its inner product with the list of four ones. Putting it all together in a .hs file, we have:

-- circular right-shift
circShiftR :: [a] -> [a]
circShiftR [] = []
circShiftR x = last x : init x

-- inner product of two lists
innerProd :: Num a => [a] -> [a] -> a
innerProd xs ys = sum(zipWith (*) xs ys)

-- circular convolution of two lists
circConv :: Num a => [a] -> [a] -> [a]
circConv xs ys = map (innerProd xs) yss
where
n   = length xs
ys' = (circShiftR . reverse) ys
yss = take n (iterate circShiftR ys')

We use several higher-order functions in this implementation: map, iterate, zipWith. We also use function composition and partial function application. A lot of beautiful ideas in only a dozen lines of code!

I am a Haskell neophyte, and I make no claims that the code above cannot be improved. If you have any constructive suggestions, I would be happy to hear them. Please use the HTML tags <pre> and </pre> to post code in the comments.

__________

Testing

Last but not least, let us carry out a couple of tests using examples from Mitra’s book [1]:

*Main> -- problem 5.2 b)
*Main> let xs = [-1,5,3,0,3]
*Main> let hs = [-2,0,5,3,-2]
*Main> circConv xs hs
[1,-1,-2,16,26]
*Main> -- problem 5.45 b)
*Main> let gs = [2,-1,3,0]
*Main> let hs = [-2,4,2,-1]
*Main> circConv gs hs
[3,7,-6,8]

It appears to be working! Please let me know if you find any bugs.

__________

References

[1] Sanjit K. Mitra, Digital Signal Processing: a computer-based approach, 3rd edition, McGraw-Hill, 2005.