Попалась головоломка:

type Tree<'a> =
  | Leaf of 'a
  | Branch of 'a * Tree<'a> list


let getInfoList a =
  if System.DateTime.UtcNow.Ticks % 10L > 5L 
  then [ a*2L; a*4L; ]
  else []


let rec buildTree a =
    let lst = getInfoList a
    
    if List.isEmpty lst 
    then
      Leaf (a)
    else
      let subTrees = List.map buildTree lst
      Branch (a, subTrees)


let r = buildTree 1L

buildTree возможно ли сделать рекурсих хвостовой? Мне почему-то кажется, что нет, но как это доказать не пойму.

Здравствуйте, varenikAA, Вы писали:

AA>buildTree возможно ли сделать рекурсих хвостовой? Мне почему-то кажется, что нет, но как это доказать не пойму.
Хвостовая рекурсия требует отсутствия операций над результатом рекурсивного вызова. Здесь же из результатов рекурсивного вызова требуется создать список и поместить их в Branch. Другими словами, хвостовая рекурсия работает с линейными структурами данных, с простыми цепочками.

Таким образом, построить tail-call не ленивое дерево от корня нельзя. Но можно собрать его через аккумулятор, для этого придется научиться подменять Leaf существующего дерева на Branch и начать с пустого дерева, обходя его каждый раз и перестраивая.

Здравствуйте, samius, Вы писали:

S>Здравствуйте, varenikAA, Вы писали:

AA>>buildTree возможно ли сделать рекурсих хвостовой? Мне почему-то кажется, что нет, но как это доказать не пойму.
S>Хвостовая рекурсия требует отсутствия операций над результатом рекурсивного вызова. Здесь же из результатов рекурсивного вызова требуется создать список и поместить их в Branch. Другими словами, хвостовая рекурсия работает с линейными структурами данных, с простыми цепочками.

S>Таким образом, построить tail-call не ленивое дерево от корня нельзя. Но можно собрать его через аккумулятор, для этого придется научиться подменять Leaf существующего дерева на Branch и начать с пустого дерева, обходя его каждый раз и перестраивая.


но ведь одно значение дает два новых, получается чтобы собрать ветку нужно вычислить оба новых значения и так до бесконечности
1
2 4
4 8 8 16

Здравствуйте, varenikAA, Вы писали:

AA>Здравствуйте, samius, Вы писали:

S>>Здравствуйте, varenikAA, Вы писали:

AA>>>buildTree возможно ли сделать рекурсих хвостовой? Мне почему-то кажется, что нет, но как это доказать не пойму.
S>>Хвостовая рекурсия требует отсутствия операций над результатом рекурсивного вызова. Здесь же из результатов рекурсивного вызова требуется создать список и поместить их в Branch. Другими словами, хвостовая рекурсия работает с линейными структурами данных, с простыми цепочками.

S>>Таким образом, построить tail-call не ленивое дерево от корня нельзя. Но можно собрать его через аккумулятор, для этого придется научиться подменять Leaf существующего дерева на Branch и начать с пустого дерева, обходя его каждый раз и перестраивая.


AA>но ведь одно значение дает два новых, получается чтобы собрать ветку нужно вычислить оба новых значения и так до бесконечности
AA> 1
AA> 2 4
AA> 4 8 8 16

Не ленивое дерево бесконечной длины мы не сможем расположить в конечной памяти. Да и разрядность int64 конечна. Так, что о бесконечности не станем.

Вопрос же в другом, как сделать хвостовую рекурсию? Один из путей — класть промежуточный результат в аккумулятор. Начать с дерева Leaf 1L и в каждой итерации делать пробежку по нему и перестраивать.

Второй путь — continuation-ы. Он гарантированный. Любой рекурсивный процесс с помощью cont-ов сводится к хвостовому. Доказать обратное вряд ли получится.

Здравствуйте, varenikAA, Вы писали:

AA>buildTree возможно ли сделать рекурсих хвостовой? Мне почему-то кажется, что нет, но как это доказать не пойму.
Фундаментальная проблема в том, что тебе нужно сохранять позицию в дереве.
По этому, как ни крути, а стек у тебя в любом случае будет.
Даже если ты его спрячешь в CPS, стеком он быть не перестанет.

AA>buildTree возможно ли сделать рекурсих хвостовой? Мне почему-то кажется, что нет, но как это доказать не пойму.
Никак не доказать, т.к. абсолютно любая рекурсия превращается в хвостовую. Выше уже упомянули CPS. https://wiki.c2.com/?CpsTransformation

Здравствуйте, samius, Вы писали:

S>Здравствуйте, varenikAA, Вы писали:

AA>>Здравствуйте, samius, Вы писали:

S>>>Здравствуйте, varenikAA, Вы писали:

AA>>>>buildTree возможно ли сделать рекурсих хвостовой? Мне почему-то кажется, что нет, но как это доказать не пойму.
S>>>Хвостовая рекурсия требует отсутствия операций над результатом рекурсивного вызова. Здесь же из результатов рекурсивного вызова требуется создать список и поместить их в Branch. Другими словами, хвостовая рекурсия работает с линейными структурами данных, с простыми цепочками.

S>>>Таким образом, построить tail-call не ленивое дерево от корня нельзя. Но можно собрать его через аккумулятор, для этого придется научиться подменять Leaf существующего дерева на Branch и начать с пустого дерева, обходя его каждый раз и перестраивая.


AA>>но ведь одно значение дает два новых, получается чтобы собрать ветку нужно вычислить оба новых значения и так до бесконечности
AA>> 1
AA>> 2 4
AA>> 4 8 8 16

S>Не ленивое дерево бесконечной длины мы не сможем расположить в конечной памяти. Да и разрядность int64 конечна. Так, что о бесконечности не станем.

S>Вопрос же в другом, как сделать хвостовую рекурсию? Один из путей — класть промежуточный результат в аккумулятор. Начать с дерева Leaf 1L и в каждой итерации делать пробежку по нему и перестраивать.

S>Второй путь — continuation-ы. Он гарантированный. Любой рекурсивный процесс с помощью cont-ов сводится к хвостовому. Доказать обратное вряд ли получится.

Да. Ощущение что понял, но не до конца, попробую с перестройкой.