insertAt in F# simpler and/or better

Question

I would like to start some questions about simplifying different expressions in F#.

Anyone have ideas for better and/or simpler implementation of insertAt (parameters could be reordered, too). Lists or Sequences could be used.

Here is some start implementation:

let insertAt x xs n = Seq.concat [Seq.take n xs; seq [x]; Seq.skip n xs]

Answer 1

From the Haskell Wiki - http://www.haskell.org/haskellwiki/99_questions/21_to_28

insertAt :: a -> [a] -> Int -> [a]
insertAt x ys     1 = x:ys
insertAt x (y:ys) n = y:insertAt x ys (n-1)

I'm not an F# programmer so I don't know the equivalent syntax for F# but this is a nice recursive definition for insertAt

Answer 2

Here's an F# implementation of the Haskell list insertion:

let rec insertAt x ys n =
    match n, ys with 
    | 1, _      
    | _, []     -> x::ys
    | _, y::ys  -> y::insertAt x ys (n-1)

let a = [1 .. 5]
let b = insertAt 0 a 3
let c = insertAt 0 [] 3

> 
val a : int list = [1; 2; 3; 4; 5]
val b : int list = [1; 2; 0; 3; 4; 5]
val c : int list = [0]

My Haskell isn't good enough to know whether the case of passing an empty list is correctly taken care of in the Haskell function. In F# we explicitly take care of the empty list in the second match case.

Danny

Answer 3

The implementation dannyasher posted is a non-tail-recursive one. In order to make the function more efficient, we'll have to introduce an explicit accumulator parameter which makes the function tail-recursive and allows the compiler to optimize the recursion overhead away:

let insertAt =
    let rec insertAtRec acc n e list = 
        match n, list with
        | 0, _     -> (List.rev acc) @ [e] @ list
        | _, x::xs -> insertAtRec (x::acc) (n - 1) e xs
        | _        -> failwith "Index out of range"

    insertAtRec []

Answer 4

For case you really want to work with sequence:

let insertAt x ys n =
  let i = ref n
  seq {
    for y in ys do
    decr i
    if !i = 0 then yield x
    yield y
  }

For all other cases dannyasher's answer is definitly nicer and faster.

Answer 5

Tail-recursive using Seqs:

let rec insertAt = function
    | 0, x, xs -> seq { yield x; yield! xs }
    | n, x, xs -> seq { yield Seq.hd xs; yield! insertAt (n-1, x, Seq.skip 1 xs) }