кстати, как в хаскеле с дебагом принтами? Есть какой-нибудь хак типа Debug.log : String -> a -> a как в элме, который ведет себя как id + выводит что-нибудь чисто для дебага?
ты просто забил этот тип в hoogle?:)
Ilya
кана
да)
Зигохистоморфный
trace, traceM вроде
Andrey
С дебугтрейсом в ленивой семантике порой неожиданные вещи получаешь на выход )
a66ath
`
a66ath
levelorder x = loop [x]
where
loop [] = []
loop (Empty:xs) = loop xs
loop (Node v l r:xs) = v : loop (xs ++ [l, r])
a66ath
Как это оптимизировать?
Vladislav
С дебугтрейсом в ленивой семантике порой неожиданные вещи получаешь на выход )
Неожиданные они только если не знаешь, чего ожидать
Vladislav
Ленивостью надо проникнуться
Vladislav
Как это оптимизировать?
Добавить в loop еще один параметр, в котором будут накапливаться эти [l, r] в обратном порядке, а потом, как дойдешь до [], начать их разбирать
Andrey
Дерево в список элементов сплющить? Фолдом имхо, дерево дерайвит фолдабл.
Vladislav
Я думаю это какое-то упражнение
Vladislav
Иначе конечно фолд обычный
Andrey
foldr (:) [] вроде, если не путаю. Ну или что-то подобное из 5 символов )
a66ath
У меня кастомное дерево
Oleg
levelorder x = loop [x]
where
loop [] = []
loop (Empty:xs) = loop xs
loop (Node v l r:xs) = v : loop (xs ++ [l, r])
Мне кажется я один не понимаю, почему тут loop по списку, если функция принимает ровно один x
Andrey
Ну напиши в конце твоего тривиального кастомного бинарного дерева дерайвинг все что надо - от еку до траверсабла
Зигохистоморфный
a66ath
codewars
a66ath
Но да, stepik тоже
a66ath
Andrey
ааа, там не просто сплющить, а определенный порядок чтобы был? ну свой фолд написать - какМосквин завещал )
a66ath
Это и есть свой фолд
a66ath
Лол
a66ath
Но он медленный
Andrey
ясен пень xs ++ [l,r]
a66ath
Ну это понятно
a66ath
Но как
a66ath
В обратном порядке хранить эти [l,r] мне уже советовали
a66ath
Но как их потом разворачивать
a66ath
Вот это загадка
Andrey
Можно накопить в обратном порядке а потом все реверснуть. А вооюще задачу бы всю увидеть.
a66ath
Это вся задача
a66ath
Нет
a66ath
Но да
Andrey
на степике тесты убогие - на оптимальность реализации не проверяют вообще
Andrey
поэтому там бы прошло )
a66ath
https://www.codewars.com/kata/52bef5e3588c56132c0003bc/train/haskell
a66ath
treeByLevels :: Maybe (TreeNode a) -> [a]
treeByLevels x = loop [x] []
where
loop [] [] = []
loop [] acc = loop (concat . reverse $ acc) []
loop (Nothing:xs) acc = loop xs acc
loop (Just (TreeNode l r x) : xs) acc = x : loop xs ([l, r] : acc)
a66ath
Все еще медленно
Зигохистоморфный
замени вектором)
Зигохистоморфный
а потом просто toList
a66ath
Решил на списках
a66ath
Решил
Евгений
Ух, что-то интересное, а то всё редакторосрач, да редакторосрач
Andrey
Тоже решил. Там все просто. МОжет мои каты порешаете, раз такое вызывает интерес? ;)
Ilya
treeByLevels :: Maybe (TreeNode a) -> [a]
treeByLevels x = loop [x] []
where
loop [] [] = []
loop [] acc = loop (concat . reverse $ acc) []
loop (Nothing:xs) acc = loop xs acc
loop (Just (TreeNode l r x) : xs) acc = x : loop xs ([l, r] : acc)
Насколько я понял, стоит задача обойти бинарное дерево в ширину.
В таком случае, эффективное решение должно использовать тип данных "очередь". Очередь на списках эмулировать можно, но это будет неэффективно, т.к. нам надо прилеплять элементы с одно конца, а доставать с другого, а в х-ле списки "одностронние".
Ilya
гугл по запросу "haskell queue" выдает Data.Sequence, Data.Dequeue, можешь попробовать их
Andrey
Там для тестов достаточно обходить в ширину и приклеивать в конец списка. Главное не сорваться в глубину - подсунут бесконечное дерево и захотят взять первые 100 элементов результата функции - и тогда приплыли )
Ilya
вроде как речь шла про эффективную реализацию
Andrey
Ну по крайней мере на их месте я бы именно так и сделал. Бесконечные структуры данных в тестах на сабже милы - они сразу отсеивают решения, подразумевающие дно.
Ilya
по-крайней мере этого хотел автор
Andrey
Речь шла чтобы тесты на кодоварсах пройти
Andrey
И имхо именно этого хотел автор, а написал про "эффективную реализацию" )
Ilya
Это пожалуйста. Но надо понимать, что сколько не усирайся - нормально на х-ль списках эту задачу не решишь.
Ilya
def нормально = сравнимо с императивным алгоритмом, использующим очередь
Andrey
Надо. Но кодоварс - сферической в вакууме, никаких секов/дипсеков, арраев, векторов и прочих эффективных практических ужасов там не нужно ) Там даже вектор не подключается, насколько я помню )
кана
ну и на хаскеле можно решить императивно, если уж очень хочется
Ilya
а тут и не обязательно императивно даже
Ilya
просто блин, у списков доступ к концу это O(n), у очереди - O(1)
Ilya
вы это никак не обойдете
Ilya
а тесты можно сделать сколько угодно слабыми
Ilya
чтобы какое угодно г. прошло
кана
ну так у вектора доступ к любому элементу за O(1)
Andrey
Вектора ресайзить надо оптимально под капотом. С очередью свои сложности. А спписок в Хаскеле - это поток, или генератор.Но в этой задаче бесспорно он не самая оптимальная дструктура данных.
Ilya
я бы сказал самая неоптимальная =)
Ilya
ибо список по сути рабботает как стек
Ilya
а стек это противоположность очереди в каком-то смысле
Andrey
я бы поспорил насчет сравнения с вектором
Ilya
Andrey
если деревьев много и они неглубокие - вектор победит имхо. А если деревья глубокие - вектор просядет из-за постоянных релокаций и забивания памяти, а список сфьюзится и даже в память не будет занимать
Andrey
Ну выше тремя постами писали про вектра. И до этого тоже, предлагая их в этой задаче.
Ilya
ну может где-то очередь и реализуют вектором, не знаю
Alexander
Andrey
я Окасаков на читал, не знаю как эффективно реализовать очередь в ФП.