How to make this code more compact and idiomatic?

Question

Hullo is everything.

I am a C # programmer, learning F # in my free time. I wrote the following small program for convolution of images in 2D.

open System let convolve yx = y |> List.map (fun ye -> x |> List.map ((*) ye)) |> List.mapi (fun il -> [for q in 1..i -> 0] @ l @ [for q in 1..(l.Length - i - 1) -> 0]) |> List.reduce (fun rc -> List.zip rc |> List.map (fun (a, b) -> a + b)) let y = [2; 3; 1; 4] let x = [4; 1; 2; 3] printfn "%A" (convolve yx) 

My question is: Is the above code idiomatic F #? Is it possible to make it more concise? (for example, is there a shorter way to generate a populated list of 0 (I used understanding in my code for this purpose)). Any changes that could improve its performance?

Any help would be greatly appreciated. Thanks.

EDIT:

Thanks Brian. I did not receive your first offer. This is what my code looks like after applying the second sentence. (I also abstracted the operation of populating the list.)

 open System let listFill howMany withWhat = [for i in 1..howMany -> withWhat] let convolve yx = y |> List.map (fun ye -> x |> List.map ((*) ye)) |> List.mapi (fun il -> (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 yx) 

Can anything else be improved? Waiting for more offers ...

Answer 1

As Brian noted, using @ usually problematic because an operator cannot be effectively implemented for (simple) functional lists — it needs to copy the entire first list.

I think Brians' suggestion was to write a sequence generator that would generate a list right away, but it's a little more complicated. You will need to convert the list to an array and then write something like:

 let convolve yx = y |> List.map (fun ye -> x |> List.map ((*) ye) |> Array.ofList) |> List.mapi (fun il -> 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 (+)) 

In general, if performance is an important issue, then you will probably have to use arrays anyway (because this problem can be better solved by accessing items by index). Using arrays is a bit more complicated (you need to index correctly), but is great for F #.

In any case, if you want to write this using lists, then there are some options. You can use sequence expressions everywhere that look like this:

 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 (+)) 

... or you can also combine the two parameters and use the expression of the nested sequence (with yield! to generate zeros and lists) in the lambda function that you switch to List.mapi :

 let convolve yx = y |> List.map (fun ye -> x |> List.map ((*) ye)) |> List.mapi (fun il -> [ 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

The idiomatic solution would be to use arrays and loops in the same way as in C. However, you might be interested in the following alternative solution, which uses pattern matching instead:

  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

As for zeros, how about for example

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

(I have not tested to verify that this is accurate, but I hope the idea is clear.) In general, any use of @ is a smell of code.

Regarding overall performance, for small lists this is probably good; for larger ones, you can use Seq instead of List for some intermediate calculations to avoid allocating as many temporary lists in the path.

It seems that the last zip-then-map can be replaced simply by calling map2 , something like

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

or maybe even just

 ... List.map2 (+) 

but I am far from the compiler, so I have not checked it twice.

Answer 4

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

Really?

I acknowledge | > pretty, but you could just write: (fun ye -> List.map ((*) ye) x)

Answer 5

Another thing you could do is fuse the first two cards. l |> List.map f |> List.mapi g = l |> List.mapi (fun ix -> gi (fx)) , therefore, given the suggestions of Thomas and Brian, you can get something like:

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