«А если делать на анафорических лямбдах — так задачка вообще на пять минут»

Я что-то пока не понимаю, как сделать AST на final tagless. Мне нужно хранить АТД для дерева, чтобы по нему туда-сюда ходить, а не обработать линейно один раз.

Т.е. матчить его хочется? У Олега в lecture notes был пример про это

@GabrielFallen, ошибка преобразования в число: String: open

На либу в таком стиле бы поглядеть.

Я делал отдельные типы для представления выражений на разных стадиях обработки и кучу почти тождественных преобразований. Знакомые в одном исследовательском проекте в аналогичном случае создавали один общий тип.
Может быть можно воспользоваться GATD с параметром фантомным типом в зависимости от которого доступны нужные конструкторы.

Функциональное программирование в музыке.

Закодируйте по Чёрчу -- будет дерево, по которому можно "ходить" сколько угодно раз. 🤷‍♀

В общем-то, final tagless так же работает...

А про типизацию там глава есть? https://habr.com/ru/company/nix/blog/490010/

Кривой перевод очень до смешного.  Местами не понял, полез в оригинал.
Про типизацию в старой советской книжке пока не видел. Только начал читать.

Но зачем столько ухищрений, если можно просто иметь ADT?

"Просто ADT" у Вас уже есть. Но что-то Вас всё-таки не устраивает, а? 😉

Да, лишние уровни вложенности. А с полиморфными вариантами и лишних уровней нет, и дерево остаётся простым деревом!

TTG уже упоминали?

Дерево простым не остаётся, строго говоря, оно разваливается на куски — это раз. Без open recursive style полиморфные варианты всё равно не решают expression problem — это два. Сильно подозреваю, что у них есть "скрытые особенности" (подводные камни) в части типизации, композиции и реализации — это три.

Не надо думать, что полиморфные варианты — серебряная пуля. Final tagless, Free monads, Church encoding обеспечивают примерно все те же плюшки за примерно ту же цену. Дальше вопрос личного вкуса, IMHO. 🤷‍♀️

«примерно ту же»?..

— Как решить такую-то маленькую задачку?
— Вот тебе много умных слов, иди разбирайся.
Спросить на Reddit, что ли…

А кто определяет размер задачи? 😂

Количество строк в альтернативном решении!