Недавний плакат, который лучше всего оставить анонимным, попытался реализовать факториальную функцию следующим образом:
f :: Int -> Int
f = fix f
Это явно не сработало. Но потом я задумался: могу ли я пройти проверку типов? Что откроет его тип?
Недавний плакат, который лучше всего оставить анонимным, попытался реализовать факториальную функцию следующим образом:
f :: Int -> Int
f = fix f
Это явно не сработало. Но потом я задумался: могу ли я пройти проверку типов? Что откроет его тип?
Действительно, благодаря полиморфной рекурсии он будет проверять типы для более общего типа:
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
, и в этот момент становится ясно, что первый аргумент бесполезен для получения результата.
f = bar f
будет работать с любыми bar :: F a -> a
, где F a
- любой тип (который может зависеть от a
). Например. proj2 :: (a,a) -> a
. Я вообще-то думаю, что в fix
, который здесь эксплуатируется, нет ничего особенного.
- person chi; 22.02.2016
fix
, это также проверка типа: f3 :: a -> a ; f3 = fix f3
и f4 :: (a -> a) -> a -> a ; f4 = fix f4
. Полиморфная рекурсия все еще нужна (конечно!), Но мне интересно, что у нас больше типизаций, чем ::a
(бесконечное множество, я полагаю).
- person chi; 22.02.2016
seq
Haskell может различать ⊥
, const ⊥
, const (const ⊥)
и т. Д., Наиболее общий forall a . a
типизация также является наиболее информативной.
- person dfeuer; 22.02.2016
forall a . a
должно иметь возможность создавать что-то типа a
для любого a
, без какой-либо информации о a
. Это невозможно, но для.
- person dfeuer; 22.02.2016
forall
к функции f
упростит задачу.
- person Sibi; 22.02.2016
fact
^^ - но спасибо за обновление - person Random Dev   schedule 22.02.2016