Приведи список постижений за и получи!хвостовая рекурсия в F #? - PullRequest
Новая
       13

Приведи список постижений за и получи!хвостовая рекурсия в F #?

0 голосов
/ 01 октября 2018

Я написал эту небольшую функцию , я повторю ее здесь для простоты ссылки: 

/// Take a list of lists, go left-first, and return each combination,
/// then apply a function to the resulting sublists, each length of main list
let rec nestedApply f acc inp =
    match inp with
    | [] -> f acc
    | head::tail -> 
        [
            for x in head do
                yield! nestedApply f (x::acc) tail
        ]

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

Если это не так, как я могу написать этот же код вхвост-рекурсивный способ?Я пробовал с List.collect (вывернутая идея есть в указанном вопросе), но я не совсем понял.

Ответы [ 2 ]

0 голосов
/ 04 октября 2018

Чтобы упростить вещи, я собираюсь отделить умножение списков от отображения функции.Таким образом, nestedApply будет выглядеть следующим образом: 

let nestedApply f lsts = mult lsts |> List.collect f

Где mult выполняет умножение списков и возвращает все комбинации.

Обычно я считаю, что выполнять хвостовую рекурсию лучшечтобы начать сначала с простой рекурсии: 

let rec mult lsts =
    match lsts with
    | [ ]       ->  [[]]
    | h :: rest ->  let acc = mult rest
                    h |> List.collect (fun e -> acc |> List.map (fun l -> e :: l ) )

Итак, эта версия mult выполняет свою работу, но не использует хвостовую рекурсию.Он служит шаблоном для создания версии хвостовой рекурсии, и я могу проверить, что оба возвращают одно и то же значение: 

let mult lsts =
    let rec multT lsts acc =
        match lsts with
        | h :: rest -> h 
                       |> List.collect (fun e -> acc |> List.map (fun l -> e :: l ) ) 
                       |> multT rest
        | [ ]       -> acc
    multT (List.rev lsts) [[]]

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

Много раз, когда у вас есть хвостовая рекурсивная функция, вы можете устранить рекурсию, используя функцию fold: 

let mult lsts  = 
    List.rev lsts 
    |> List.fold  (fun acc h -> 
           h 
           |> List.collect (fun e -> acc |> List.map (fun l -> e :: l ) ) 
         ) [[]]

или foldBack: 

let mult lsts =
    List.foldBack (fun h acc -> 
        h 
        |> List.collect (fun e -> acc |> List.map (fun l -> e :: l ) ) 
      ) lsts [[]]

Обратите внимание на сходство.

Вот решение в скрипке:

https://dotnetfiddle.net/sQOI7q

0 голосов
/ 02 октября 2018

Нет, это не хвостовая рекурсия, и фактически взорвет стек: 

let lists = 
    [1 .. 10000]
    |> List.map (fun i -> List.replicate 100 i)

nestedApply id [] lists

Вы можете сделать nestedApply хвостовую рекурсию, переписав ее в стиле передачи продолжения, но это не так.это просто n-арный декартово произведение, за которым следует карта?

...