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

У меня есть объявление функции высокого порядка, чтобы применить функцию, заданную в качестве аргумента дважды:

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)и так далее. Есть восемь twices в приведенном выше выражении, так что вы получите 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
Другие вопросы по тегам