F # Интересное поведение функции

Question

карри

У меня есть функция

// Will perform a given function twice 
let twice f = (fun x -> f (f x)) 

Тогда у меня есть что-то подобное.

// Take x add 1 
let f x = x+1 

В зависимости от того, как я называю дважды, он ведет себя по-разному, чтобы левая ассоциативность.

(twice (twice (twice (twice f)))) 0;; // Outputs 16 
twice twice twice twice f 0;; // Outputs 65536 

Если я добавить еще дважды моя программа делает StackOverflow, но до сих пор, кажется, ведут себя без рисунка, который сводит меня с ума.

Позволяет k быть числом twice.

Для того, чтобы получить ответ, вы получите нетоварный 2^k.

Curried чрезвычайно странный. Гипотеза 1: Когда число вызовов меньше, чем 4 выглядит как 2^(2^(к-1)), но при к 4 она ведет себя как 2^(2^к)

ли кто-нибудь увидеть шаблон? Или вы можете запустить его мимо k = 4, чтобы доказать это?

Answer 1

Это простые правила приоритета, которые ведут себя странно (намек 65536 = 2^16). Во втором случае вы фактически создаете экспоненциальное число вызовов f, а не линейное увеличение, которое вы ожидали.

Когда вы расширяете один слой на втором случае вы получите

twice twice twice (twice twice twice (f)) 0 

и число членов будет расти в геометрической прогрессии, как вы пишете больше twice

Answer 2

В самом деле, это все о ассоциативности. Когда вы пишете,

let x1 = twice twice twice twice f 0 

Это равно

let x11 = (((twice twice) twice) twice) f 0 

Это приводит к экспоненциальному росту порядка вызова: каждый twice вызов должен вызвать f x два раза. Вместо этого он рекурсивно называет себя, и только самый внутренний вызов будет ссылаться на f.

Вы можете посмотреть на прототип функции:

let y1: (_ -> _ -> int) = twice twice twice twice 
// val y1: ((int -> int) -> int -> int) 

Минимальный код, чтобы сделать ассоциативности работу хорошо бы:

// note we need to specify a type here 
let y2: (_ -> _ -> int) = twice >> twice >> twice >> twice 
// the same with all arguments 
let x2 = (twice >> twice >> twice >> twice) f 0 

или

let y3 = f |> twice |> twice |> twice |> twice 
let x3 = (f |> twice |> twice |> twice |> twice) 0