5 ms·
This idiom is even more useful in functional programming where the last step is an inverse of the first step in the applicative sense rather than in the side-ef
by psykotic 15y ago
This idiom is even more useful in functional programming where the last step is an inverse of the first step in the applicative sense rather than in the side-effects sense.
Mathematicians call it conjugation, and it can be usefully thought of as a temporary change of coordinates or change in vantage point. Problems often become simpler, even trivial, when working in the right coordinates.
In practical programming, it is commonplace that the "inverse" that occurs in conjugation idioms is a genuine right-inverse but only partially a left-inverse. This is true for his example of squares and square roots. For another instance, consider
reverseWords = unwords . reverse . words
The composition words . unwords :: [String] -> [String] is the identity, but unwords . words :: String -> String is the identity only for strings whose words are separated by a single space rather than multiple spaces, tabs, etc. This property can actually be put to good use:
normalizeWhitespace = unwords . words
If you like, you can think of unwords . words as an orthogonal projection onto the subspace of strings on which unwords is a genuine left-inverse of words (cf. Moore-Penrose pseudoinverses).
That's cool and all, but the effect on reverseWords is that it normalizes interword whitespace in the process of reversing words, whether you like it or not.
Incidentally, it's not too hard to abstract out this pattern with invertible functions:
data Invertible a b = Invertible (a -> b) (b -> a)
invertible = Invertible
apply (Invertible f f') = f
unapply (Invertible f f') = f'
inverse (Invertible f f') = Invertible f' f
compose (Invertible f f') (Invertible g g') = Invertible (f . g) (g' . f')
conjugate i f = unapply i . f . apply i
on = flip conjugate
Now you'd have to set up invertibles for all the usual foo/unfoo pairs of functions. Assume that has been done. Our example only needs words/unwords:
import Data.String as S
words = invertible S.words S.unwords
With those preliminaries out of the way, you can then reimplement reverseWords very neatly:
reverseWords = reverse `on` words
In fact, it's now so concise and self-explanatory that you hardly need the named definition anymore and can just refer to reverse `on` words directly.
- jfoutz 15y agoya know, i was thinking of bracket, but your example is better. fwiw, the haskell bracket docs contain "captures a common allocate, compute, deallocate idiom in which the deallocation step must occur even in the case of an error during computation. This is similar to try-catch-finally in Java. "
- sfvisser 15y agoOne of the interesting properties of the Invertible datatype is that it can be made an instance of the Haskell Category type class, which makes invertible functions fully composable using the (.) operator.
- dons 15y agoYes, composable data structure editors (lenses) with an overloaded (.) make my day to day work much more pleasant.
- Martijn 15y agoAlso: identity = Invertible id id
- ArbitraryLimits 15y agoAnother nice simple example of the "pseudoinverse idiom" is when you have a "boolean" variable in C, i.e. 0 is false and non-zero is true, and you want to set a particular bit in a bit flag to 0/1 from this boolean value. If the origianl "boolean" value is foo, you do "!!foo" since !<non-zero> == 0 and !0 == 1, and bit-shift the result. I never made the connection with Moore-Penrose pseudoinverses, but there it is.
- waqf 15y ago> If you like, you can think of unwords . words as an orthogonal projection onto the subspace of strings on which unwords is a genuine left-inverse of words (cf. Moore-Penrose pseudoinverses). It's even more like a reflector in a https://en.wikipedia.org/wiki/Reflective_subcategory https://en.wikipedia.org/wiki/Reflective_subcategory. (To make this analogy precise, you'd have to have some category structure where single-space is initial among all whitespace strings. Which is certainly possible; you just have to persuade yourself that that's a natural thing to do.)
- agumonkey 15y agoSome guy at Adobe Research made a conference about inverse relations in GUI context ( classical example being the degrees to fahrenheit relation ). I can't locate the URL right now * frustrated * I think it was their C++ guru .. can't remember anything else // ahh self cache miss
- agumonkey 15y agoTurns out I greatly exagerated my memories (sic), he was mentionning equivalence relation using c++ concepts then went into constraint/dependant interactive input. http://stlab.adobe.com/wiki/images/2/20/2008_07_25_google.pdf http://stlab.adobe.com/wiki/images/2/20/2008_07_25_google.pd... page 18, 38 this was hosted at googletechtalks http://www.youtube.com/watch?v=4moyKUHApq4 http://www.youtube.com/watch?v=4moyKUHApq4 (240p)
- shubber 15y agoThis idea is incredibly seductive to me, but the trouble I've always had is made completely lucid in your description of "conjugates" that are "only partially left inverse." The issue is that so many operations that it would be nice to be able to use as a conjugation aren't actually reversible. At best, you have situations where the flawed reversal is acceptable - the Ruby File::open("file"){} example, or the J example for computing magnitude. close(open("file")) isn't exactly as if nothing had happened. sqrt(a2) ?= a // only if a >= 0 But, consider parsing and templating: Could you template back exactly the input that you parsed to get an internal representation? Only if every character of input is unambiguous and significant - in other words, almost never.
- oelewapperke 15y agoThe big problem in this functional description imho is that the original premise is wrong : this idiom does not -at all- call for the inverse of functions. close() is not the inverse of open(). Especially not if there have been write actions on the file. Open "dereferences" a filename into a series of bytes. Close destroys the filehandle. Both are very un-functional concepts. Even memory allocation malloc/free are hardly the reverse of eachother. Free does not leave the system in the state it was before malloc, that only happens in the most trivial case possible.
- tmoertel 15y agoActually (unwords . words) is the identity only for lists of strings containing no whitespace. For example: Prelude> let xs = [" a"] in xs == (words . unwords) xs False
- psykotic 15y agoThanks for catching that!