I would like convolve a discrete signal with a discrete filter. The signal and filter is sequences of float in F#.
我想用离散的滤波器将离散信号卷积。信号和滤波器是f#中的浮点序列。
The only way I can figure out how to do it is with two nested for loops and a mutable array to store the result, but it does not feel very functional.
我唯一能想到的方法是用两个嵌套的for循环和一个可变数组来存储结果，但它感觉不太实用。
Here is how I would do it non-functional:
下面是我如何做非功能性的:
conv = double[len(signal) + len(filter) - 1]
for i = 1 to len(signal)
for j = 1 to len(filter)
conv[i + j] = conv[i + j] + signal(i) * filter(len(filter) - j)
4 个解决方案
#1
3
Try this function:
试试这个功能:
let convolute signal filter =
[|0 .. Array.length signal + Array.length filter - 1|] |> Array.map (fun i ->
[|0 .. i|] |> Array.sum_by (fun j -> signal.[i] * filter.[Array.length filter - (i - j) - 1]))
It's probably not the nicest function solution, but it should do the job. I doubt there exists a purely functional solution that will match the imperative one for speed however.
它可能不是最好的函数解决方案，但是它应该可以完成这项工作。然而，我怀疑是否存在一个纯粹的功能性解决方案，它将与加快速度的必要性相匹配。
Hope that helps.
希望有帮助。
Note: The function is currently untested (though I've confirmed it compiles). Let me know if it doesn't quite do what it should. Also, observe that the i and j variables do not refer to the same things as is your original post.
注意:这个函数目前没有经过测试(尽管我已经确认它是编译的)。如果它不像它应该做的那样，请告诉我。另外，请注意，i和j变量并不表示与原来的post相同的内容。
#2
5
I don't know F#, but I'll post some Haskell and hopefully it will be close enough to use. (I only have VS 2005 and an ancient version of F#, so I think it would be more confusing to post something that works on my machine)
我不知道f#，但我会发布一些Haskell，希望它足够接近使用。(我只有VS 2005和f#的一个古老版本，所以我认为在我的机器上发布一些有用的东西会更令人困惑)
Let me start by posting a Python implementation of your pseudocode to make sure I'm getting the right answer:
让我先发布一个Python实现的伪代码，以确保我得到了正确的答案:
def convolve(signal, filter):
conv = [0 for _ in range(len(signal) + len(filter) - 1)]
for i in range(len(signal)):
for j in range(len(filter)):
conv[i + j] += signal[i] * filter[-j-1]
return conv
Now convolve([1,1,1], [1,2,3]) gives [3, 5, 6, 3, 1]. If this is wrong, please tell me.
现在卷积((1 1 1)[1,2,3])给(3、5、6、3、1]。如果这是错误的，请告诉我。
The first thing we can do is turn the inner loop into a zipWith; we're essentially adding a series of rows in a special way, in the example above: [[3,2,1], [3,2,1], [3,2,1]]. To generate each row, we'll zip each i in the signal with the reversed filter:
我们能做的第一件事就是把内环路变成一个拉链;我们实际上是用一种特殊的方式增加了一系列的行，在上面的例子中:[[3,2,1]，[3,2,1]，[3,2,1]]。为了生成每行，我们将用反向过滤器将每个i压缩到信号中:
makeRow filter i = zipWith (*) (repeat i) (reverse filter)
(Note: according to a quick google, zipWith is map2 in F#. You might have to use a list comprehension instead of repeat) Now:
(注意:根据快速谷歌，zipWith是f#中的map2。你可能需要使用列表理解而不是重复)现在:
makeRow [1,2,3] 1
=> [3,2,1]
makeRow [1,2,3] 2
=> [6,4,2]
To get this for all i, we need to map over signal:
为了得到这个，我们需要映射一个信号:
map (makeRow filter) signal
=> [[3,2,1], [3,2,1], [3,2,1]]
Good. Now we just need a way to combine the rows properly. We can do this by noticing that combining is adding the new row to the existing array, except for the first element, which is stuck on front. For example:
好。现在我们需要一种正确组合行的方法。我们可以这样做，注意组合是将新行添加到现有的数组中，除了第一个元素，它被卡在前面。例如:
[[3,2,1], [6,4,2]] = 3 : [2 + 6, 1 + 4] ++ [2]
// or in F#
[[3; 2; 1]; [6; 4; 2]] = 3 :: [2 + 6; 1 + 4] @ [2]
So we just need to write some code that does this in the general case:
所以我们只需要写一些在一般情况下的代码:
combine (front:combinable) rest =
let (combinable',previous) = splitAt (length combinable) rest in
front : zipWith (+) combinable combinable' ++ previous
Now that we have a way to generate all the rows and a way to combine a new row with an existing array, all we have to do is stick the two together with a fold:
现在我们有了一种方法来生成所有的行，以及将新行与现有数组组合在一起的方法，我们所要做的就是将两者结合起来:
convolve signal filter = foldr1 combine (map (makeRow filter) signal)
convolve [1,1,1] [1,2,3]
=> [3,5,6,3,1]
So that's a functional version. I think it's reasonably clear, as long as you understand foldr and zipWith. But it's at least as long as the imperative version and like other commenters said, probably less efficient in F#. Here's the whole thing in one place.
这是一个功能版本。我认为这是相当清楚的，只要你理解foldr和zipWith。但它至少和命令式的版本一样长，就像其他评论者说的那样，在f#中可能效率不高。这是一个地方的整体。
makeRow filter i = zipWith (*) (repeat i) (reverse filter)
combine (front:combinable) rest =
front : zipWith (+) combinable combinable' ++ previous
where (combinable',previous) = splitAt (length combinable) rest
convolve signal filter = foldr1 combine (map (makeRow filter) signal)
Edit:
编辑:
As promised, here is an F# version. This was written using a seriously ancient version (1.9.2.9) on VS2005, so be careful. Also I couldn't find splitAt in the standard library, but then I don't know F# that well.
正如所承诺的，这里有一个f#版本。这是在VS2005上使用一个非常古老的版本(1.9.2.9)编写的，所以要小心。我在标准库中也找不到splitAt，但是我不知道f#。
open List
let gen value = map (fun _ -> value)
let splitAt n l =
let rec splitter n l acc =
match n,l with
| 0,_ -> rev acc,l
| _,[] -> rev acc,[]
| n,x::xs -> splitter (n - 1) xs (x :: acc)
splitter n l []
let makeRow filter i = map2 ( * ) (gen i filter) (rev filter)
let combine (front::combinable) rest =
let combinable',previous = splitAt (length combinable) rest
front :: map2 (+) combinable combinable' @ previous
let convolve signal filter =
fold1_right combine (map (makeRow filter) signal)
#3
1
Indeed, you generally want to avoid loops (plain, nested, whatever) and anything mutable in functional programming.
实际上，您通常希望避免循环(简单的、嵌套的、随便的)和函数编程中的任何可变的东西。
There happens to be a very simple solution in F# (and probably almost every other functional language):
f#中有一个非常简单的解决方案(可能几乎所有其他函数语言):
let convolution = Seq.zip seq1 seq2
The zip function simply combines the two sequences into one of pairs containing the element from seq1 and the element from seq2. As a note, there also exist similar zip functions for the List and Array modules, as well as variants for combining three lists into triples (zip3). If you want tom ore generally zip (or "convolute") n lists into a list of n-tuples, then you'll need to write your own function, but it's pretty straightforward.
zip函数简单地将两个序列组合成一个包含来自seq1的元素和来自seq2的元素的组合。值得注意的是，列表和数组模块中也有类似的zip函数，以及将三个列表组合成三元组的变体(zip3)。如果您想让tom ore通常将n个列表压缩到一个n元组列表中，那么您需要编写自己的函数，但这很简单。
(I've been going by this description of convolution by the way - tell me if you mean something else.)
(顺便说一下，我一直在用这个卷积的描述——告诉我你是不是在说别的什么。)
#4
1
In principle, it should be possible to use the (Fast) Fourier Transform, or the related (Discrete) Cosine Transform, to calculate the convolution of two functions reasonably efficiently. You calculate the FFT for both functions, multiply them, and apply the inverse FFT on the result.
原则上，应该可以使用(快速)傅里叶变换，或相关的(离散的)余弦变换，来计算两个函数的卷积。你计算两个函数的FFT，乘以它们，然后在结果上应用逆FFT。
数学背景
That's the theory. In practice you'd probably best find a math library that implements it for you.
理论上是这样的。在实践中，您可能最好找到一个为您实现它的数学库。
#1
3
Try this function:
试试这个功能:
let convolute signal filter =
[|0 .. Array.length signal + Array.length filter - 1|] |> Array.map (fun i ->
[|0 .. i|] |> Array.sum_by (fun j -> signal.[i] * filter.[Array.length filter - (i - j) - 1]))
It's probably not the nicest function solution, but it should do the job. I doubt there exists a purely functional solution that will match the imperative one for speed however.
它可能不是最好的函数解决方案，但是它应该可以完成这项工作。然而，我怀疑是否存在一个纯粹的功能性解决方案，它将与加快速度的必要性相匹配。
Hope that helps.
希望有帮助。
Note: The function is currently untested (though I've confirmed it compiles). Let me know if it doesn't quite do what it should. Also, observe that the i and j variables do not refer to the same things as is your original post.
注意:这个函数目前没有经过测试(尽管我已经确认它是编译的)。如果它不像它应该做的那样，请告诉我。另外，请注意，i和j变量并不表示与原来的post相同的内容。
#2
5
I don't know F#, but I'll post some Haskell and hopefully it will be close enough to use. (I only have VS 2005 and an ancient version of F#, so I think it would be more confusing to post something that works on my machine)
我不知道f#，但我会发布一些Haskell，希望它足够接近使用。(我只有VS 2005和f#的一个古老版本，所以我认为在我的机器上发布一些有用的东西会更令人困惑)
Let me start by posting a Python implementation of your pseudocode to make sure I'm getting the right answer:
让我先发布一个Python实现的伪代码，以确保我得到了正确的答案:
def convolve(signal, filter):
conv = [0 for _ in range(len(signal) + len(filter) - 1)]
for i in range(len(signal)):
for j in range(len(filter)):
conv[i + j] += signal[i] * filter[-j-1]
return conv
Now convolve([1,1,1], [1,2,3]) gives [3, 5, 6, 3, 1]. If this is wrong, please tell me.
现在卷积((1 1 1)[1,2,3])给(3、5、6、3、1]。如果这是错误的，请告诉我。
The first thing we can do is turn the inner loop into a zipWith; we're essentially adding a series of rows in a special way, in the example above: [[3,2,1], [3,2,1], [3,2,1]]. To generate each row, we'll zip each i in the signal with the reversed filter:
我们能做的第一件事就是把内环路变成一个拉链;我们实际上是用一种特殊的方式增加了一系列的行，在上面的例子中:[[3,2,1]，[3,2,1]，[3,2,1]]。为了生成每行，我们将用反向过滤器将每个i压缩到信号中:
makeRow filter i = zipWith (*) (repeat i) (reverse filter)
(Note: according to a quick google, zipWith is map2 in F#. You might have to use a list comprehension instead of repeat) Now:
(注意:根据快速谷歌，zipWith是f#中的map2。你可能需要使用列表理解而不是重复)现在:
makeRow [1,2,3] 1
=> [3,2,1]
makeRow [1,2,3] 2
=> [6,4,2]
To get this for all i, we need to map over signal:
为了得到这个，我们需要映射一个信号:
map (makeRow filter) signal
=> [[3,2,1], [3,2,1], [3,2,1]]
Good. Now we just need a way to combine the rows properly. We can do this by noticing that combining is adding the new row to the existing array, except for the first element, which is stuck on front. For example:
好。现在我们需要一种正确组合行的方法。我们可以这样做，注意组合是将新行添加到现有的数组中，除了第一个元素，它被卡在前面。例如:
[[3,2,1], [6,4,2]] = 3 : [2 + 6, 1 + 4] ++ [2]
// or in F#
[[3; 2; 1]; [6; 4; 2]] = 3 :: [2 + 6; 1 + 4] @ [2]
So we just need to write some code that does this in the general case:
所以我们只需要写一些在一般情况下的代码:
combine (front:combinable) rest =
let (combinable',previous) = splitAt (length combinable) rest in
front : zipWith (+) combinable combinable' ++ previous
Now that we have a way to generate all the rows and a way to combine a new row with an existing array, all we have to do is stick the two together with a fold:
现在我们有了一种方法来生成所有的行，以及将新行与现有数组组合在一起的方法，我们所要做的就是将两者结合起来:
convolve signal filter = foldr1 combine (map (makeRow filter) signal)
convolve [1,1,1] [1,2,3]
=> [3,5,6,3,1]
So that's a functional version. I think it's reasonably clear, as long as you understand foldr and zipWith. But it's at least as long as the imperative version and like other commenters said, probably less efficient in F#. Here's the whole thing in one place.
这是一个功能版本。我认为这是相当清楚的，只要你理解foldr和zipWith。但它至少和命令式的版本一样长，就像其他评论者说的那样，在f#中可能效率不高。这是一个地方的整体。
makeRow filter i = zipWith (*) (repeat i) (reverse filter)
combine (front:combinable) rest =
front : zipWith (+) combinable combinable' ++ previous
where (combinable',previous) = splitAt (length combinable) rest
convolve signal filter = foldr1 combine (map (makeRow filter) signal)
Edit:
编辑:
As promised, here is an F# version. This was written using a seriously ancient version (1.9.2.9) on VS2005, so be careful. Also I couldn't find splitAt in the standard library, but then I don't know F# that well.
正如所承诺的，这里有一个f#版本。这是在VS2005上使用一个非常古老的版本(1.9.2.9)编写的，所以要小心。我在标准库中也找不到splitAt，但是我不知道f#。
open List
let gen value = map (fun _ -> value)
let splitAt n l =
let rec splitter n l acc =
match n,l with
| 0,_ -> rev acc,l
| _,[] -> rev acc,[]
| n,x::xs -> splitter (n - 1) xs (x :: acc)
splitter n l []
let makeRow filter i = map2 ( * ) (gen i filter) (rev filter)
let combine (front::combinable) rest =
let combinable',previous = splitAt (length combinable) rest
front :: map2 (+) combinable combinable' @ previous
let convolve signal filter =
fold1_right combine (map (makeRow filter) signal)
#3
1
Indeed, you generally want to avoid loops (plain, nested, whatever) and anything mutable in functional programming.
实际上，您通常希望避免循环(简单的、嵌套的、随便的)和函数编程中的任何可变的东西。
There happens to be a very simple solution in F# (and probably almost every other functional language):
f#中有一个非常简单的解决方案(可能几乎所有其他函数语言):
let convolution = Seq.zip seq1 seq2
The zip function simply combines the two sequences into one of pairs containing the element from seq1 and the element from seq2. As a note, there also exist similar zip functions for the List and Array modules, as well as variants for combining three lists into triples (zip3). If you want tom ore generally zip (or "convolute") n lists into a list of n-tuples, then you'll need to write your own function, but it's pretty straightforward.
zip函数简单地将两个序列组合成一个包含来自seq1的元素和来自seq2的元素的组合。值得注意的是，列表和数组模块中也有类似的zip函数，以及将三个列表组合成三元组的变体(zip3)。如果您想让tom ore通常将n个列表压缩到一个n元组列表中，那么您需要编写自己的函数，但这很简单。
(I've been going by this description of convolution by the way - tell me if you mean something else.)
(顺便说一下，我一直在用这个卷积的描述——告诉我你是不是在说别的什么。)
#4
1
In principle, it should be possible to use the (Fast) Fourier Transform, or the related (Discrete) Cosine Transform, to calculate the convolution of two functions reasonably efficiently. You calculate the FFT for both functions, multiply them, and apply the inverse FFT on the result.
原则上，应该可以使用(快速)傅里叶变换，或相关的(离散的)余弦变换，来计算两个函数的卷积。你计算两个函数的FFT，乘以它们，然后在结果上应用逆FFT。
数学背景
That's the theory. In practice you'd probably best find a math library that implements it for you.
理论上是这样的。在实践中，您可能最好找到一个为您实现它的数学库。