Намиране на елемент в списък и връщане на неговия индекс - OCaml

Написах следната функция за намиране на даден елемент "x" в даден списък "lst" и връщане на неговия индекс, ако бъде намерен, в противен случай ще върне грешка:

exception Failure of string

let rec func x lst c = match lst with
    | [] -> raise(Failure "Not Found")
    | hd::tl -> if (hd=x) then c else func x tl (c+1)


let find x lst = func x lst 0

Функцията работи напълно, само се чудя каква е консумацията на памет от нея? Това означава, че консумацията на памет зависи от дължината на списъка? или е O(1)?

Ако не е O(1), може ли някой да ме уведоми какво трябва да направя, за да стане така?

Благодаря ти


list find ocaml ml memory-consumption
person Kyle    schedule 07.07.2015    source източник
comment
Между другото, OCaml има конструктор на изключения Not_found само за този вид неща.   -  person gsg    schedule 08.07.2015

Отговори (1)


arrow_upward
4
arrow_downward

Вашата функция консумира постоянно (O(1)) пространство, защото е рекурсивна.

Можете да прочетете за опашната рекурсия в OCaml.org, тук.

Актуализация

Ето едно нерекурсивно решение:

exception Failure of string

let rec find x lst =
    match lst with
    | [] -> raise (Failure "Not Found")
    | h :: t -> if x = h then 0 else 1 + find x t

(Току-що забелязах, че PatJ вече обясни това, съжалявам :-)

Често нерекурсивното решение е по-сбито и елегантно. Жалко, но понякога светът е такъв.

person Jeffrey Scofield    schedule 07.07.2015
comment
Благодаря :) Просто от любопитство, как би изглеждала функция, която върши същата работа като тази, която написах, но консумира O(n) пространство? Няма нужда да отговарям на това, но всъщност бих искал да знам, тъй като не мога да измисля начин да го направя дори след като прочетох връзката, която ми изпратихте - person Kyle; 08.07.2015
comment
Ако рекурсивното извикване на функцията не е последното извършено действие преди връщането, тогава ще бъде O(n). Например, ако вместо променлива на брояча c имате if (hd=x) then 0 else 1+(find x tl), тогава всяко рекурсивно извикване ще добавя някои променливи към стека. - person PatJ; 08.07.2015
comment
Благодаря и на двама ви! Смешно е, защото снощи вероятно написах същата функция, която и двамата предложихте, но някак си просто не работи. OCamlWin е просто толкова бъгов понякога. - person Kyle; 08.07.2015