Sunday, 6 May 2012

Convolve two lists


The idiomatic solution would be to use arrays and loops just as you would in C. However, the following function uses pattern matching and recursion to convolve two lists:
  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]

No comments: