Как смешать CoFree с катаморфизмом F-алгебры?

Во-первых, это основано на https://www.schoolofhaskell.com/user/bartosz/understanding-алгебрах, поэтому, если вы не знакомы с алгебрами и схемами рекурсии, прочитайте контекст.

Скажем, у меня есть простой анализатор выражений:

data Expr a = ... -- whatever
parse :: String -> Fix Expr
eval :: Algebra Expr (Either String Int)

Это может или не может быть успешным. Пример:

cata eval $ parse "3+4" -- Right 7
cata eval $ parse "3+x" -- Left "x not defined"

Мой вопрос в том, если бы кто-то

1) обновить функцию parse, чтобы аннотировать узлы с позициями разбора

2) префикс сообщений об ошибках с позициями разбора

как я могу интегрировать эти новые функции ниже с теми, что выше?

type ParsePositions = (Int,Int)
parse' :: String -> Cofree Expr ParsePositions
prefixError :: ParsePositions -> String -> String

Пример использования:

run "3+4" -- Right 7
run "3+x" -- Left "Error parsing [2,2]: x not defined"

Будет ли это зигоморфизмом? Может гистоморфизм? Оба потребуют некоторого искажения типа.

Бонусные баллы: должен ли я использовать алгебру elgot для короткого замыкания в случае неудачи, когда оценка может вернуть Left String?


haskell recursion-schemes catamorphism
person Golly    schedule 22.10.2016    source источник
comment
Что такое run? Это eval, или eval . parse, или что-то еще? (как правило, ваш вопрос должен содержать код, который можно скомпилировать и запустить, а не только сигнатуры примеров). Кажется, что run анализирует и оценивает за один шаг, что является ошибкой - выражение 3+x не является ошибкой синтаксического анализа, это семантическая ошибка. (вы обнаружите ошибку только тогда, когда синтаксический анализ завершен и вы пытаетесь оценить). Откажитесь от этой идеи, так как она ничего не даст вам по сравнению с раздельным синтаксическим анализом и оценкой.   -  person user2407038    schedule 22.10.2016
comment
Более того, повторное переключение на Cofree, похоже, ничего вам не даст. Что не так с Fix (Expr :+: K ParsePositions) или data (:&) f x a = f x :& a; Fix (Expr :& ParsePositions)? Они изоморфны Cofree Expr ParsePositions, но не требуют изменения базового типа во всем коде. Есть ли веская причина для перехода на Cofree? Вы хотите использовать некоторые дополнительные функции Cofree? Если да, то какой?   -  person user2407038    schedule 22.10.2016
comment
Я думаю, что этот вопрос более или менее дублирует Как работать с AST с аннотацией Cofree?. В моем ответе на этот вопрос я указываю, что Cofree не обязательно лучший выбор для маркировки синтаксических деревьев и что старый добрый функторный продукт сделает эту работу.   -  person Benjamin Hodgson♦    schedule 23.10.2016