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

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

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, но вложены под капот), но это не дает мне ни малейшего представления о том, почему результаты так сильно различаются. Я просто не могу понять семантику программы после предоставления функции, которая частично не применяется в качестве аргумента. Может кто-нибудь объяснить, почему это число ТАКОЕ ВЕЛИКОЛЕПНОЕ?


person nyarian    schedule 28.10.2018    source источник
comment
Пожалуйста, не используйте только форматированный текст, JPEG.   -  person Michael Litchard    schedule 29.10.2018


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

person David Young    schedule 29.10.2018
comment
Кажется, я наконец понял. Мы получим twice^8, что равно 16 times f(x), где f = (*2) и аргумент 2. Спасибо! Это описание достаточно понятно для такого новичка, как я! - person nyarian; 29.10.2018
comment
@AndreyIlyunin нет, 16 times (*2) is (* (2^16)) = (* 65536) - person Will Ness; 29.10.2018
comment
Ой, да, с числами напортачил. Из последнего шага сокращения ясно, что twice будет применяться на восьми уровнях, поэтому дважды будет вызываться 2^8 раза. Таким образом, с аргументом мы получим 2^(2^8) с одним *2, добавленным из самого аргумента. Таким образом, у нас будет 2^257 - person nyarian; 29.10.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
person chi    schedule 28.10.2018
comment
Я думаю, что понимаю, что происходит, но не знаю, почему это так ... Но спасибо, это половина пути! - person nyarian; 29.10.2018
comment
@AndreyIlyunin Совсем не очевидно. Если немного запутались, думаю, это нормально :) - person chi; 29.10.2018
comment
Да, это своего рода волшебный после императива мир с просто циклами. - person nyarian; 29.10.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
person Will Ness    schedule 29.10.2018
comment
сам ответ кажется более сложным, чем вопрос: D - person nyarian; 29.10.2018
comment
Хм. Я думал, что это проясняет. :) - person Will Ness; 29.10.2018
comment
Я изучаю Haskell около 3 дней, и я видел ад только сейчас xD Постараюсь понять это ... после года практики, может быть: D - person nyarian; 29.10.2018
comment
уведомление в (^. m) (^. n) f = f ^. (n^m) n, m - это обычные числа. Вы знакомы с разделами операторов? - person Will Ness; 29.10.2018
comment
Думаю, в этом могут быть ваши затруднения. Разделы операторов: (+ 2) 3 == (3 +) 2 == (+) 3 2 = 3 + 2. - person Will Ness; 29.10.2018
comment
Позвольте нам продолжить это обсуждение в чате. - person Will Ness; 29.10.2018