Как сделать этот код более компактным и понятным?

Question

Привет всем.

Я программист на C #, в свободное время изучаю F #.Я написал следующую небольшую программу для свертки изображений в 2D.

open System

let convolve y x = 
  y |> List.map (fun ye -> x |> List.map ((*) ye))
    |> List.mapi (fun i l -> [for q in 1..i -> 0] @ l @ [for q in 1..(l.Length - i - 1) -> 0])
    |> List.reduce (fun r c -> List.zip r c |> List.map (fun (a, b) -> a + b))   

let y = [2; 3; 1; 4]
let x = [4; 1; 2; 3]
printfn "%A" (convolve y x)

Мой вопрос: является ли приведенный выше код идиоматическим F #?Можно ли сделать его более кратким?(Например, есть ли какой-нибудь более короткий способ создать заполненный список из 0 (для этого я использовал в своем коде понимание списка)).Любые изменения, которые могут улучшить его производительность?

Любая помощь будет принята с благодарностью.Спасибо.

РЕДАКТИРОВАТЬ:

Спасибо Брайан.Я не получил ваше первое предложение.Вот как выглядит мой код после применения вашего второго предложения.(Я также абстрагировал операцию заполнения списка.)

open System

let listFill howMany withWhat = [for i in 1..howMany -> withWhat]

let convolve y x = 
  y |> List.map (fun ye -> x |> List.map ((*) ye))
    |> List.mapi (fun i l -> (listFill i 0) @ l @ (listFill (l.Length - i - 1) 0))
    |> List.reduce (List.map2 (+))

let y = [2; 3; 1; 4]
let x = [4; 1; 2; 3]
printfn "%A" (convolve y x)

Что-нибудь еще можно улучшить?В ожидании новых предложений ...

Answer 1

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

Я думаю, что Брианс предложил написать генератор последовательностей, который бы сразу генерировал список, но это немного сложнее.Вам нужно будет преобразовать список в массив, а затем написать что-то вроде:

let convolve y x =  
  y |> List.map (fun ye -> x |> List.map ((*) ye) |> Array.ofList) 
    |> List.mapi (fun i l -> Array.init (2 * l.Length - 1) (fun n -> 
        if n < i || n - i >= l.Length then 0 else l.[n - i]))
    |> List.reduce (Array.map2 (+))

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

let convolve y (x:_ list) =  
  [ for i, v1 in x |> List.zip [ 0 .. x.Length - 1] ->
      [ yield! listFill i 0
        for v2 in y do yield v1 * v2
        yield! listFill (x.Length - i - 1) 0 ] ]
  |> List.reduce (List.map2 (+))

... или вы также можете объединить эти два параметра и использовать вложенное выражение последовательности (с yield! для создания нулей и списков)в лямбда-функции, которую вы передаете List.mapi:

let convolve y x =  
  y |> List.map (fun ye -> x |> List.map ((*) ye)) 
    |> List.mapi (fun i l -> 
         [ for _ in 1 .. i do yield 0
           yield! l 
           for _ in 1 .. (l.Length - i - 1) do yield 0 ])
    |> List.reduce (List.map2 (+))    

Answer 2

Идиоматическим решением будет использование массивов и циклов так же, как в C. Однако вас может заинтересовать следующее альтернативное решение, которое вместо этого использует сопоставление с образцом:

  let dot xs ys =
     Seq.map2 (*) xs ys
     |> Seq.sum

  let convolve xs ys =
     let rec loop vs xs ys zs =
        match xs, ys with
        | x::xs, ys -> loop (dot ys (x::zs) :: vs) xs ys (x::zs)
        | [], _::(_::_ as ys) -> loop (dot ys zs :: vs) [] ys zs
        | _ -> List.rev vs
     loop [] xs ys []

  convolve [2; 3; 1; 4] [4; 1; 2; 3]

Answer 3

Что касается нулей, как насчет, например,

[for q in 0..l.Length-1 -> if q=i then l else 0]

(я не проверял, чтобы убедиться, что это совершенно верно, но, надеюсь, идея ясна.) В общем, любое использование @запах кода.

Что касается общей производительности, для небольших списков это, вероятно, хорошо;для более крупных вы можете использовать Seq вместо List для некоторых промежуточных вычислений, чтобы избежать выделения как можно большего количества временных списков.

Похоже, что окончательный zip-then-карту можно заменить просто вызовом map2 , что-то вроде

... fun r c -> (r,c) ||> List.map2 (+)

или, возможно, просто

... List.map2 (+)

, но я не в компиляторе, поэтомуеще раз не проверил.

Answer 4

Еще одна вещь, которую вы могли бы сделать, это соединить первые две карты. l |> List.map f |> List.mapi g = l |> List.mapi (fun i x -> g i (f x)), поэтому, учитывая предложения Томаса и Брайана, вы можете получить что-то вроде:

let convolve y x = 
  let N = List.length x
  y
  |> List.mapi (fun i ye -> 
      [for _ in 1..i -> 0
       yield! List.map ((*) ye) x
       for _ in 1..(N-i-1) -> 0])    
  |> List.reduce (List.map2 (+))  

Answer 5

(fun ye -> x |> List.map ((*) ye))

Действительно?

Я признаю, что> довольно, но вы могли бы просто написать: (fun ye -> List.map ((*) ye) x)