Inverse functions in Haskell

In this post I will show a simple way of finding the inverse of a function on the real line in Haskell.

Let f be a continuous (real) function defined on a closed interval [a,b]. The inverse of f is well-defined if and only if f is injective (i.e. no value can be assumed at two distinct points, i.e. f(x)=f(y) implies x=y). This is not a property that Haskell can easily check for us, so it is up to us to make sure that f is injective. From now on, we assume that f is injective.

The problem at hand is this: for each y in the range of f find x such that f(x)=y (the range of f in our case is simply the interval [f(a),f(b)], or [f(b),f(a)] if f(b)<f(a)). The function which maps y to x is called the inverse of f. This problem can be solved by introducing a new function F(x)=f(x)-y and then finding the zero of F for each y in the range of f. Note that I say the zero here, since f is assumed to be injective and hence the zero is unique. In general the function F need not be linear, so we’ll need a non-linear equation solver to tackle this problem.

To find zeros of a non-linear equation I’ll use the bisection method. Given f and two points l<r such that f changes sign on the open interval (l,r), the bisection method halves the interval and picks a subinterval where f changes sign and repeats. If the function is zero at the midpoint the method stops (otherwise f must change sign on at least one of the two subintervals since f is continuous and hence the intermediate value theorem applies).

When implementing the bisection method we will eventually run out of precision and the interval can no longer be halved. Our implementation checks for this condition first, and bisects only if it is possible. (For simplicity, we always bisect to maximum precision in this implementation instead of allowing an arbitrary precision to be specified. This is fine as long as we’re using fixed precision arithmetic and the function f does not take too long to evaluate.)

> bisect' f l r
>     | m <= l    = l
>     | m >= r    = r
>     | f l * f m < 0 = bisect' f l m
>     | f m * f r < 0 = bisect' f m r
>     | otherwise = m
>     where m  = (l+r)/2

Note that f(l)*f(m)<0 implies that f changes sign on the open interval (l,m) and f(m)*f(r)<0 implies that f changes sign on (m,r).

The function bisect' is guaranteed to find a zero if f changes sign on (l,r). If f does not change sign then it will still return a solution even though there may be none. To fix this problem so that our bisection method only returns a zero if there is one we call this function from a “wrapper” which checks that f changes sign. Also, we make some sanity checks on the endpoints a and b.

> bisect f a b
>     | a > b = bisect f b a
>     | f a * f b < 0 = bisect' f a b
>     | f a == 0 = a
>     | f b == 0 = b
>     | otherwise = error "bisect: failed"

Normally the return value should be wrapped in a Maybe and return Nothing instead of raising an exception in the case where the method fails, but for my purposes I really want the program to halt if there is no solution, hence the use of error.

With bisect in hand we can now easily find the inverse of a continuous and injective function f defined on the closed interval [a,b]:

> inverse f a b y = bisect (\x -> f x - y) a b

Let’s use this to find the inverse of a function f on [0,1] which cannot be inverted “by hand”. Note the f below is injective on this interval, but not on any interval which strictly contains [0,1]. In GHCi:

*Main> let f x = x^2 * abs (tan x)
*Main> let g = inverse f 0 1
*Main> g 1
0.8952060453842319
*Main> f it
1.0
*Main> f (g 0.3)
0.30000000000000004
*Main> it - 0.3
5.551115123125783e-17

That looks good! (Haskell uses double precision floating point, so the last result is zero up to machine epsilon [approx. 10^-16 for double precision].) Note that you have to be careful with the inverse g since it is only defined on the range of f, namely [f(0),f(1)] in this case. At this point it would probably make sense to write some QuickCheck tests, but I’ll stop now anyway.

Coercing the Cocoa text system

I just spent the last couple of days refactoring keyboard input handling in MacVim and thought I’d write down some of my findings here for posterity. I’ve read Apple’s documentation on the Cocoa text system over and over again, but it assumes that you are writing a new Cocoa application from scratch and it doesn’t really cover the case when you are porting an app which already has its own way of dealing with keyboard input. If you are in the latter situation, these notes may be of use to you.

My expectations in MacVim are these: I want to enable the use of different input sources (different keyboard layouts as well as more complex input sources such as Kotoeri) but at the same time I need to pass raw key events (which key was pressed and which modifiers were held?) on to Vim since it does its own processing.

Keyboard input arrives in an NSView derived subclass as follows (by “Cmd keys” I mean keys pressed at the same time as Cmd is held and similarly for Ctrl/Alt/Shift):

1. Cmd and Ctrl keys are sent to performKeyEquivalent: before being passed on to the app menus for key equivalent handling. Note: on Tiger Ctrl keys go directly to keyDown: and (more importantly) if you don’t handle a Cmd key here it will never reach keyDown:. In Leopard Apple fixed this problem: unhandled Cmd key presses (i.e. ones that did not have a menu item bound to them) are sent to keyDown:.The way MacVim handles Cmd key presses on Tiger is to call [[NSApp mainMenu] performKeyEquivalent:event] inside performKeyEquivalent: and if that returns NO send the Cmd key on to Vim and return YES. This way it is possible to bind menu items to key equivalents and let Vim deal with unbound Cmd keys.
2. Next keyDown: is called. Ideally at this stage I’d like to inspect the NSEvent and pass it on to Vim, but doing so would disable input sources like Kotoeri. To give these a chance to respond to the key event you must call interpretKeyEvents:. When this is done, one of the following will happen:
   • insertText: is called with text to insert (in the form of a NSString or a NSAttributedString)
   • doCommandBySelector: is called with a selector whose name indicates what should happen (e.g. insertNewline:) but the selector name can also be noop: (which is meaningless)
   • the current input source swallows the event and tells us to add marked text (e.g. this happens when you press Alt+i on a US keyboard)
   • the input manager swallows the event and nothing happens (e.g. you press Cmd+Alt and some key which was not bound to a menu item)

If this looks complicated, well, that’s because it is! Lets discuss in more detail the things that can happen as a result of calling interpretKeyEvents:.

Normal text

“Normally” insertText: is called with the text to insert, e.g. when you hit a key by itself or with Shift held. This is also the case with most Alt keys (on a US keyboard layout) except for some “dead keys” such as Alt+i and Alt+e. Be careful with the parameter to insertText: — it may be either a NSString or a NSAttributedString. In MacVim I explicitly check for the latter case and extract the string from it (since I can’t support the attributes anyway) as follows:

- (void)insertText:(id)string
{
    if ([string isKindOfClass:[NSAttributedString class]])
        string = [string string];

Note that insertText: may be called with more than one character, e.g. when inserting previously marked text. Typically this happens when you use complex input sources such as Kotoeri. Also, insertText: may be called without any keys being pressed at all. For example, the “Special Characters” palette may be used to insert text (this palette can usually be found on the “Edit” menu) so don’t rely on the current event being a key event inside insertText:.

Key bindings

Keys that have a key binding on the other hand will cause doCommandBySelector: to be called, e.g. Ctrl+[ is by default bound to cancelOperation:. In this situation it is a bit tricky to figure out what to do. One possibility is to do nothing and then back in keyDown: look at the NSEvent object to figure out what to do (e.g. by calling characters on the event) and this may work in most cases. However, there are several cases I know of where it does not work so well.

For example, if you press "Alt+i, Return" then the first press (Alt+i) causes marked text to be added, and the second (Return) will first cause the input manager to call insertText: with the marked text (^) and then doCommandBySelector: is called with the selector insertNewline:. If you inspect the [NSEvent characters] in keyDown: for the event generated by the Return press, it will return ^\x0d and not \x0d as you would expect (i.e. the event contains the result of the Alt+i press as well!). In MacVim I check for certain selectors (e.g. insertNewline:) in doCommandBySelector: and pass an appropriate key on to Vim, but most selectors I ignore and deal with it in keyDown: instead.

Swallowed key events

The problem with the input manager swallowing events is hard to deal with. It can be solved by adding appropriate key bindings but currently there is no public API to modify the key bindings at run time.

For example, Cmd+Alt keys will be blocked, but if you add an entry to the key bindings dictionary with the key "@~" and value noop: (@=Cmd, ~=Alt) then the input manager will pass any Cmd+Alt presses on to doCommandBySelector: with selector noop:. One way to deal with this via Private APIs is to set your own key binding dictionary when initializing your app and make sure your own dictionary contains entries such as "@~" to let key presses through. This is the API you can use to do so:

// Private AppKit API (from class-dump)
@interface NSKeyBindingManager : NSObject
+ (id)sharedKeyBindingManager;
- (id)dictionary;
- (void)setDictionary:(id)arg1;
@end

And here is how to set your own dictionary (assuming dict has been populated with your own key bindings already):

NSKeyBindingManager *mgr =
    [NSKeyBindingManager sharedKeyBindingManager];
[mgr setDictionary:dict];

I have yet to find any problems caused by this, but try it at your own risk. One thing to note is that your custom key bindings dictionary should contain most (if not all) of the bindings found in the system default key bindings dictionary

/System/Library/Frameworks/AppKit.framework
            /Resources/StandardKeyBinding.dict

else keyboard navigation may not work in dialogs since they rely on these standard bindings (e.g. forget to bind Return to insertNewline: and you won't be able to use Return to dismiss dialogs).

The unexpected Ctrl+q

Another gotcha I came across in my investigations was that Ctrl+q always seemed to be swallowed by the input manager and then the next keystroke would get mangled in one way or another. The problem turned out to be a User Default called NSQuotedKeystrokeBinding. By default this is set to "^q" (Ctrl+q) and is used to literally enter keys that would otherwise be interpreted by the input manager. Hence, if you ever want to receive any Ctrl+q presses this needs to be disabled, which fortunately is easy using a little bit of Core Foundation:

CFPreferencesSetAppValue(
        CFSTR("NSQuotedKeystrokeBinding"),
        CFSTR(""),
        kCFPreferencesCurrentApplication);

This should be called in the initialization of your application.

Marked text

Apple is a bit vague on how to support marked text handling in custom views. Basically, they say you should implement the NSTextInput protocol but then they don't exactly explain how this is done.

One method that seems to work well is to keep a NSString and a NSRange in your custom view and whenever setMarkedText:selectedRange: is called you update your marked text and range variables. Occasionally the input manager will ask if there is any marked text and what the selected range is by calling markedText and markedRange. When the user finishes entering marked text (e.g. by hitting Enter in Kotoeri manager), the input manager calls insertText: to let you know that it is finished with the current marked text entry. As a result you should always clear you local marked text and range variables. Note that the input manager almost never explicitly calls unmarkText to unmark the text, which is why you need to do the unmarking manually in insertText:.

Command keys

When a Cmd key press reaches keyDown: I ideally would like to know which key was pressed and which modifiers were held but there is a problem here in that Cocoa sometimes will add the modifiers into the key and sometimes not. This turns into a game as to whether to extract characters or charactersIgnoringModifiers from the NSEvent and trying to guess which of the flags in modifierFlags have already been included in the event.

This is already turning into one massive post so let me just summarize the heuristic I finally settled on:

• If Shift and/or Alt is held, then use charactersIgnoringModifiers, otherwise use characters
• The Shift flag is always included in the key so clear it from modifierFlags. The Alt flag should only be cleared if the Ctrl flag is set as well.

Note that I could not find any (reasonably easy) way of extracting which unmodified key on the physical keyboard was pressed. Even though the method is called charactersIgnoringModifiers it will some times include the modifier flags (e.g. Shift, Alt) and sometimes it won't.

MacVim Services

Many people probably never use the “Services” item that appears on the application menu in every Mac OS X application. At least I never used to, and for two reasons: I didn’t even know it existed for a long time and then when I did learn about it I could never be bothered navigating through all those submenus. I’ve since found a good way to actually use the Services menu, namely via Mac OS X’s ability to customize keyboard shortcuts for any menu item in any application.

Consider the MacVim service “Open Document Containing Selection” (phew). With it you can select some text in (almost) any application, run the service and a new MacVim window will open up with the selected text. Using the Services menu to do this would take a lot more time then to simply ⌘C, switch to MacVim, ⌘N, then ⌘V but by assigning your own keyboard shortcut to this service it actually becomes useful.

Here’s how to assign ⌃⌥⌘V to this service (yes, that’s a lot of keys, but at least it’s unlikely to be assigned to some other menu and it is not too awkward to type):

1. Click the Apple Menu
2. Choose “System Preferences…”
3. Click “Keyboard & Mouse”
4. Click the “Keyboard Shortcuts” tab
5. Click “+” button in the bottom left corner
6. In the sheet that pops down, choose “All Applications” from the drop down menu
7. In the text box next to “Menu Title” enter “New Document Containing Selection” (double-check for typos or the shortcut won’t work)
8. Click the edit box next to “Keyboard Shortcut” and hold down Control, Option, Command and v at the same time, then click the “Add” button

Now try it out! For example open Safari, select some text, and hit ⌃⌥⌘V. If it does not work then you have most likely misspelled the menu item in step 7, or you have chosen a shortcut that is already in use (⌃⌥⌘V worked in Safari for me). Finding a shortcut that works across all applications can be kind of frustrating and sometimes you have to restart an application before it will notice a change to the shortcut.

Another tip is to assign a shortcut to the “New Document Here” service for Finder only (choose “Finder” instead of “All Applications” from the drop down menu in step 6 and enter “New Document Here” in step 7). Using that shortcut will open a new MacVim window and the current directory will be set to whatever folder you are currently browsing in the Finder. I often use this to create a new document on the Desktop by clicking the Desktop, hitting the shortcut, enter some text, then hit ⌘S and enter a file name. Give it a try.

A minimal Vim configuration

I have seen plenty of people describing how they trick out Vim with fancy plugins and (relatively) large rc-files. What I want to do is to point out what I consider a minimal setup that allows me to use Vim without going insane.

MacVim comes with a few default settings that other Vim ports lack. If you are not using MacVim I highly suggest you create a ~/.vimrc file and add these three lines:

set nocp
set bs=indent,eol,start
syntax on

With that out of the way, lets get started. First of all, you will need to create the file ~/.gvimrc unless you have already done so. To do this, open Vim and enter :e ~/.gvimrc (you may use ~/.vimrc if you prefer, but some of the options below only make sense in the GUI so you may as well stick with ~/.gvimrc unless you have a good reason not to).

These are the options that I consider essential:

Turn off the blinking cursor in normal mode:

set gcr=n:blinkon0

The blinking cursor kind of stresses me out so it is nice to have normal mode as a sort of haven away from insert mode. This may also work as encouragement not to stay in insert mode too much for those who are new to Vim. (Replace with set gcr=a:blinkon0 if you want the blinking to stop altogether!)

Enable search-related options: highlight matches in a search (hls), show the current matching pattern as you search (is), ignore case (ic) unless you are searching for both upper and lowercase letters (scs). The second line adds the mapping Ctrl+n to quickly disable the currently highlighted search term (using the command :noh):

set hls is ic scs
nmap <silent> <C-n> :noh<CR>

The Ctrl+n mapping only works in normal mode, see :h map-modes.

Enable automatic file type detection:

filetype plugin indent on

Each time a recognized file type is opened this option will cause Vim to set several other options to ease editing of that particular type of file.

Use 4 spaces for indentation and replace tabs with spaces in a smart way:

set sw=4 sts=4 et

Choose whichever number of spaces you prefer for indentation by replacing 4 with the number of your choosing.

Yep, that’s really all that I think is necessary but let me still list a few more settings that almost made it on that list:

Hide the toolbar:

set go-=T

Maybe one day the toolbar will be useful for something, but right now it isn’t and with it gone you’ll be able to fit at least another line of text on your monitor.

Show the cursor line and column number:

set ruler

The scrollbar is a great visual indication as to where you are in the file but I still find this option very useful.

Increase the default number of lines:

set lines=35

I use this as a sensible default for quick edits and if I start editing in earnest I have a tendency to hit Cmd+Ctrl+z to maximize the window (MacVim only).

Use a dark background: In MacVim the default color scheme’s dark variant is quite nice:

set bg=dark

For other GUIs you’ll need to find a nice dark scheme and use the :colorscheme command (see :h colorscheme). I use dark color schemes since they tend to be much easier on the eyes. (In MacVim black backgrounds can make it hard to distinguish overlapping editor windows (because windows have no borders on Mac OS X) so I often add the line hi Normal guibg=Grey8 to make the background almost-but-not-completely black.)

One final comment; I do not use hidden buffers when editing (which means the undo history is lost when a buffer is hidden). Instead I open separate tabs for each file that I am currently editing. This works well when editing only a handful of files at a time but if you need to edit a lot of files at the same time you may want to take a look at the hidden option (see :h 'hid).