@fsharp_flood - страница 1663

Henry

Что угодно.

Henry

Значение в узле.

Anonymous

код работает?

Anonymous

у Tree чего-то не хватает (ветви и листья)

Henry

Если поставить конкретную функцию для getAList, то да. Просто втупую можно: let getAList a = [ a; a ]

Henry

Но валится со StackOverflow.

Anonymous

аккумулятор добавь

Henry

По сути, ветка с пустым списком детей - это листок.

Anonymous

buildTree [] a1

Anonymous

еще непонятно условие выхода из функции

Henry

Пробовал и с аккумулятором, и с продолжением.

Henry

Поясню.

Anonymous

функция зациклена походу

Vladislav

А можно попросить помощи по хвостовой рекурсии? В какую сторону смотреть? Или есть общие принципы для таких кейсов? type Tree<'a> = | Branch of 'a * Tree<'a> list // val getAList : 'a -> 'a list let rec buildTree a = let lst = getAList a if List.isEmpty lst then Branch (a, []) else let subTrees = List.map buildTree lst Branch (a, subTrees)

А что сделать то хочешь

Henry

Есть внешняя функция getAList, которая по некоторому параметру вернёт список значений для под-деревьев. Если функция вернёт пустой список, то мы просто возвращаем листок. Тут вся информация описана.

Henry

А что сделать то хочешь

Хочу функцию buildTree сделать tail recursive.

Anonymous

buildTree a -(где а почему-то (a, subslist) -какая-то матрешщка получается

Anonymous

не благодари

Henry

Ну, конечно. Эта функция (buildTree) рекурсивно строит дерево. Когда-нибудь функция getAList для каждого узла не вернёт под-деревьев, и buildTree завершится и вернёт большое дерево.

Henry

не благодари

Так не за что благодарить. с:

Henry

Мне не обработать дерево нужно, а построить.

Anonymous

Henry

Это обработка "дерева" директорий, а не построение.

Henry

Новые папочки тут не добавляются, короче.

Anonymous

давай условие задачи и исходные данные

Henry

type Tree<'a> = | Branch of 'a * Tree<'a> list let getAList a = [ a; a ] let rec buildTree a = let lst = getAList a if List.isEmpty lst then Branch (a, []) else let subTrees = List.map buildTree lst Branch (a, subTrees) buildTree 1Нужно чтобы эта штука никогда не валилась со StackOverflowException.

Henry

Пробовал (наверняка неправильно пробовал) с аккумуляторами, продолжениями. Сейчас смотрю в сторону trampoline.

Vasily

Что оно валится, это логично

Henry

Это да.

Henry

Изначально я спросил, в какую сторону смотреть, чтобы функции такого вида сделать tail recursive.

Vasily

В хвостовой рекурсии текущий стейт вызывается до вызова функции

Romɑn

type Tree<'a> = | Branch of 'a * Tree<'a> list let getAList a = [ a; a ] let rec buildTree a = let lst = getAList a if List.isEmpty lst then Branch (a, []) else let subTrees = List.map buildTree lst Branch (a, subTrees) buildTree 1Нужно чтобы эта штука никогда не валилась со StackOverflowException.

У тебя List.IsEmpty никогда не будет тру. И на каждый элемент списка ты безусловно удваивает.

Romɑn

У тебя List.IsEmpty никогда не будет тру. И на каждый элемент списка ты безусловно удваивает.

Естественно у тебя СО потому что тут нет условия выхода(оно должно было бы быть на List.IsEmpty, но у тебя так построена ф-ция getAlist что ты условия выхода никогда не будет достигнуто

Henry

У тебя List.IsEmpty никогда не будет тру. И на каждый элемент списка ты безусловно удваивает.

В реальности там другая функция вместо getAList.

Henry

А можно попросить помощи по хвостовой рекурсии? В какую сторону смотреть? Или есть общие принципы для таких кейсов? type Tree<'a> = | Branch of 'a * Tree<'a> list // val getAList : 'a -> 'a list let rec buildTree a = let lst = getAList a if List.isEmpty lst then Branch (a, []) else let subTrees = List.map buildTree lst Branch (a, subTrees)

Henry

Чуть ранее сюда писал.

Henry

Когда-нибудь функция getAList для каждого узла не вернёт под-деревьев, и buildTree завершится и вернёт большое дерево.

Henry

Надеюсь, внятно донёс идею.

Romɑn

Изначально я спросил, в какую сторону смотреть, чтобы функции такого вида сделать tail recursive.

Чтоб сделать рекурсию хвостовой надо делать рекурсивный вызов в самом конце ветки ветвления. В тех местах где ты ставишь return в с#

Vasily

Ну у него тип данных не позволит

Vasily

Он почему-то вычисляет все дерево

Romɑn

Чтоб сделать рекурсию хвостовой надо делать рекурсивный вызов в самом конце ветки ветвления. В тех местах где ты ставишь return в с#

А у тебя она заворачивается в Branch

Romɑn

А у тебя она заворачивается в Branch

Так что никак в данном случае

Vasily

Вместо родительских ветвей

Henry

Я понимаю.

Romɑn

Вместо родительских ветвей

Дочерних?

Vasily

Ну да, имеет смысл вычислять только дочерние

Henry

Разве не любую функцию можно сделать tail recursive?

Vasily

И этот список передавать ниже

Vasily

Но читать в телеге код ппц неудобно. Предлагаю оформить гист

Romɑn

Разве не любую функцию можно сделать tail recursive?

Нет. Любую тэйл рекурсив ф-цию можно свести к циклу, но не любую рекрсию можно сделать тэйл

Romɑn

В этом и мощь рекурсии, ты иногда можешь делать такие вещи, которые циклами не сделать

Henry

Но читать в телеге код ппц неудобно. Предлагаю оформить гист

https://gist.github.com/HenryKovalevsky/b971aa95be70626de2cd774000dbe53e

Henry

Нет. Любую тэйл рекурсив ф-цию можно свести к циклу, но не любую рекрсию можно сделать тэйл

Интересно. Спасибо. Надо глубже проникнуться.

Romɑn

В этом и мощь рекурсии, ты иногда можешь делать такие вещи, которые циклами не сделать

Но чаще всего ты и не будешь их делать, тоже стоит понимать

Romɑn

А можно попросить помощи по хвостовой рекурсии? В какую сторону смотреть? Или есть общие принципы для таких кейсов? type Tree<'a> = | Branch of 'a * Tree<'a> list // val getAList : 'a -> 'a list let rec buildTree a = let lst = getAList a if List.isEmpty lst then Branch (a, []) else let subTrees = List.map buildTree lst Branch (a, subTrees)

Попробуй поменять типа дерева

Romɑn

Или это не вариант?

Henry

Вариант.

Henry

В оригинале там был рекурентный Record. :D

Henry

Увидел в проекте товарища и опрометчиво сказал, что можно оптимизировать функцию.

Henry

Полдня мучаюсь.

Henry

Я подозреваю, можно преобразовать в двоичное дерево, а на нём уже с continuation'ами реализовать.

Romɑn

Я подозреваю, можно преобразовать в двоичное дерево, а на нём уже с continuation'ами реализовать.

усложняешь чего-то)

Henry

усложняешь чего-то)

Не отрицаю такой вероятности.)

Igor

в данном случае хвостовая рекурсивная функция должна иметь 2 параметра: аккумулятор и еще что-то в теле функции мы проверяем это что-то и либо возвращаем аккумулятор как есть, либо дальше вычисляем функцию с новыми значениями аккумулятора и еще чего-то

Igor

аккумулятор в данном случае это дерево, которое строится

Igor

а второй параметр это наверное lst из "let lst = getInfoList a"

Igor

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

Ayrat

Полдня мучаюсь.

Я так и не понял с чем ты мучаешься Обход дерева можно сделать через хвостовую рекурсию. Но то что ты пытался сделать, я так и не понял. Какой-то билдТри который нихуя не делает!

Диёр

Я так и не понял с чем ты мучаешься Обход дерева можно сделать через хвостовую рекурсию. Но то что ты пытался сделать, я так и не понял. Какой-то билдТри который нихуя не делает!

Я думал нихуя не делает id в хаскеле

Ayrat

Я думал нихуя не делает id в хаскеле

Не, оно греет Землю

Ayrat

Возьми значение, верни значение!

Ayrat

Фаршик хотя бы инлайнит

Doge

Не, оно греет Землю

Так хаскель такое ещё как инлайнит же

Ayrat

Так хаскель такое ещё как инлайнит же

Да я шуткую

Ayrat

Не получилось

Henry

Я так и не понял с чем ты мучаешься Обход дерева можно сделать через хвостовую рекурсию. Но то что ты пытался сделать, я так и не понял. Какой-то билдТри который нихуя не делает!

Тут не обход дерева, а его построение. Мол, есть некоторое значение А, которое: 1. Записывается в текущий узел дерева 2. По значению генерируется список значений для дочерних деревьев.

Henry

Я сейчас поподробнее опишу.

Ayrat

Тут не обход дерева, а его построение. Мол, есть некоторое значение А, которое: 1. Записывается в текущий узел дерева 2. По значению генерируется список значений для дочерних деревьев.

И когда конструирование должно прекратится?

Ayrat

Звучит сомнительно