tldr; перейдите к Моему вопросу

Я считаю, что проблема, представленная здесь, не должна быть совсем новой, но я не смог найти никакого прямого соответствующего обсуждения.

Предположим, что у меня есть следующая функция (чтобы обеспечить детерминированную замену функции реального мира, имеющей те же структурные свойства, типа 'a -> 'a seq ):

 // I'm a function that looks suspiciously like a tree
let lsExample x =
    match x with
    | 0 -> seq { 1; 6; 7 }
    | 1 -> seq { 2; 3 }
    | 3 -> seq { 4; 5 }
    | 7 -> seq { 8; 9 }
    | _ -> Seq.empty
 

Теперь я хотел бы иметь следующее:

 let lsAll: ('a -> 'a seq) -> 'a -> 'a seq
 

такие, что

 lsAll lsExample 0
 

оценивает, чтобы

 seq { 0 .. 9 }
 

Я нашел одно многословное решение этой проблемы и одно простое, но все же не идеальное решение аналогичной проблемы.

Решение 1

Преобразуйте ls функцию в Розовое дерево, затем сделайте предварительный заказ dfs на дереве следующим образом:

 open FSharpx.Collections
module L = LazyList
module R = Experimental.RoseTree

let rec asRoseTree (ls: 'a -> seq<'a>) (item: 'a) =
    let children = ls item
    if (Seq.isEmpty children) then
        R.singleton item
    else
        children
        |> Seq.map (asRoseTree ls)
        |> L.ofSeq
        |> R.create item

let lsAll ls =
    asRoseTree ls >> R.dfsPre
 

Решение 2

Выполнив свою работу, я захотел более элегантного решения, поэтому начал с этого приближения с использованием 'a -> 'a list ( list s предлагают сопоставление структурных шаблонов, в то seq время как s этого не делают… Я надеюсь, что никто никогда не использует эту реализацию):

 let rec lsAll' (ls: 'a -> 'a list) (xs: 'a list) =
    match xs with
    | [] -> []
    | [x] -> lsAll' ls (ls x) |> List.append [x]
    | x :: tail -> lsAll' ls tail |> List.append (lsAll' ls [x])

let lsAll ls x = lsAll' ls [x]
 

Затем я зашел в тупик, пытаясь сделать этот хвост рекурсивным, даже без дополнительных неудобств, связанных с переключением обратно на seq.

Мой вопрос

Как мы можем реализовать lsAll :

• не прибегая к построению промежуточной, явной древовидной структуры;
• с нужными типами (seq, не список);
• использование хвостовой рекурсии (случай для CPS?); и
• без явной саморекурсии (например, используйте сгиб с аккумулятором/cps)?

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

Вы можете сделать это очень красиво, используя выражения последовательности F# yield yield! и конструкции and:

 let rec lsAll ls x = seq {
  yield x
  for c in ls x do
    yield! lsAll ls c }

lsAll lsExample 0
 

Выражение последовательности seq { .. } — это блок кода, который генерирует последовательность. Внутри этого вы можете использовать yield для добавления одного элемента в последовательность, но также yield! и для добавления всех элементов какой-либо другой последовательности. Здесь вы можете сделать это, чтобы включить все значения, созданные рекурсивным вызовом.

Вы также можете объединить это с подходом в своем решении 2:

 let rec lsAll ls xs = seq {
  match xs with 
  | [] -> ()
  | x::xs -> 
      yield x
      yield! lsAll ls (ls x)
      yield! lsAll ls xs }
 

Для этого требуется lsAll вернуть список — вы могли бы вставить List.ofSeq его в предпоследнюю строку, но я думаю, что, вероятно, лучше оставить это пользователю. Однако теперь вы можете превратить это в хвостовую рекурсивную версию, используя CPS, где продолжением является «последовательность значений, которые будут получены после завершения текущего».:

 let rec lsAll ls xs cont = seq {
  match xs with 
  | [] -> yield! cont
  | x::xs -> 
      yield x
      yield! lsAll ls (ls x) (lsAll ls xs cont) }

lsAll (lsExample >> List.ofSeq) [0] Seq.empty
 

Если я дам этому бесконечное дерево, оно на самом деле не будет стекаться, но будет выделять все больше и больше памяти, так что, я думаю, это работает!