Возвращает индекс запрошенного значения списка, используя fold в OCaml

Я написал рекурсивную версию индекса следующим образом

let index list value =
  let rec counter num = function
    | [] -> -1
    | h::t -> 
        if h == value 
          then num 
        else (counter (num + 1)) t
  in counter 0 list;;

Это работает, но затем наш профессор сказал, что мы должны использовать хвостовую рекурсивную версию, чтобы не было тайм-аута на сервере, поэтому я написал новую индексную функцию, используя fold, но я не могу понять, почему, если она не находит элемент, он возвращает число больше, чем длина списка, хотя я хочу, чтобы он возвращал -1.

let index2 list value = fold (fun i v -> 
  if i > (length list) then -1
  else if v == value then i                          
  else i+1) 0 list;;

Вот и моя складная версия:

let rec fold f a l = match l with
    [] -> a
  | (h::t) -> fold f (f a h) t;;

functional-programming higher-order-functions fold ocaml
person Arthur Collé    schedule 27.03.2014    source источник
comment
== — это физическое равенство (что хорошо для целых чисел), но вы, вероятно, имели в виду =.   -  person nlucaroni    schedule 28.03.2014
comment
Ваша реализация index является хвостовой рекурсией.   -  person Martin Jambon    schedule 28.03.2014

Ответы (2)


arrow_upward
1
arrow_downward

ИЗМЕНИТЬ

Почему вы переопределяете fold вместо использования List.fold_left?

Ваша первая версия индекса уже является хвостовой рекурсией, но вы можете улучшить ее стиль:

  • использование типа option вместо возврата -1, если он не найден;
  • напрямую рекурсивно вызывать индекс вместо функции подсчета;
  • использовать компаратор = (структурный) вместо == (физический);
  • используйте защиту в сопоставлении с образцом вместо оператора if.

So

let index list value =
  let rec index' list value i = match list with
    | [] -> None
    | h :: _ when h = value -> Some i
    | _ :: t -> index' t value (succ i)
  in index' list value 0

И, как уже было сказано, index2 не работает, потому что вы никогда не достигнете элемента, индекс которого больше, чем длина списка, поэтому вам просто нужно заменить i > (length list) на i = (length list) - 1, чтобы он заработал.

Но index2 менее эффективен, чем index, потому что index останавливается, как только элемент найден, тогда как index2 всегда оценивает каждый элемент списка и каждый раз сравнивает длину списка со счетчиком.

person Benoît Guédas    schedule 27.03.2014

arrow_upward
2
arrow_downward

Ваша сложенная функция вызывается один раз для каждого элемента списка. Таким образом, вы никогда не увидите значение i больше, чем (length list - 1).

В качестве побочного комментария довольно неэффективно (квадратичная сложность) продолжать вычислять длину списка. Было бы лучше вычислить его один раз в начале.

В качестве еще одного побочного комментария вы почти никогда не захотите использовать оператор ==. Вместо этого используйте оператор =.

person Jeffrey Scofield    schedule 27.03.2014