VPF::[Ocaml] Работа со списками - Форум программистов

ywaw

Дата 4.7.2011, 08:24 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 2
Регистрация: 4.7.2011

Репутация: нет
Всего: нет

На днях начал изучать Ocaml. Подскажите как получить значение к произвольного элемента списка, удалить произвольный
элемент списка или вставить новый элемент в произвольную позицию. Это возможно?

Void

Дата 5.7.2011, 20:04 (ссылка)

(нет голосов)

Загрузка ...

λcat.lolcat

Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

Репутация: 1
Всего: 173

Возможно, только с линейной сложностью, как и полагается для односвязного списка.

Цитата(ywaw @ 4.7.2011, 10:24

)

получить значение к произвольного элемента списка

List.nth

Цитата(ywaw @ 4.7.2011, 10:24

)

удалить произвольный элемент списка или вставить новый элемент в произвольную позицию.

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

Код

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

--------------------

“Coming back to where you started is not the same as never leaving.” — Terry Pratchett

ywaw

Дата 6.7.2011, 05:44 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 2
Регистрация: 4.7.2011

Репутация: нет
Всего: нет

Цитата(Void @ 5.7.2011, 20:04)

Возможно, только с линейной сложностью, как и полагается для односвязного списка.

Цитата(ywaw @ 4.7.2011, 10:24

)

получить значение к произвольного элемента списка

List.nth

Цитата(ywaw @ 4.7.2011, 10:24

)

удалить произвольный элемент списка или вставить новый элемент в произвольную позицию.

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

Код

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\

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Функциональные языки: общие вопросы \| Следующая тема »