Transformation of a list of positions to a 2D array of positions using functional programming (F#)

Question

How would you make the folowing code functional with the same speed? In general, as an input I have a list of objects containing position coordinates and other stuff and I need to create a 2D array consisting those objects.

let m = Matrix.Generic.create 6 6 []
let pos = [(1.3,4.3); (5.6,5.4); (1.5,4.8)]  
pos |> List.iter (fun (pz,py) ->
  let z, y = int pz, int py
  m.[z,y] <- (pz,py) :: m.[z,y]
)

It could be probably done in this way:

let pos = [(1.3,4.3); (5.6,5.4); (1.5,4.8)]
Matrix.generic.init 6 6 (fun z y ->
  pos |> List.fold (fun state (pz,py) ->
    let iz, iy = int pz, int py
    if iz = z && iy = y then (pz,py) :: state else state
  ) []
)

But I guess it would be much slower because it loops through the whole matrix times the list versus the former list iteration...

PS: the code might be wrong as I do not have F# on this computer to check it.

Answer 1

It depends on the definition of "functional". I would say that a "functional" function means that it always returns the same result for the same parameters and that it doesn't modify any global state (or the value of parameters if they are mutable). I think this is a sensible definition for F#, but it also means that there is nothing "dis-functional" with using mutation locally.

In my point of view, the following function is "functional", because it creates and returns a new matrix instead of modifying an existing one, but of course, the implementation of the function uses mutation.

let performStep m =
  let res = Matrix.Generic.create 6 6 [] 
  let pos = [(1.3,4.3); (5.6,5.4); (1.5,4.8)]   
  for pz, py in pos do
    let z, y = int pz, int py 
    res.[z,y] <- (pz,py) :: m.[z,y] 
  res

Mutation-free version: Now, if you wanted to make the implementation fully functional, then I would start by creating a matrix that contains Some(pz, py) in the places where you want to add the new list element to the element of the matrix and None in all other places. I guess this could be done by initializing a sparse matrix. Something like this:

let sp = pos |> List.map (fun (pz, py) -> int pz, int py, (pz, py)) 
let elementsToAdd = Matrix.Generic.initSparse 6 6 sp

Then you should be able to combine the original matrix m with the newly created elementsToAdd. This can be certainly done using init (however, having something like map2 would be maybe nicer):

let res = Matrix.init 6 6 (fun i j -> 
  match elementsToAdd.[i, j], m.[i, j] with
  | Some(n), res -> n::res
  | _, res -> res )

There is still quite likely some mutation hidden in the F# library functions (such as init and initSparse), but at least it shows one way to implement the operation using more primitive operations.

EDIT: This will work only if you need to add at most single element to each matrix cell. If you wanted to add multiple elements, you'd have to group them first (e.g. using Seq.groupBy)

Answer 2

Why do you want to do it functionally? The Matrix type is designed to be mutated, so the way you're doing it now looks good to me.

If you really want to do it functionally, though, here's what I'd do:

let pos = [(1.3,4.3); (5.6,5.4); (1.5,4.8)]  
let addValue m k v = 
  if Map.containsKey k m then
    Map.add k (v::m.[k]) m
  else
    Map.add k [v] m
let map = 
  pos 
  |> List.map (fun (x,y) -> (int x, int y),(x,y)) 
  |> List.fold (fun m (p,q) -> addValue m p q) Map.empty
let m = Matrix.Generic.init 6 6 (fun x y -> if (Map.containsKey (x,y) map) then map.[x,y] else [])

This runs through the list once, creating an immutable map from indices to lists of points. Then, we initialize each entry in the matrix, doing a single map lookup for each entry. This should take total time O(M + N log N) where M and N are the number of entries in your matrix and list respectively. I believe that your original solution using mutation takes O(M+N) time and your revised solution takes O(M*N) time.

Answer 3

You can do something like this:

[1.3, 4.3; 5.6, 5.4; 1.5, 4.8]
|> Seq.groupBy (fun (pz, py) -> int pz, int py)
|> Seq.map (fun ((pz, py), ps) -> pz, py, ps)
|> Matrix.Generic.initSparse 6 6

But in your question you said:

How would you make the folowing code functional with the same speed?

And in a later comment you said:

Well, I try to avoid mutability so that the code would be simple to paralelize in the future

I am afraid this is a triumph of hope over reality. Functional code generally has poor absolute performance and scales badly when parallelized. Given the huge amount of allocation this code is doing, you're not likely to see any performance gain from parallelism at all.