Почему этот вложенный рекурсивный вызов в шаблоне соответствия не работает?

Я написал простую функцию для репликации каждого элемент в списке заданное количество раз.

    let rec replicate l n = 
        let rec f l n acc = 
            match l with 
            |[]->acc
            |x::xs->f xs n (let rec h e n acc = if n = 0 then acc else h e (n-1) (e::acc) in h x n acc) 
        in List.rev (f l n [])

Это работает, поскольку я вызываю f и устанавливаю его аккумулятор на результат вспомогательного метода h

Но почему следующий метод не работает?

let rec replicate l n = 
    let rec f l n acc = 
        match l with 
        |[]->acc
        |x::xs->(let rec h e n acc = if n = 0 
        then f xs n acc else h e (n-1) (e::acc) 
        in h x n acc) 
    in f l n [];;

Здесь я вызываю внешнюю функцию f в случае n=0.

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

  1. повторить ["а"; "б"; "с"] 3;;
  • : список строк = ["а"; "а"; "а"; "б"; "б"; "б"; "с"; "с"; "с"]
  1. повторить ["а"; "б"; "с"] 3;;
  • : список строк = ["а"; "а"; "а"]

Вторая функция имеет синтаксическую ошибку

glennsl 22.03.2022 14:37

Есть еще одна закрытая скобка, которой там быть не должно: let rec h e n acc = (if n = 0)

Stef 22.03.2022 14:38
Учебная записка [Medium] Leetcode#22 Generate Parentheses
Учебная записка [Medium] Leetcode#22 Generate Parentheses
На этот раз мы собираемся решить еще одну классическую проблему, связанную с парными скобками, так называемую генерацию скобок.
1
2
56
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Во второй строке

let rec h e n acc = 
  if n = 0 then f xs n acc
  else h e (n-1) (e::acc) 
in h x n acc

вы вызываете f xs n acc с n=0, а не с начальным значением n.

Общий совет: лучше не вкладывать определения рекурсивных функций. Действительно, это ограничивает сложность вашего потока управления функциями. Например, с

let rec repeated_append n x l =
  if n = 0 then l
  else repeated_append (n-1) x (x::l)

let replicate n l = 
  let rec replicate_aux n acc l = 
    match l with 
    | [] -> List.rev acc
    | x::xs-> replicate_aux n (repeated_append n x acc) xs
  in
  replicate_aux n [] l

Я уверен, что рекурсивные функции repeated_append и replicate_append вызывают только себя в своем теле. В частности, нет возможности h вызова replicate или f, что упрощает чтение функции.

Учитывая repeated_append, вы также можете определить replicate просто как: let replicate n l = List.(l |> map (fun x -> repeated_append n x []) |> flatten)

Chris 22.03.2022 17:34

Если мы используем функции из модуля List, лучше использовать List.concat_map напрямую.

octachron 22.03.2022 17:37

Справедливо. Рано утром для меня. Также застрял на более старой версии OCaml на этой рабочей станции.

Chris 22.03.2022 17:39

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

octachron 22.03.2022 17:43

Другие вопросы по теме