Хвостовая рекурсия при ветвлении в ширь
От: varenikAA https://www.youtube.com/playlist?list=PLtrvASfI1KW7VOYRKjglcagQzWLoxlncl
Дата: 13.12.19 04:13
Оценка:
Попалась головоломка:
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 возможно ли сделать рекурсих хвостовой? Мне почему-то кажется, что нет, но как это доказать не пойму.
Re: Хвостовая рекурсия при ветвлении в ширь
От: samius Япония http://sams-tricks.blogspot.com
Дата: 13.12.19 06:09
Оценка:
Здравствуйте, varenikAA, Вы писали:

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

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

Таким образом, построить tail-call не ленивое дерево от корня нельзя. Но можно собрать его через аккумулятор, для этого придется научиться подменять Leaf существующего дерева на Branch и начать с пустого дерева, обходя его каждый раз и перестраивая.
Re[2]: Хвостовая рекурсия при ветвлении в ширь
От: varenikAA https://www.youtube.com/playlist?list=PLtrvASfI1KW7VOYRKjglcagQzWLoxlncl
Дата: 13.12.19 09:52
Оценка:
Здравствуйте, samius, Вы писали:

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


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

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

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



но ведь одно значение дает два новых, получается чтобы собрать ветку нужно вычислить оба новых значения и так до бесконечности
1
2 4
4 8 8 16
Re[3]: Хвостовая рекурсия при ветвлении в ширь
От: samius Япония http://sams-tricks.blogspot.com
Дата: 13.12.19 11:08
Оценка:
Здравствуйте, 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-ов сводится к хвостовому. Доказать обратное вряд ли получится.
Re: Хвостовая рекурсия при ветвлении в ширь
От: WolfHound  
Дата: 14.12.19 00:30
Оценка:
Здравствуйте, varenikAA, Вы писали:

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

Фундаментальная проблема в том, что тебе нужно сохранять позицию в дереве.
По этому, как ни крути, а стек у тебя в любом случае будет.
Даже если ты его спрячешь в CPS, стеком он быть не перестанет.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re: Хвостовая рекурсия при ветвлении в ширь
От: σ  
Дата: 14.12.19 01:35
Оценка:
AA>buildTree возможно ли сделать рекурсих хвостовой? Мне почему-то кажется, что нет, но как это доказать не пойму.
Никак не доказать, т.к. абсолютно любая рекурсия превращается в хвостовую. Выше уже упомянули CPS. https://wiki.c2.com/?CpsTransformation
Отредактировано 14.12.2019 1:35 σ . Предыдущая версия .
Re[4]: Хвостовая рекурсия при ветвлении в ширь
От: varenikAA https://www.youtube.com/playlist?list=PLtrvASfI1KW7VOYRKjglcagQzWLoxlncl
Дата: 16.12.19 03:52
Оценка:
Здравствуйте, 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-ов сводится к хвостовому. Доказать обратное вряд ли получится.


Да. Ощущение что понял, но не до конца, попробую с перестройкой.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.