كيف أفعل الإلتواء في F #؟

Question

وأود لف إشارة منفصلة مع فلتر منفصلة. إشارة والمرشح هو تسلسل تطفو في F #.

والطريقة الوحيدة التي يمكنني معرفة كيفية القيام بذلك هو مع اثنين من متداخل للحلقات ومجموعة قابلة للتغيير لتخزين نتيجة، لكنه لا يشعر ظيفية للغاية.

وهنا هو كيف لي أن تفعل ذلك غير وظيفية:

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

جرب هذه الوظيفة:

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 2

وأنا لا أعرف F #، لكن أنا ما بعد بعض هاسكل واتمنى ان تكون قريبة بما فيه الكفاية لاستخدامها. (وليس لدي سوى VS 2005 ونسخة قديمة من F #، لذلك أعتقد أنه سيكون أكثر مربكة للنشر شيء يعمل على الجهاز الخاص بي)

واسمحوا لي أن أبدأ عن طريق نشر تنفيذ بيثون من شبة الكود الخاص بك للتأكد من انني اتلقى الجواب الصحيح:

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. وقد كتب ذلك باستخدام نسخة قديمة بجدية (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 3

والواقع، تريد عموما لتجنب التكرار (عادي، متداخلة، أيا كان) وأي شيء قابلة للتغيير في البرمجة الوظيفية.

وهناك صادف أن يكون حلا بسيطا جدا في F # (وكل لغة وظيفية أخرى ربما تقريبا):

let convolution = Seq.zip seq1 seq2

وظيفة zip ببساطة يجمع بين متواليات اثنين الى واحد من أزواج التي تحتوي على عنصر من seq1 وعنصر من seq2. كملاحظة، توجد أيضا وظائف البريدي مماثلة للوحدات List وArray، فضلا عن المتغيرات للجمع بين ثلاث قوائم في يتضاعف ثلاث مرات (zip3). إذا كنت تريد خام توم الرمز البريدي عموما (أو "ملفوف") ن القوائم في قائمة ن الصفوف، ثم ستحتاج لكتابة وظيفة الخاصة بك، ولكن انها واضحة جدا.

و(أنا مستمر من قبل هذا الوصف من التفاف بالمناسبة - قل لي إذا كنت تعني شيئا آخر)

Answer 4

في المبدأ، ينبغي أن يكون من الممكن استخدام (السريع) تحويل فورييه، أو ذات الصلة (المتقطعة) جيب التمام تحويل، لحساب الإلتواء وظيفتين بكفاءة معقولة. على حساب الاتحاد الفرنسي للتنس على حد سواء وظائف، اضرب لهم، وتطبيق الاتحاد الفرنسي للتنس معكوس على النتيجة.

خلفية رياضية

وهذه هي النظرية. في الممارسة العملية كنت ربما أفضل العثور على مكتبة الرياضيات التي تطبق لانها لكم.