Merge two sorted lists by a key

Merges two sorted lists by a key.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17:

// Example: mergeBy (fun (key,_)->key) [("a", 1); ("c", 2)] [("c", 2); ("d", 3)];;
// val it : ((string * int) option * (string * int) option) list =
// [(Some ("a", 1), None); (Some ("c", 2), Some ("c", 2)); (None, Some ("d", 3))]

let mergeBy keyselector ls rs = 
    let rec aux ls rs acc =
        match ls, rs with
        | [], [] -> acc
        | l::ls', [] -> aux ls' [] ((Some l, None)::acc)
        | [], r::rs' -> aux [] rs' ((None, Some r)::acc)
        | l::ls', r::rs' -> 
            match compare (keyselector l) (keyselector r) with
            | n when n < 0 -> aux ls' rs ((Some l, None)::acc)
            | 0 -> aux ls' rs' ((Some l, Some r)::acc)
            | _ -> aux ls rs' ((None, Some r)::acc)
            
    aux ls rs [] |> List.rev

val mergeBy : keyselector:('a -> 'b) -> ls:'a list -> rs:'a list -> ('a option * 'a option) list (requires comparison)

Full name: Script.mergeBy

val keyselector : ('a -> 'b) (requires comparison)

val ls : 'a list

val rs : 'a list

val aux : ('a list -> 'a list -> ('a option * 'a option) list -> ('a option * 'a option) list)

val acc : ('a option * 'a option) list

val l : 'a

val ls' : 'a list

union case Option.Some: Value: 'T -> Option<'T>

union case Option.None: Option<'T>

val r : 'a

val rs' : 'a list

val compare : e1:'T -> e2:'T -> int (requires comparison)

Full name: Microsoft.FSharp.Core.Operators.compare

val n : int

Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
  | ( [] )
  | ( :: ) of Head: 'T * Tail: 'T list
  interface IEnumerable
  interface IEnumerable<'T>
  member Head : 'T
  member IsEmpty : bool
  member Item : index:int -> 'T with get
  member Length : int
  member Tail : 'T list
  static member Cons : head:'T * tail:'T list -> 'T list
  static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>

val rev : list:'T list -> 'T list

Full name: Microsoft.FSharp.Collections.List.rev

Raw view Test code New version

More information

Link:	http://fssnip.net/ck
Posted:	12 years ago
Author:	Simon Weijgers
Tags:	lists