Hacker News new | ask | show | jobs
by rntz 3253 days ago
To me the most interesting part of this article is the part that nobody else seems to be commenting on: the ability to automatically invert a function, even a programmer-defined function. That seems magical! What if I define a hash function? How can it possibly invert that? Clearly there's something interesting going on behind the scenes, and I wish the article discussed what it is, and how (and when) it works.

Everything else in the article seems like plain old functional programming to me, with a little syntax sugar here and there.
2 comments
evincarofautumn 3253 days ago
The only other language where I’ve seen this is Factor, with its “undo” word. I presume they work similarly, so I can speak to the general idea.

It’s not that the compiler can invert a hash, or automatically derive a logarithm function from an exponentiation function, or anything like that.

Essentially, if you have a composition of functions in a “pipeline” (h ∘ g ∘ f):

    [ f g h ]
Then to get the inverse of the composition, you just invert each function and reverse the whole thing (f⁻¹ ∘ g⁻¹ ∘ h⁻¹):

    [ f g h ] undo
    [ \ h undo \ g undo \ f undo ]
“undo” is defined for a set of primitive words. If there isn’t an inverse defined for some function you used in the composition, then it fails; however, you can just define a custom inverse for your function. And obviously this relies on having some kind of reified representation of functions available.

“undo” can be used for things like pattern-matching: a destructuring function, which takes some value and produces its fields, is the inverse of a constructor, which takes the fields and constructs a value.

link
yorwba 3253 days ago
You could do something similar in "normal" functional programming languages, but you usually won't get the nice syntax.

Basically, you can represent each invertible function by a pair of functions (pseudo-Haskell, because I don't use it very often and can't test on mobile):

  data Invertible a b = Invertible { forward :: a, backward :: b }

  apply :: Invertible (a -> b) (b -> a) -> a
  apply f a = forward f a

  invert :: Invertible (Invertible a b -> Invertible b a) (Invertible b a -> Invertible a b)
  invert = Invertible { forward = invert', backward = invert'}
      where
      invert' :: Invertible a b -> Invertible b a
      invert f = Invertible { forward = backward f, backward = forward f}
Then you can for example invert invert itself by

  apply invert invert == invert
But because there is no built-in language support, you'll end up doing lots of parallel construction of the standard library before you can even think of using it productively. Apparently someone already did that for Haskell (https://hackage.haskell.org/package/invertible), but it likely doesn't cover everything.
link