Как сделать так, чтобы внутренняя рекурсивная функция достигла исходной переменной в OCaml?

Question

Я изучаю OCaml и теперь застрял с кодом. Это код, который составляет список доступных узлов из графика.

type graph = (vertex * vertex) list
and vertex = int

let rec sort lst =
   match lst with
     [] -> []
   | h::t -> insert h (sort t)
 and insert n lst =
   match lst with
     [] -> [n]
   | h::t -> if n <= h then n :: lst else h :: insert n t;;

let rec remove lst =
match lst with
| []       -> []
| x::[]    -> x::[]
| x::y::tl ->
   if x=y then remove (y::tl)
   else x::remove (y::tl);;

let rec reach : graph * vertex -> vertex list
= fun (g, v) ->
  match g with
  |[] -> []
  |h::t ->let x = [] in
          match h with
         |a,b -> if a = v then remove(sort(v::x) @ (reach (g, b)))
                  else
                    remove(sort(v::reach (t, v)));;
reach([(1,2);(2,3);(3,4);(4,2);(2,5)],4);;

Я думаю, что мой код бессмысленно сложен из-за отсутствия у меня возможности кодирования. Кроме того, главная проблема, с которой я сейчас сталкиваюсь, заключается в том, что я не могу заставить рекурсивную функцию «достигать» доступа с исходным списком «g», поскольку она становится рекурсивной в другом состоянии, поскольку она обращается со списком «t».

trace говорит

reach <-- ([(1, 2); (2, 3); (3, 4); (4, 2); (2, 5)], 4)
reach <-- ([(2, 3); (3, 4); (4, 2); (2, 5)], 4)
reach <-- ([(3, 4); (4, 2); (2, 5)], 4)
reach <-- ([(4, 2); (2, 5)], 4)
reach <-- ([(4, 2); (2, 5)], 2)
reach <-- ([(2, 5)], 2)
reach <-- ([(2, 5)], 5)
reach <-- ([], 5)
reach --> []
reach --> [5]
reach --> [2; 5]
reach --> [2; 5]
reach --> [4; 2; 5]
reach --> [2; 4; 5]
reach --> [2; 4; 5]
reach --> [2; 4; 5]
- : vertex list = [2; 4; 5]

Сначала я запросил новую переменную с let y = g и изменил код

|a,b -> if a = v then remove(sort(v::x) @ (reach (y, b)))
                  else
                    remove(sort(v::reach (t, v)));;

, так как полагал, что дубликаты будут удаленыс помощью функции «удалить» и внутренняя функция получит доступ к списку y, а не к t, который потерял свою голову. Однако все пошло не так, как я планировал. Это все еще дает мне тот же результат. Чтобы сделать доступ к функции с исходным списком «g» в другом состоянии, что мне делать ...?

reach <-- ([(1, 2); (2, 3); (3, 4); (4, 2); (2, 5)], 4)
reach <-- ([(2, 3); (3, 4); (4, 2); (2, 5)], 4)
reach <-- ([(3, 4); (4, 2); (2, 5)], 4)
reach <-- ([(4, 2); (2, 5)], 4)
reach <-- ([(1, 2); (2, 3); (3, 4); (4, 2); (2, 5)], 2)
(*I want function goes back to original list as the variable changes like above*)

Answer 1

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

let reach g v = 
  let rec aux g' v' = ... (* here you can use g as the auxiliary function defines g' instead *)
  in aux g v

Обратите внимание, что я также определяю функцию с двумя аргументами вместо одного кортежа, это более идиоматично:)

Также, если v'всегда одно и то же значение, вспомогательная функция не должна переопределять его

let reach g v = 
  let rec aux g' = ... 
  in aux g v

Еще одно замечание. Можно выполнить более глубокое сопоставление с образцом, например:

  match g with
  |[] -> []
  |(a,b)::t -> let x = [] in
     if a = v
     then remove(sort(v::x) @ (reach (g, b)))
     else remove(sort(v::reach (t, v)));;

Нет необходимости во втором сопоставлении.

Наконец, вам может быть известно ключевое слово function, которое создает функцию одного аргумента. создание сопоставления с шаблоном:

let f x = match x with
(* same as *)
let f = function

Поэтому:

let reach (g:graph) (v:vertex) =
  let aux v' = function (*we don't create a g' variable here, we match it straight *)
  | [] -> []
  | (a,b)::t as g' -> (* you can still define the variable in the matching if you need it *)
    let x = [] in
      if a = v
      then remove(sort(v::x) @ (aux b g')) (* or g if that's what you need *)
      else remove(sort(v::aux v t))
  in aux v g

будет делать то же самое, что и ваш код

Редактировать: исправлять повторные вызовы до reach рекурсивными вызовамиaux как не получится.

Answer 2

Отвечая непосредственно на ваш вопрос, вот как получить доступ к исходному значению в рекурсивной функции

let to_matrix outer = 
    let rec loop = function
      | [] -> []
      | x :: xs -> [x::outer] @ loop xs in
    loop outer

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

# to_matrix [1;2;3];;
- : int list list =
[[1; 1; 2; 3]; [2; 1; 2; 3]; [3; 1; 2; 3]]

. Пример может быть глупым, но я надеюсь, что он проясняет технику. Идея заключается в том, что мы создаем внутреннюю функцию с именем loop в нашем случае, которая имеет собственный параметр, и мы рекурсивно используем только этот параметр, оставляя исходный список outer без изменений.

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

let rec to_matrix outer inner = match inner with
  | [] -> []
  | x :: xs -> [x::outer] @ to_matrix outer xs

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

to_matrix [1;2;3] [1;2;3];;

. Поэтому идиоматично скрывать эту функцию с помощью более приятного интерфейса.