Splicing F# lists

user_45843 0
Viewed 77

What's the best way to splice one list into the middle of another in F#?

For example, suppose the lists are [1; 2; 3; 4] and [7; 8; 9] respectively, and the splicing point is halfway along the first list, the result should be [1; 2; 7; 8; 9; 3; 4].

By 'best' I mean simplest/most idiomatic, on condition that it takes time no more than linear in the length of the result.

list f#
3 Answers

If you're already on F# 6, I would indeed follow Jackson's advice and just use the newly introduced List.insertManyAt.

If you're still on an older version and if you're fine with exceptions when the index is out of bounds, you could go with something like:

let insertManyAt index newValues source =
    let l1, l2 = List.splitAt index source
    l1 @ newValues @ l2

Or if you want a total function:

let insertManyAt index newValues source =
    if List.length source < index
    then
        None
    else
        let l1, l2 = List.splitAt index source
        Some (l1 @ newValues @ l2)
user_22194180
user_290610

An illustration how to solve the problem of inserting one list into another at an arbitrary position as a recursive function:

let insertManyAt index values source =
    let rec aux acc n =
        if n < index then function                       // not reached index yet
            | xs, y::ys -> aux (y::acc) (n + 1) (xs, ys) // element from source
            | _, [] -> List.rev acc                      // source exhausted, done
        else function
            | x::xs, ys -> aux (x::acc) n (xs, ys)       // element from values
            | [], y::ys -> aux (y::acc) n ([], ys)       // values empty, take source instead
            | [], [] -> List.rev acc                     // both lists empty, done
    aux [] 0 (values, source)

[ 0; 1; 2 ]
|> insertManyAt 1 [ 8; 9 ]
// val it : int list = [0; 8; 9; 1; 2]
user_28071300
Related