How to implement f (g) == g (f)
I answered a question yesterday and it made me think of an interesting (to me) puzzle
With the restriction on the use of lambdas, numbers, and +
only (no if
, ?:
or other language functions), the goal is to implement some f
and some g
such that
// contract f(x) => f' g(y) => g' f'(g') == g'(f') // or more simply: m(n) == n(m)
This is what I have come up with so far - this code is in JavaScript for the purpose of demonstrating the code in a browser , but answers in any functional language are acceptable (racket, clojure, ocaml, lambda calc, etc.)
// f
const f = x => k =>
k(y => y + x)
// g
const g = y => k =>
k(x => x + y)
// make instance of each
const a = f(1)
const b = g(2)
console.log(a(b))
// x => x + y1
// should be 3
console.log(b(a))
// y => y + x2
// should be 3
I was able to capture half of the relationship, but the other side is broken, because that f
and g
is now asymmetrical
// f
const f = x => k =>
k(y => y(x))
// g
const g = y => k =>
k(x => x + y)
// make instance of each
const a = f(1)
const b = g(2)
console.log(a(b))
// 3
// should be 3 (OK)
console.log(b(a))
// y => y + x2
// should be 3
I know why it doesn't work, but I'm having trouble fixing it. Most importantly, if this is not possible, I would be interested to know why.
If you come up with a solution that violates the constraints, I'm still interested in seeing it ^ _ ^
source to share
This answer assumes a strong unitless system (like Haskell, but I'm trying to stick with JS-like syntax here).
If we stay in the realm of parametricity, we don't need (and can't even use) numbers or conditions. Permanent functions don't change anything, so I'll leave them and link directly to f
and g
.
First, note that the equation
f(g) == g(f)
means both f
and g
have function types. Assuming both have different inputs, we get f: A -> X
and g: B -> X == (A -> X) -> X == ((B -> X) -> X) -> X == ...
, i.e. You get an infinite type. I remember reading an article about this exact construct (you can think of it as a pair of types and I think it forms a category), but unfortunately forgot its name - maybe there is more to say here.
A simpler solution would be a requirement A == B
. Then f, g: A -> X
, but since X == A
according to the symmetry equation, then f, g: A -> A
- for any A
, i.e. One of the possibilities doing this is the identity function:
id(id) == id(id)
Other solutions arise when we specialize A
in A -> A
; then we are looking for functions like (A -> A) -> (A -> A)
. This is already one (specialized) identical function that has already been found, but all form functions h => h o ... o h
are composition ( (o) = h => x => h(h(x))
) functions for a number of types. They "add their own repeats" in the application, for example.
(h => h o h)(h => h o h) == (h => h o h) o (h => h o h)
== h => h o h o h o h.
This shows that we can choose
f == g == h => h,
f == g == h => h o h,
f == g == h => h o h o h,
f == g == ...
which I think are all type functions forall A. (A -> A) -> (A -> A)
(excluding iteration).
There is also a ratio of the limit of this construction (infinite composition) to the infinite case described above (now in real Haskell):
Prelude> let g = \h -> h . g
<interactive>:11:19:
Occurs check: cannot construct the infinite type: b ~ (b -> c) -> c
source to share
This is the closest I could get, but it uses 3D expression ( ?:
)
const f = x => g =>
g === undefined ? x : g() + x
const g = y => f =>
f === undefined ? y : f() + y
const a = f(1)
const b = g(2)
console.log(a(b)) // 3
console.log(b(a)) // 3
Here is f
completely equivalent g
and we could just use one or the other
const f = x => g =>
g === undefined ? x : g() + x
const a = f(1)
const b = f(2)
console.log(a(b)) // 3
console.log(b(a)) // 3
source to share
For this, it is obvious that both f
, and g
should take a function as an argument and return the same value. However, after fumbling around, it quickly hit me with the fact that I was dealing with infinite types.
It's good if your Haskell functions id
are similar to JS x => x
. So in Haskell I would do;
f :: a -> a g :: a -> a f = id g = id *Main> f(g)(+3) 2 5 *Main> g(f)(+3) 2 5
Can be easily implemented in JS.
source to share