How to make this code more compact and idiomatic?

Question

Hullo all.

I am a C# programmer, exploring F# in my free time. I have written the following little program for image convolution in 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)

My question is: Is the above code an idiomatic F#? Can it be made more concise? (e.g. Is there some shorter way to generate a filled list of 0's (I have used list comprehension in my code for this purpose)). Any changes that can improve its performance?

Any help would be greatly appreciated. Thanks.

EDIT:

Thanks Brian. I didn't get your first suggestion. Here's how my code looks after applying your second suggestion. (I also abstracted out the list-fill operation.)

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)

Anything else can be improved? Awaiting more suggestions...

Answer 1

Regarding the zeroes, how about e.g.

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

(I haven't tested to verify that is exactly right, but hopefully the idea is clear.) In general, any use of @ is a code smell.

Regarding overall performance, for small lists this is probably fine; for larger ones, you might consider using Seq rather than List for some of the intermediate computations, to avoid allocating as many temporary lists along the way.

It looks like maybe the final zip-then-map could be replaced by just a call to map2, something like

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

or possibly even just

... List.map2 (+)

but I'm away from a compiler so haven't double-checked it.

Answer 2

As Brian mentioned, the use of @ is generally problematic, because the operator cannot be efficiently 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 the list at once, but that's a bit more complicated. You'd have to convert the list to array and then write something like:

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

In general, if performance is an important concern, then you'll probably need to use arrays anyway (because this kind of problem can be best solved by accessing elements by index). Using arrays is a bit more difficult (you need to get the indexing right), but perfectly fine approach in F#.

Anyway, if you want to write this using lists, then here ara some options. You could use sequence expressions everywhere, which would 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 options and use a nested sequence expression (with yield! to generate zeros and lists) in the lambda function that you're passing to 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 3

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

Really ?

I'll admit |> is pretty, but you could just wrote : (fun ye -> List.map ((*) ye) x)

Answer 4

Another thing that you could do is fuse the first two maps. l |> List.map f |> List.mapi g = l |> List.mapi (fun i x -> g i (f x)), so incorporating Tomas and Brian's suggestions, you can get something like:

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

The idiomatic solution would be to use arrays and loops just as you would in C. However, you may be interested in the following alternative solution that 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]