Как мне сделать свертку в 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)

(Примечание: согласно быстрому Google, 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)

Edit:

Как и было обещано, вот версия F #. Это было написано с использованием очень древней версии (1.9.2.9) на VS2005, поэтому будьте осторожны. Также я не смог найти 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)

Answer 2

Попробуйте эту функцию:

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

Это, вероятно, не самое хорошее функциональное решение, но оно должно делать свою работу. Я сомневаюсь, что существует чисто функциональное решение, которое будет соответствовать императивному по скорости.

Надеюсь, это поможет.

Примечание: функция в настоящее время не проверена (хотя я подтвердил, что она компилируется). Дайте мне знать, если он не совсем делает то, что должен. Также обратите внимание, что переменные i и j не относятся к тем же вещам, что и ваш исходный пост.

Answer 3

В принципе, должно быть возможно использовать (быстрое) преобразование Фурье или связанное с ним (дискретное) косинусное преобразование для достаточно эффективного вычисления свертки двух функций. Вы вычисляете БПФ для обеих функций, умножаете их и применяете обратное БПФ к результату.

математический фон

Это теория. На практике вам, вероятно, лучше всего найти математическую библиотеку, которая реализует ее для вас.

Answer 4

Действительно, вы обычно хотите избегать циклов (простых, вложенных и т. Д.) И всего, что может изменяться в функциональном программировании.

В F # есть очень простое решение (и, возможно, почти любой другой функциональный язык):

let convolution = Seq.zip seq1 seq2

Функция zip просто объединяет две последовательности в одну из пар, содержащих элемент из seq1 и элемент из seq2. Как примечание, существуют также аналогичные функции zip для модулей List и Array, а также варианты объединения трех списков в тройки (zip3). Если вы хотите, чтобы tom ore, как правило, упаковывали n (или «свернули») n списков в список из n-кортежей, то вам нужно написать собственную функцию, но это довольно просто.

(Я, кстати, подхожу к этому описанию свертки, кстати - скажи мне, если ты имеешь в виду что-то еще.)