Как тип `Fix` и функция` fix` одинаковы в Haskell?

Question

Я пытаюсь убедить себя, что тип 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?

Answer 1

Посмотрите на вид конструктора типа Fix:

> :k Fix
Fix :: (* -> *) -> *

Конструктор type Fix аналогичен функции fix.

Конструктор data - это нечто другое. Следуя объяснению, найденному в Понимание F-алгебры , Fix является оценщиком : он вычисляет член типа f (Fix f) для получения значения типа Fix f. Эта оценка без потерь ; Вы можете восстановить исходное значение из результата, используя unFix.

Answer 2

Давайте возьмем наивную реализацию fix:

fix f = f (fix f)

Для функции f это создает что-то вроде следующего:

f (f (f (f (f (f (f ...

Fix newtype делает то же самое, но для типов. Поэтому, если мы возьмем тип 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