Ведение счетчика при каждом рекурсивном вызове в OCaml - PullRequest
Новая
       10

Ведение счетчика при каждом рекурсивном вызове в OCaml

4 голосов
/ 24 марта 2012

Я пытаюсь написать функцию, которая возвращает индекс переданного значения v в заданном списке x;-1 если не найдено.Моя попытка найти решение: 

let rec index (x, v) =
    let i = 0 in
        match x with
        [] -> -1
        | (curr::rest) -> if(curr == v) then
                            i
                          else
                            succ i; (* i++ *)
                            index(rest, v)
;;

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

Ответы [ 3 ]

7 голосов
/ 24 марта 2012

Мутация не является распространенным способом решения проблем в OCaml. Для этой задачи вы должны использовать рекурсию и накапливать результаты, изменяя индекс i при определенных условиях: 

let index(x, v) =
    let rec loop x i =
        match x with
        | [] -> -1
        | h::t when h = v -> i
        | _::t -> loop t (i+1)
    in loop x 0

Другое дело, что использование -1 в качестве исключительного случая не очень хорошая идея. Вы можете где-то забыть это предположение и относиться к нему как к другим показателям. В OCaml лучше обрабатывать это исключение, используя тип option, поэтому компилятор заставляет вас заботиться о None каждый раз: 

let index(x, v) =
    let rec loop x i =
        match x with
        | [] -> None
        | h::t when h = v -> Some i
        | _::t -> loop t (i+1)
    in loop x 0
4 голосов
/ 24 марта 2012

Это, безусловно, проблема с домашней работой, поэтому я просто сделаю два комментария.

Во-первых, такие значения, как i, являются неизменяемыми в OCaml.Их ценности не меняются.Так что succ i не делает то, что говорит ваш комментарий.Это не меняет значение i.Он просто возвращает значение, которое больше i.Это эквивалентно i + 1, а не i++.

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

3 голосов
/ 24 марта 2012

Вы не можете изменять переменные в OCaml (ну, есть способ, но вы не должны делать простые вещи, подобные этому)

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

let rec index_helper (x, vs, i) =
    match vs with
      [] -> -1
      | (curr::rest) ->
          if(curr == x) then
              i
          else
              index_helper (x, rest, i+1)
;;

let index (x, vs) = index_helper (x, vs, 0) ;;

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

Для некоторых конкретных шаблонов вместо этого вы можете попытаться воспользоватьсямногократно используемых функций высшего порядка, таких как map или folds.

...