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

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

0 голосов
/ 29 октября 2018

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

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 ]

0 голосов
/ 29 октября 2018

Смотря на уменьшение __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) с.Следующий twice удваивает это значение до 4 (*2) с, следующий после этого удваивает это значение до 8 (*2) с и так далее.В приведенном выше выражении содержится восемь twice с, поэтому в итоге вы получите 2 ^ 8 = 256 (*2) с, в результате получите 2 * (2^(2^8)) = 2 * (2^256) = 231584178474632390847141970017375815706539969331281128078915168015826259279872.

0 голосов
/ 29 октября 2018

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
0 голосов
/ 29 октября 2018

Для церковных чисел применение двух цифр 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
...