我如何在F#中进行卷积？

Question

我想用离散滤波器对离散信号进行卷积.信号和滤波器是F#中的浮点序列.

我可以弄清楚如何做的唯一方法是使用两个嵌套的for循环和一个可变数组来存储结果,但它感觉不是很有用.

这是我如何做到非功能性:

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) 

Answer 1

我不知道F#,但我会发布一些Haskell,希望它足够接近使用.(我只有VS 2005和F#的古老版本,所以我认为在我的机器上发布可以使用的东西会更加混乱)

让我首先发布您的伪代码的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

现在convolve([1,1,1], [1,2,3])给出[3, 5, 6, 3, 1].如果这是错的,请告诉我.

我们能做的第一件事就是将内循环变成一个zipWith; 我们实际上是以一种特殊的方式添加一系列行,在上面的例子中:[[3,2,1], [3,2,1], [3,2,1]].要生成的每一行,我们将压缩每个i在signal与反滤:

makeRow filter i = zipWith (*) (repeat i) (reverse filter)

(注:根据快速谷歌,zipWith是map2在F#中,您可能需要使用列表理解来代替.repeat)现在:

makeRow [1,2,3] 1
=> [3,2,1]
makeRow [1,2,3] 2
=> [6,4,2]

为了实现这一目标i,我们需要映射信号:

map (makeRow filter) signal
=> [[3,2,1], [3,2,1], [3,2,1]]

好.现在我们只需要一种正确组合行的方法.我们可以通过注意组合将新行添加到现有数组来实现这一点,除了第一个元素,它被卡在前面.例如:

[[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]

所以我们只需要编写一些在一般情况下执行此操作的代码:

combine (front:combinable) rest =
    let (combinable',previous) = splitAt (length combinable) rest in
    front : zipWith (+) combinable combinable' ++ previous

现在我们有了生成所有行的方法以及将新行与现有数组相结合的方法,我们所要做的就是将两者放在一起并用折叠:

convolve signal filter = foldr1 combine (map (makeRow filter) signal)

convolve [1,1,1] [1,2,3]
=> [3,5,6,3,1]

这是一个功能版本.我认为只要你理解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)

编辑:

正如所承诺的,这是一个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)