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.