Какая фиксированная точка фиксации?

Недавний плакат, который лучше всего оставить анонимным, попытался реализовать факториальную функцию следующим образом:

f :: Int -> Int
f = fix f

Это явно не сработало. Но потом я задумался: могу ли я пройти проверку типов? Что откроет его тип?


person dfeuer    schedule 22.02.2016    source источник
comment
ого ... не достал деталь с fact ^^ - но спасибо за обновление   -  person Random Dev    schedule 22.02.2016


Ответы (1)


Действительно, благодаря полиморфной рекурсии он будет проверять типы для более общего типа:

f :: a
f = fix f

По параметричности мы сразу видим, что он должен быть нижним, и, исходя из определения fix, это должен быть бесконечный цикл, а не исключение.

чи комментарии, для того же причина f = bar f будет "работать" с любыми bar :: F a -> a, где F a - это любой тип (который может зависеть от a). Определение выглядит так:

foo :: forall f a .
       (forall b . f b -> b) -> a
foo g = g (foo g)

Опять же, сигнатура типа является поддельной из-за параметризации, поскольку я могу выбрать, например, f ~ Const Void, и в этот момент становится ясно, что первый аргумент бесполезен для получения результата.

person dfeuer    schedule 22.02.2016
comment
Интересный. По той же причине f = bar f будет работать с любыми bar :: F a -> a, где F a - любой тип (который может зависеть от a). Например. proj2 :: (a,a) -> a. Я вообще-то думаю, что в fix, который здесь эксплуатируется, нет ничего особенного. - person chi; 22.02.2016
comment
Что касается fix, это также проверка типа: f3 :: a -> a ; f3 = fix f3 и f4 :: (a -> a) -> a -> a ; f4 = fix f4. Полиморфная рекурсия все еще нужна (конечно!), Но мне интересно, что у нас больше типизаций, чем ::a (бесконечное множество, я полагаю). - person chi; 22.02.2016
comment
@chi, смотри мою правку в ответ на твой первый комментарий. Ваш второй также действителен, но поскольку зло seq Haskell может различать , const ⊥, const (const ⊥) и т. Д., Наиболее общий forall a . a типизация также является наиболее информативной. - person dfeuer; 22.02.2016
comment
Что вы подразумеваете под параметричностью в ответе? Я не сразу вижу, что это дно из параметричности. - person Sibi; 22.02.2016
comment
@Sibi, что-то с типом forall a . a должно иметь возможность создавать что-то типа a для любого a, без какой-либо информации о a. Это невозможно, но для. - person dfeuer; 22.02.2016
comment
Ах, спасибо. Это проясняет. Вероятно, добавление forall к функции f упростит задачу. - person Sibi; 22.02.2016