CODEWITHSUNDEEP
f#f#-scripting
Mike John
Mike John

Reputation: 818

F# Interesting Behavior of Curried Function

I have a function 

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

Then I have something like.

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

Depending on how I call twice it behaves differently do to left associativity. 

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

If I add another twice my program does a StackOverflow, but so far it seems to behave without a pattern, which drives me crazy.

Let k be the number of times twice is called.

Un-curried is 2^k to get the answer.

Curried is extremely odd. Hypothesis 1: When the number of calls is less than 4 it looks like 2^(2^(k-1)), but when k is 4 it behaves like 2^(2^k)

Does anyone see the pattern? Or can you run it past k = 4 to prove it?

Upvotes: 2

Views: 317

Answers (2)

Be Brave Be Like Ukraine
Be Brave Be Like Ukraine

Reputation: 7735

Indeed, it's all about associativity. When you write,

let x1 = twice twice twice twice f 0

It's equal to

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

This leads to exponential growth of call order: each twice call is supposed to call f x two times. Instead, it recursively calls itself, and only the most inner call would invoke f.

You may look at the prototype of the function:

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

The minimal code to make the associativity work well would be:

// 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

or

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

Upvotes: 1

John Palmer
John Palmer

Reputation: 25516

This is simple precedence rules behaving weirdly (the hint is 65536=2^16). In the second case you are actually creating an exponential number of calls to f rather than the linear increase you expected.

When you expand one layer on the second case you get

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

and the number of terms will grow exponentially as you write more twice

Upvotes: 3

Related Questions