вставить в F # проще и / или лучше

Question

Я хотел бы начать несколько вопросов об упрощении различных выражений в F #.

У любого есть идеи для лучшей и / или более простой реализации insertAt (параметры также могут быть переупорядочены). Можно использовать списки или последовательности.

Вот несколько начальных реализаций:

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

Answer 1

Хвост-рекурсивный с использованием 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) }

Answer 2

Реализация, опубликованная Данняшером, не является хвостовой рекурсией . Чтобы сделать функцию более эффективной, нам нужно будет ввести явный параметр-аккумулятор, который делает функцию хвостовой рекурсивной и позволяет компилятору оптимизировать затраты на рекурсию:

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 3

Для случая, когда вы действительно хотите работать с последовательностью:

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
  }

Для всех остальных случаев ответ Данняшера определенно лучше и быстрее.

Answer 4

Вот реализация F # вставки списка Haskell:

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]

Мой Haskell недостаточно хорош, чтобы знать, правильно ли обрабатывается случай передачи пустого списка в функции Haskell. В F # мы явно заботимся о пустом списке во втором случае совпадения.

Danny

Answer 5

Из Хаскель Вики - 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)

Я не программист F #, поэтому не знаю эквивалентного синтаксиса для F #, но это хорошее рекурсивное определение для insertAt