Не могу понять результат вызова функции высокого порядка, предоставленной с частично не примененной функцией в качестве аргумента
У меня есть объявление функции высокого порядка, чтобы применить функцию, заданную в качестве аргумента дважды:
twice :: (a -> a) -> a -> a
twice f x = f (f x)
Беспорядок прибывает из этой сессии GHCi:
*Main> let _4 = twice twice
*Main> let __4 = twice twice (*2)
*Main> let _16 = _4 _4
*Main> let __16 = _4 __4
*Main> _16 (*2) 2
231584178474632390847141970017375815706539969331281128078915168015826259279872
*Main> __16 2
131072
Это вроде понятно с __16
потому что происходит просто "умножение" этого вызова функции, поэтому мы на самом деле получим (2 ^ 16) * 2
после его вызова. Насколько я понимаю, это происходит потому, что функция, заданная в качестве параметра, уже применяется частично, поэтому тип __4 и __16 (Num a) => a -> a
,
Но результат вызова _16
с данной функцией и целочисленными аргументами просто приводит меня в замешательство. Я могу понять, что тип либо _4
а также _16
сырые (равны twice
подпись функции, но вложенные под капот), но это не дает мне понятия о том, почему результаты так сильно отличаются. Я просто не могу получить семантику программы после предоставления функции, которая частично не применяется в качестве аргумента. Может кто-нибудь объяснить, почему этот номер просто так здорово?
3 ответа
Глядя на сокращение __16 2
немного:
__16 2 = _4 __4 2
= (twice twice) (twice twice (*2)) 2
= twice (twice (twice twice (*2)) 2
= twice (twice (twice (twice (*2)) 2
по сравнению с
_16 (*2) 2 = _4 _4 (*2) 2
= (twice twice) (twice twice) (*2) 2
= twice (twice (twice twice)) (*2) 2
Обратите внимание с __16
версия, вы просто удваиваете количество применений (*2)
с каждым twice
, Если вы посмотрите внимательно, вы увидите, что _16
версия заключена в скобки немного по-другому. Сначала вы удваиваете саму операцию удвоения, а затем применяете это к (*2)
а также 2
,
Первые несколько шагов по снижению _16 (*2) 2
может выглядеть так, следуя сверху
twice (twice (twice twice)) (*2) 2
= twice (twice (\x -> twice (twice x))) (*2) 2
= twice (\z -> (\x -> twice (twice x)) ((\y -> twice (twice y)) z)) (*2) 2
= twice (\z -> (\x -> twice (twice x)) (twice (twice z))) (*2) 2
= twice (\z -> twice (twice (twice (twice z)))) (*2) 2
= (\z -> twice (twice (twice (twice z)))) ((\w -> twice (twice (twice (twice w)))) (*2)) 2
= ((\z -> twice (twice (twice (twice z)))) (twice (twice (twice (twice (*2)))))) 2
= twice (twice (twice (twice (twice (twice (twice (twice (*2)))))))) 2
= ...
Самый внутренний twice (*2)
дает вам два (*2)
s. Следующий twice
удваивает это до 4 (*2)
s, то после этого удваивает это снова до 8 (*2)
и так далее. Есть восемь twice
s в приведенном выше выражении, так что вы получите 2^8 = 256 (*2)
с, так что результат 2 * (2^(2^8)) = 2 * (2^256) = 231584178474632390847141970017375815706539969331281128078915168015826259279872
,
С церковными цифрами, применение двух цифр a b
эквивалентно экспоненциальному b^a
, Так, _4 _4
соответствует 4^4=256
не 16
,
Грубо говоря: _4 f
средства f . f . f . f
то есть f
четыре раза, или "умножение f
на четыре ". Итак, _4 _4 f
означает "умножение f
в четыре, четыре раза ", следовательно 4^4
,
В самом деле:
> 2^256 * 2 :: Integer
231584178474632390847141970017375815706539969331281128078915168015826259279872
twice
не "дважды", это "квадрат":
(^.) :: (a -> a) -> Int -> (a -> a)
(f^.n) x = foldr ($) x [f | _ <- [1..n]]
((^.m) . (^.n)) f x = ((f^.n)^.m) x
= foldr ($) x [f^.n | _ <- [1..m]]
= (f^.(m * n)) x
= (^.(m * n)) f x
twice = (^.2) -- f^.2 = f . f f squared
_4 = twice twice
_4 f = (^.2) (^.2) f = ((^.2) . (^.2)) f = (f^.2)^.2 = f^.4
_4 = (^.4)
(^.3) (^.3) f = ((^.3) . (^.3) . (^.3)) f =
= ((^.3) . (^.3)) (f^.3)
= (^.3) ((f^.3)^.3)
= ((f^.3)^.3)^.3 = f^.(3*3*3) = f^.(3^3) = f^27
(^.4) (^.3) f = (((f^.3)^.3)^.3)^.3 = f^.(3*3*3*3) = f^.(3^4) = f^81
И вообще
(^.m) (^.n) f = f^.(n^m)
Функциональная композиция - это умножение, а приложение - (обратное) возведение в степень.
Таким образом, мы имеем
_16 f x = _4 _4 f x = (^.4) (^.4) f x = (f^.(4^4)) x = (f^.256) x
_16 (*2) 2 = ((*2)^.256) 2 = (* (2^256)) 2 = 2^257
*Main> _16 (*2) 2
231584178474632390847141970017375815706539969331281128078915168015826259279872
*Main> 2^257
231584178474632390847141970017375815706539969331281128078915168015826259279872