CODEWITHSUNDEEP
listf#functional-programmingidioms
Terence Lewis
Terence Lewis

Reputation: 914

Idiomatic way to "merge" multiple lists of the same length in F#?

I have a number of lists - each instance of which contains 9 floating point numbers. What I effectively need to do is produce one new list that takes the first element from each of my lists and adds them together as my first element, then add the second element from each list as my second element, etc.

So effectively, if my data looks something like this:

List1 = [a1; b1; c1; d1; e1; f1; g1; h1; i1]
List2 = [a2; b2; c2; d2; e2; f2; g2; h2; i2]
...
Listn = [an; bn; cn; dn; en; fn; gn; hn; in]

Then I need to produce a new list Listx such that

Listx = [a1 + a2 + ... + an; b1 + b2 + ... + bn; ... ]

The number of lists I will be merging will vary (sometimes I may only have a single list of 9 numbers, and sometimes more than 100 lists, always 9 elements long), so I was wondering if anybody's got any advice on a nice idiomatic way of doing this?

I did have a look at this question and this one but both appear to advocate an intermediate step of indexing my elements first and then using groupby. This bugs me because a) I get the feeling there might be a more elegant solution for my particular case and b) performance may be an issue later - I don't want to optimize prematurely, but I also don't want to shoot myself in the foot.

Upvotes: 5

Views: 535

Answers (5)

bklaric
bklaric

Reputation: 477

Here's an alternative one liner with default values when the list of lists is empty:

let sumVertically length = List.fold (List.map2 (+)) (List.replicate length 0)

//usage
//stolen from pad's answer
let listOfLists = List.init 1000 (fun i -> [i+1..i+9])
sumVertically 9 listOfLists

Upvotes: 0

pad
pad

Reputation: 41290

Here is a solution which works on a list of lists with the same length:

let mapN f = function
   | []  -> []
   | xss -> List.reduce (List.map2 f) xss

let inline merge xss = mapN (+) xss

// Usage
let yss = List.init 1000 (fun i -> [i+1..i+9])
let ys = merge yss

Upvotes: 7

missingfaktor
missingfaktor

Reputation: 92026

// Shamelessly stolen from:
// http://hackage.haskell.org/packages/archive/base/latest/doc/html/src/Data-List.html#transpose
let rec transpose = function
  | [] -> []
  | ([] :: xss) -> transpose xss
  | ((x :: xs) :: xss) -> (x :: List.map List.head xss) :: transpose (xs :: List.map List.tail xss)

let fuse = transpose >> List.map List.sum

printfn "%A" (fuse [[3; 4]; [1; 90]; [34; 89]]) // prints [38; 183]

Upvotes: 1

J D
J D

Reputation: 48687

I'd go via something easier like a matrix:

let merge xss =
  let m = matrix xss
  List.map (m.Column >> Seq.sum) [0..m.NumCols-1]

Upvotes: 2

ildjarn
ildjarn

Reputation: 62975

Here's one approach:

let merge lists =
  let rec impl acc lists =
    match List.head lists with
    | [] -> List.rev acc
    | _  -> let acc' = (lists |> List.map List.head |> List.reduce (+))::acc
            let lists' = List.map List.tail lists
            impl acc' lists'
  impl [] lists

Some notes:

  • List.reduce (+) is used instead of List.sum or List.sumBy because the latter only work for numeric types whereas (+) can work for e.g. string.

  • merge is deduced to be of type int list list -> int list rather than being generic due to subtleties of the way operator + works. If you only need this to work for a single type, and that type is not int (e.g. float), then adding a type annotation to merge will be sufficient:

    let merge (lists:float list list) =

  • merge can be marked inline and then will work for any type that supports operator +, but this will lead to lots of bloat in your IL if there are more than one or two call-sites. If you have multiple types that need to work with merge, and all are known beforehand, then a good workaround here is to make merge inline (and possibly private) then define different type-specific functions that are implemented in terms of the generic merge:

    let inline merge lists =
  let rec impl acc lists =
    match List.head lists with
    | [] -> List.rev acc
    | _  -> let acc' = (lists |> List.map List.head |> List.reduce (+))::acc
            let lists' = List.map List.tail lists
            impl acc' lists'
  impl [] lists

let mergeInts (lists:int list list) = merge lists
let mergeFloats (lists:float list list) = merge lists
let mergeStrings (lists:string list list) = merge lists

    If you then only call the type-specific merges, the IL bloat should be negligible.

  • Lastly, if performance is really a concern, then use arrays rather than lists.

Upvotes: 1

Related Questions