[Haskell-cafe] Convolution

[Henning Thielemann]

On Fri, 7 Nov 2008, Andrew Coppin wrote:

> A simple and straight-forward way to define the DSP operations of correlation 
> and convolution is as follows:
>
> correlate1 :: [Double] -> [Double] -> Double
> correlate1 ks = sum . zipWith (*) ks
>
> correlate :: [Double] -> [Double] -> [Double]
> correlate ks [] = []
> correlate ks xs = correlate1 ks xs : correlate ks (tail xs)
>
> convolute :: [Double] -> [Double] -> [Double]
> convolute ks = correlate (reverse ks)

I think the verb is 'convolve'.

> This very simple code work - and actually works quite well. It has the nice 
> property of generating output from input lazily, as it is demanded.

If ks is infinite it will not work. I have an implementation that works, 
but it computes something little different, see 'mul' in:
    http://darcs.haskell.org/htam/src/Polynomial.hs

> If the correlate function could be altered to use Prelude list functions 
> only, I would think the above code works quite well with stream fusion 
> too. (Presumably you could do this using "inits" or something?)

You mean 'tails' ? Would be rather straight-forward.