Как я могу написать эту функцию только с помощью рекурсии в F#?

Question

let rec n_cartesian_product = function
    | [] -> [[]]
    | x :: xs ->
      let rest = n_cartesian_product xs 
      List.concat (List.map (fun i -> List.map (fun rs -> i :: rs) rest) x)

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

Определение concat-функции казалось простым:

let rec list_concat ( lst : 'a list list ) : 'a list =
match lst with 
[]    -> []
|x::xs  -> x @ (list_concat xs)

Проблема в том, что я застрял в определении функций, которые дают аргумент для concat:

let rec fun_i rest =
    match rest with
    [] -> []
    |x::xs -> fun_rs

and fun_rs =
fun_i :: fun_rs

Я не могу придумать правильное решение. Вы можете мне помочь?

редактировать: например, учитывая этот вход

[["A";"a"];["B";"b"];["C";"c"]]

Я хочу этот вывод:

[["A"; "B"; "C"]; ["A"; "B"; "c"]; ["A"; "b"; "C"]; ["A"; "b"; "c"];
 ["a"; "B"; "C"]; ["a"; "B"; "c"]; ["a"; "b"; "C"]; ["a"; "b"; "c"]]

Answer 1

N-декартово произведение

Чтобы рекурсивно определить n декартово произведение, самый простой метод - просто сделать рекурсивные определения функций, используемых в вашем исходном (нерекурсивном) примере:

let rec list_concat lst =
    match lst with 
    |[]    -> []
    |x::xs  -> x @ (list_concat xs)

let rec list_map f lst =
    match lst with
    |[] -> []
    |x::xs -> (f x) :: list_map f xs

let rec n_cartesian_product = 
    function
    | [] -> [[]]
    | x :: xs ->
      let rest = n_cartesian_product xs 
      list_concat (list_map (fun head -> list_map (fun tail -> head :: tail) rest) x)

С точки зрения написания идиоматически на F#, лучше писать с использованием более общих функций (например, fold) вместо создания множества пользовательских функций с явной рекурсией. Итак, вы можете определить некоторые дополнительные функции:

let list_collect f = list_concat << list_map f

let rec list_fold f acc lst =
    match lst with
    |[] -> acc
    |hd::tl -> list_fold f (f acc hd) tl

let n_cartesian_product_folder rest first = 
    list_collect (fun head -> list_map (fun tail -> head :: tail) rest) first

Тогда мы можем переопределить n_cartesian_product просто как:

let n_cartesian_product2 lst = list_fold (n_cartesian_product_folder) [[]] lst

Если бы мы использовали основные библиотечные функции F# (а не пользовательские рекурсивные реализации), этот подход включал бы больше стандартного кода с меньшим количеством ошибок.

Декартово произведение(я оставлю эту часть здесь, так как, по-видимому, это было полезно)

Определите функцию, которая принимает список 'a и составить список 'b * 'a где все вещи типа 'b какой-то поставляемый элемент y,

/// take a list of 'a and make a list of (y, 'a)
let rec tuplify y lst =
    match lst with
    |[] -> []
    |x::xs -> (y, x) :: (tuplify y xs)

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

/// cartesian product of two lists
let rec cartesianProduct lst1 lst2 =
    match lst1 with
    |[] -> []
    |x::xs -> tuplify x lst2 @ (cartesianProduct xs lst2)