Поиск элемента в списке и возврат его индекса - OCaml

Question

Я написал следующую функцию, чтобы найти данный элемент «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), кто-то, пожалуйста, сообщите мне, что я должен сделать, чтобы сделать это так?

Спасибо

Answer 1

Вашей функции потребляет постоянное (O (1)) пространство, потому что хвостовая рекурсия.

Вы можете прочитать о рекурсии хвоста на OCaml.org, here.

Update

Здесь не является хвостовой рекурсией решение:

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 уже объяснил это, извините :-)

Часто не- хвостовое рекурсивное решение более кратким и элегантным. Это слишком плохо, но иногда так бывает в мире.