A brief summary of the Y-combinator trick, and an unusual use.
You may be familiar with the Y combinator and its sexy uses in functional programming. The standard examples of use are logging and caching. Let's summarize how the trick works. Given a recursive function $f:a\to b$, you rewrite it into a non-recursive function $f':(a\to b)\to(a\to b)$: The body of $f'\;f$ (that is, $f'$ applied to its first argument which we name $f$) looks exactly the same as the body of $f$. At this point, types are already long, so I'll write $t^\circ$ for $t\to t$. For example the type of $f'$ is $(a\to b)^\circ$. The Y combinator has the type $\forall\alpha\beta,\,(\alpha\to\beta)^\circ\to(\alpha\to\beta)$. In words, Y takes a function like $f'$ and ‘ties the knot’ to give us back $f$. Before tying the knot, however, you may apply to $f'$ any number of transformers, which are functions of type $(a\to b)^{\circ\circ}$. Roughly, each transformer pre-processes the argument and post-processes the result.
Here is an example.
let rec y f x = f (y f) x let fib' fib n = if n < 2 then n else fib (n - 1) + fib (n - 2) let p_int x = printf "%d\n" x let log p f' f n = p n; f' f n let fib = y (log p_int fib')
The call fib 3
prints the following:
3 1 2 0 1
But suppose you want to print the call graph.
init -> 3 3 -> 1 3 -> 2 2 -> 0 2 -> 1
To do so, a transformer needs access to the current value of the argument, but also to the previous value.
We will use a combinator successive
of type
$$ \forall\alpha\beta\gamma,\;(\alpha\to\gamma)\to(\alpha\to\beta)^\circ\to(\gamma\times\alpha\to\beta)^\circ $$
It transforms an untied function of type $(a\to b)^\circ$ into an untied function of type $(c\times a\to b)^\circ$, using a helper of type $a\to c$.
let successive g f' f (x, y) = f' (fun z -> f (g y, z)) y let p_string_int (s, n) = printf "%s -> %d\n" s n let fib = y (log p_string_int (successive string_of_int fib')) let _ = fib ("init", 3)
Let's break down the types involved in the second to last line, because they can get long and may be hard to track in one's head.
fib' : (int -> int) -> (int -> int) string_of_int : int -> string successive : (int -> string) -> ((int -> int) -> (int -> int)) -> (string * int -> int) -> (string * int -> int) successive string_of_int fib' : (string * int -> int) -> (string * int -> int) p_string_int : string * int -> unit log : (string * int -> unit) -> ((string * int -> int) -> (string * int -> int)) -> (string * int -> int) -> (string * int -> int) log p_string_int (successive string_of_int fib') : (string * int -> int) -> (string * int -> int) y : ((string * int -> int) -> (string * int -> int)) -> (string * int -> int) fib : string * int -> int
No comments:
Post a Comment
Note: (1) You need to have third-party cookies enabled in order to comment on Blogger. (2) Better to copy your comment before hitting publish/preview. Blogger sometimes eats comments on the first try, but the second works. Crazy Blogger.