Пытаюсь убедить себя, что тип Fix и функция fix — это одно и то же.
Но не могу найти корреляции между их определениями
-- definition of fix
fix :: (p -> p) -> p
fix f = let {x = f x} in x -- or fix f = f (fix f)
-- definition of Fix
newtype Fix f = Fix { unFix :: f (Fix f) }
Как конструктор Fix вписывается в форму (x -> x) -> x?
Посмотрите на вид конструктора типа Fix:
> :k Fix
Fix :: (* -> *) -> *
Конструктор типа Fix аналогичен функции fix.
Конструктор data — это нечто другое. Следуя объяснению, приведенному в разделе Понимание F-алгебр, Fix является оценщиком. : он оценивает терм типа f (Fix f) для получения значения типа Fix f. Эта оценка без потерь; вы можете восстановить исходное значение из результата, используя unFix.
Возьмем наивную реализацию fix:
fix f = f (fix f)
Для функции f это создает что-то вроде следующего:
f (f (f (f (f (f (f ...
Newtype Fix делает то же самое, но для типов. Итак, если мы возьмем тип Maybe, мы хотели бы создать:
Maybe (Maybe (Maybe (Maybe (Maybe (Maybe ...
Как бы мы создали функцию, которая конструирует этот тип? Сначала мы можем попробовать синоним типа:
-- fix f = f (fix f)
type Fix f = f (Fix f)
Вы должны увидеть, что это то же самое, что и наивная реализация fix выше с некоторыми незначительными изменениями. Но это не законно Haskell!
Это происходит по ряду причин: в основном, Haskell не допускает бесконечных типов, как в приведенном выше примере Maybe, и система типов Haskell является строгой, в отличие от ленивых вычислений, требуемых в fix. Вот почему нам нужен newtype. Определения новых типов (введенные с помощью newtype или data) допускают рекурсию, поэтому мы берем синоним нашего типа и меняем его на новый тип.
type Fix f = f (Fix f)
newtype Fix f = f (Fix f) -- change to newtype
newtype Fix f = Fix (f (Fix f)) -- need to have a constructor
newtype Fix f = Fix { unFix :: f (Fix f) } -- And name the field, also
