M
Size: a a a
2020 September 09
С
Спор заведомо идиотский
M
О еще
p
Нет таких
Сейчас
M
Спор заведомо идиотский
Спор как раз таки предметный но не интересный потому что в учебниках тоже самое написанно
С
Спор как раз таки предметный но не интересный потому что в учебниках тоже самое написанно
О чем там написано? Что рекурсию нельзя?
"Нам-то не гони!" (С) "Жмурки"
"Нам-то не гони!" (С) "Жмурки"
ع
erlang на рекурсии, там ни каких цЫклоФ изкаропки вообще нет. И ничего, прекрасно живет и свои задачи выполняет вполне себе норм.
С
erlang на рекурсии, там ни каких цЫклоФ изкаропки вообще нет. И ничего, прекрасно живет и свои задачи выполняет вполне себе норм.
Модель вычислений эрланга уникальна, и нигде больше такого нет. Пример хоть и подходящий, но неудачный
NL
Был бы самым умным, не спрашивал бы примеры задачек, очевидно)
Короче, есть несколько канонiчных (я правильно написал это слово? 😊) задач на рекурсию, большинство из них связано с обработкой деревьев:
1. Разбор синтаксического выражения в AST.
2. Преобразование AST, например, упрощение выражения.
3. Операции над списками в ФП стиле, insert, delete, map, fold, length, transpose, find и др.
4. Merge sort тоже в ФП стиле.
5. Реализация красно-чёрного дерева в ФП или в императивном стиле (и там, и там требуется рекурсия, но мутация вынуждает перекрашивать ноды по-разному чтобы сохранить инвариант)
6. Реализация двоичного дерева поиска в ФП.
7. Инвертирование двоичного дерева поиска (делается буквально в 3 строчки, не знаю, почему у тех, кто собеседуется в гугл так пылает).
8. Решение игры про Ханойские Башни.
9. Решение судоку.
Для примера можешь глянуть мои упражнения на преобразование арифметических выражений в обратную польскую запись и вычисление значений.
https://github.com/nlinker/playground/tree/master/rust/shunting-yard
1. Разбор синтаксического выражения в AST.
2. Преобразование AST, например, упрощение выражения.
3. Операции над списками в ФП стиле, insert, delete, map, fold, length, transpose, find и др.
4. Merge sort тоже в ФП стиле.
5. Реализация красно-чёрного дерева в ФП или в императивном стиле (и там, и там требуется рекурсия, но мутация вынуждает перекрашивать ноды по-разному чтобы сохранить инвариант)
6. Реализация двоичного дерева поиска в ФП.
7. Инвертирование двоичного дерева поиска (делается буквально в 3 строчки, не знаю, почему у тех, кто собеседуется в гугл так пылает).
8. Решение игры про Ханойские Башни.
9. Решение судоку.
Для примера можешь глянуть мои упражнения на преобразование арифметических выражений в обратную польскую запись и вычисление значений.
https://github.com/nlinker/playground/tree/master/rust/shunting-yard
ع
Модель вычислений эрланга уникальна, и нигде больше такого нет. Пример хоть и подходящий, но неудачный
да, согласен, не совсем удачный.
D
забавно что пока что формально верифицированного компилятора c, c++ или rust в принципе не может быть
ع
Dima
забавно что пока что формально верифицированного компилятора c, c++ или rust в принципе не может быть
Эммм... точно? (просто вопрос)
D
насколько я помню https://www.cl.cam.ac.uk/~pes20/cpp/notes42.html пока что не пофиксили в с11(17)(20) memory model, так что да
D
но мб я чего то не понимаю
M
Короче, есть несколько канонiчных (я правильно написал это слово? 😊) задач на рекурсию, большинство из них связано с обработкой деревьев:
1. Разбор синтаксического выражения в AST.
2. Преобразование AST, например, упрощение выражения.
3. Операции над списками в ФП стиле, insert, delete, map, fold, length, transpose, find и др.
4. Merge sort тоже в ФП стиле.
5. Реализация красно-чёрного дерева в ФП или в императивном стиле (и там, и там требуется рекурсия, но мутация вынуждает перекрашивать ноды по-разному чтобы сохранить инвариант)
6. Реализация двоичного дерева поиска в ФП.
7. Инвертирование двоичного дерева поиска (делается буквально в 3 строчки, не знаю, почему у тех, кто собеседуется в гугл так пылает).
8. Решение игры про Ханойские Башни.
9. Решение судоку.
Для примера можешь глянуть мои упражнения на преобразование арифметических выражений в обратную польскую запись и вычисление значений.
https://github.com/nlinker/playground/tree/master/rust/shunting-yard
1. Разбор синтаксического выражения в AST.
2. Преобразование AST, например, упрощение выражения.
3. Операции над списками в ФП стиле, insert, delete, map, fold, length, transpose, find и др.
4. Merge sort тоже в ФП стиле.
5. Реализация красно-чёрного дерева в ФП или в императивном стиле (и там, и там требуется рекурсия, но мутация вынуждает перекрашивать ноды по-разному чтобы сохранить инвариант)
6. Реализация двоичного дерева поиска в ФП.
7. Инвертирование двоичного дерева поиска (делается буквально в 3 строчки, не знаю, почему у тех, кто собеседуется в гугл так пылает).
8. Решение игры про Ханойские Башни.
9. Решение судоку.
Для примера можешь глянуть мои упражнения на преобразование арифметических выражений в обратную польскую запись и вычисление значений.
https://github.com/nlinker/playground/tree/master/rust/shunting-yard
Первые два сразу минус мать
С
Эммм... точно? (просто вопрос)
Понятие "верификация" нельзя применить к чему-либо полному по Тьюрингу
EG
Компиляция Rust, кажется, не требует полноты по Тьюрингу, если у нас есть лимит рекурсии типов.
EG
Компиляция C тем более.
M
Понятие "верификация" нельзя применить к чему-либо полному по Тьюрингу
Бля...