[Ocaml] Работа со списками

 
0
 
Functional languages
ava
ywaw | 04.07.2011, 09:24
На днях начал изучать Ocaml. Подскажите как получить значение к произвольного элемента списка, удалить произвольный
элемент списка или вставить новый элемент в  произвольную позицию. Это возможно?
Comments (2)
ava
Void | 05.07.2011, 20:04 #
Возможно, только с линейной сложностью, как и полагается для односвязного списка.
Цитата (ywaw @  4.7.2011,  10:24 findReferencedText)
получить значение к произвольного элемента списка

List.nth
Цитата (ywaw @  4.7.2011,  10:24 findReferencedText)
удалить произвольный элемент списка или вставить новый элемент в  произвольную позицию.

Введём сначала вспомогательную функцию:
let split_at lst n =
    let rec loop lst acc = function
        | 0 -> List.rev acc, lst
        | i -> match lst with
            | (x :: xs) -> loop xs (x :: acc) (i - 1)
            | [] -> failwith "split_at"
    in loop lst [] n

А потом:
let remove_at lst n =
    let (head, tail) = split_at lst n in
    match tail with
    | [] -> failwith "remove_at"
    | x :: xs -> head @ xs

let insert_at lst n elt =
    let (head, tail) = split_at lst n in
    head @ [elt] @ tail
ava
ywaw | 06.07.2011, 05:44 #
Цитата (Void @ 5.7.2011,  20:04)
Возможно, только с линейной сложностью, как и полагается для односвязного списка.

Цитата (ywaw @  4.7.2011,  10:24 \\"findReferencedText\\")
получить значение к произвольного элемента списка


List.nth

Цитата (ywaw @  4.7.2011,  10:24 \"findReferencedText\")
удалить произвольный элемент списка или вставить новый элемент в  произвольную позицию.


Введём сначала вспомогательную функцию:

let split_at lst n =

    let rec loop lst acc = function

        | 0 -> List.rev acc, lst

        | i -> match lst with

            | (x :: xs) -> loop xs (x :: acc) (i - 1)

            | [] -> failwith "split_at"

    in loop lst [] n


А потом:

let remove_at lst n =

    let (head, tail) = split_at lst n in

    match tail with

    | [] -> failwith "remove_at"

    | x :: xs -> head @ xs



let insert_at lst n elt =

    let (head, tail) = split_at lst n in

    head @ [elt] @ tail

Спасибо за код. Буду тестировать на скорость. Вопрос не праздный, т.к. пишу логическую игру Таблут.
Ранее писал на с#, а прототипы на питоне - если интересно - загляните на страничку chess-11.narod.ru\
Please register or login to write.
Firm of day
Вы также можете добавить свою фирму в каталог IT-фирм, и публиковать статьи, новости, вакансии и другую информацию от имени фирмы.
Подробнее
Contributors
  Void   ywaw
advanced
Submit