Рекурсивная взаимность

[deni_ok]

Между Haskell Report и GHC base имеется дивная взаимная рекурсия.

В GHC base мы имеем такое определение наименьшей неподвижной точки (least fixpoint)

fix :: (a -> a) -> a
fix f = let x = f x in x

В Haskell Report в разделе 3.12 описана трансляция для выражения let в ядро (привожу только релевантные правила)

let p = e1 in e0 = case e1 of ˜p

Comments

[maxim]

А есть какой-то алгоритм перевода Фикспойнт термов в правые фолды (с ограничениями)?
Я хочу примитивные фикспойнт потоковые парсеры (FSM) транслировать в foldr.
Типа в языке рекурсия чтобы присуствовала как понятие, но в ядре тайпчекера ее нет.

[deni_ok]

А зачем fix в языке, примитивной рекурсии над Nat недостаточно?

[maxim]

ну я вот про такую запись

expr([{N,X}|T],[{typevar,Y}|Acc]) -> expr(T,[{N,X},{typevar,Y}|Acc

[nponeccop]

Оно undecidable, но это ничего не значит

http://stackoverflow.com/a/14719346 - полезная ссылка про наименьшие и наибольшие фикспоинты

[papa_lyosha]

Класс!