Infix function trick for F#

by sandersn 22. October 2009 01:15

One of the nice things about Haskell is that you can "infix" any function by surrounding it with backquotes. This helps a lot with certain functions, either because they look like verbalised math operators, or because they just look like bedraggled OO escapees that want to appear after their subject. Examples:

Just 12 `mplus` Just 34 `mplus` mzero
-- much nicer than:
mplus (Just 12) (mplus (Just 34) mzero)

"foo" `isPrefixOf` "foonly2000"
-- much nicer than
isPrefixOf "foo" "foonly2000"

And of course if you don't feel like it, you don't have to. The choice is yours. Today I discovered how to replicate this choice without syntactic support from the language. This is important, because F# doesn't provide infixing syntax.

The trick is pretty simple. I'll Seq.append to demonstrate:

let l = [1..100]
Seq.take 49 l |> Seq.append <| Seq.skip 51 l

The key is the "pipeline operator", which is a corny name for "reverse apply". All it is is this:

let (|>) a f = f a

But it's super popular in F# because of two things:

  1. Using it a lot emulates the structure of dot-syntax OO code
     l |> skip 2 |> take 4 |> printfn "%A")
  2. It encourages you to write left-to-right, top-to-bottom code instead of functional style's upside-down inside-out side-to-side and round-about. This really helps out F#'s type inferencer, which gets confused any time it has to infer OO code. If you use a method near the end of a chain, it has a better chance of inferring the type from a function you called on it earlier in the chain.

But nobody uses "reverse pipeline" in F#, which is a reverse corny name for "apply". It does come pre-defined:

let (<|) f a = f a

(In Haskell, where it's much more popular, it's f $ a = f a)

In fact, if you look at the definition, you may wonder if it does ANYTHING. It's actually very common in Haskell, used to eliminate parentheses. The reason this works is that function call has highest precedence in Haskell and F#, so everything else is lower, usually a lot lower. So instead of this:

Seq.append (Seq.take 49 l) (Seq.skip 51 l)

You can write this:

Seq.append (Seq.take 49 l) <| Seq.skip 51 l

F# groups Seq.append (Seq.take 49 l) separately from Seq.skip 51 l because of the lower precedence of (<|)

Now just repeat the same trick with pipeline to get rid of the set of parentheses around Seq.take:

Seq.take 49 l |> Seq.append <| Seq.skip 51 l

And suddenly, not only did you get rid of the parentheses, you've infixed Seq.append!

Of course if you're really addicted to Haskell, you could just write

let (++) = Seq.append

But this lets you infix, or not, depending on what reads the best.

Disclaimer: I haven't tested this extensively with type inferencing. Using this trick may lead to a lot more type annotations being required.

Tags: , , ,

Programming

Comments (6) -

JoshuaHerring
JoshuaHerring
10/26/2009 9:29:51 AM #

DISCLAIMER: I have never even seen an F# program before reading this blog, so please excuse my ignorance.&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
It seems like this doesn&amp;amp;amp;amp;amp;#39;t really get the intended behavior on longer sequences.  &amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
a arg / b arg \\ c arg / d arg \\ e arg&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
translates to what?  If your trick succeeds because (a) function application is given highest priority and (b) the |&amp;amp;amp;amp;amp;gt; operator is just another form of function application, then won&amp;amp;amp;amp;amp;#39;t stringing these things along mess up the normal parsing order?  That is, it comes out:&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
(b a (c d)) e&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
Rather than &amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
b (a ((c d) e))&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
?&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
Otherwise, very clever.  Or, of course, if I&amp;amp;amp;amp;amp;#39;ve just displayed my ignorance, more clever still.&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
(I used CCG notaion rather than F# notation because your html filter was filtering out the F#...)

Nathan Sanders
Nathan Sanders
10/26/2009 9:37:49 PM #

This is also works in OCaml (a very nice functional programming language), so if you can still log in to jones, then you can follow along with my example by running  it in ocaml.&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
If you also define&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
# let left a _ = a;;&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
# let (a,b,c) = ([1;2], [3;4], [5;6]);;&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
Then:&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
# a |&amp;amp;amp;amp;amp;amp;gt; app &amp;amp;amp;amp;amp;amp;lt;| b |&amp;amp;amp;amp;amp;amp;gt; left &amp;amp;amp;amp;amp;amp;lt;| c;;&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
- : int list = [1; 2; 3; 4]&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
In CCG-esque notation:&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
a / app \\ b / left \\ c&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
It&amp;amp;amp;amp;amp;#39;s evaluated the same way as&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
The reason this works is that symbolic functions, so-called &amp;amp;amp;amp;amp;quot;operators&amp;amp;amp;amp;amp;quot; (I can&amp;amp;amp;amp;amp;#39;t remember who calls them this), have really really low precedence and left-to-right evaluation. It&amp;amp;amp;amp;amp;#39;s customisable in Haskell, although I don&amp;amp;amp;amp;amp;#39;t know how to do it in F#.&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
Anyway, the transformation happens left-to-right, so you properly get&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
left (app a b) c&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
from that last infix line.&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
The evaluation of&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
a / app \\ b / left \\ c&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
should follow the re-ordering.&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
(app \\ b / left \\ c) a&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
(app b / left \\ c) a&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
((left \\ c) app b) a&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
((left c) app b) a&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
Oops. Um, what if we did it right-to-left?&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
a / app \\ b / left c&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
left c (a / app \\ b)&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
left c (a / app b)&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
left c (app b a)&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
This is close except that it reverses the order of the arguments. Hm. I&amp;amp;amp;amp;amp;#39;ll have to take a closer look.

JoshuaHerring
JoshuaHerring
10/27/2009 8:36:50 AM #

If they have equal precedence it makes sense, though, which they should, actually, since they&amp;amp;amp;amp;amp;#39;re both defined functions.&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
In that case, the transformation goes like this:&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
a / app \\ b / left \\ c&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
(app a) \\ (b / left \\ c)&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
(app a) \\ ((left b) \\ c )&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
(app a) \\ ((left b) c)&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
(app a)((left b) c)&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
Typing that into OCaml (a very nice functional programming language), and I get [1;2;3;4], as I should.&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
Swapping app for right &amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
(# let right a b = b;;)&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
of course you get [3;4], so I think this is the right transformation.  In which case, I have to take back my earlier comment: it works for longer chains.

JoshuaHerring
JoshuaHerring
10/27/2009 8:58:08 AM #

Of course I&amp;amp;amp;amp;amp;#39;m a bonehead.  I mean \\ has higher precedence than /, both of which seem to have higher precedence than normal function application.&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
Some more evidence:&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
right right left / right \\ b / left \\ c&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
returns [3;4]&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
right right left / left \\ b / left \\ c&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
returns &amp;amp;amp;amp;amp;#39;_a-&amp;amp;amp;amp;amp;gt;&amp;amp;amp;amp;amp;#39;_b-&amp;amp;amp;amp;amp;gt;&amp;amp;amp;amp;amp;#39;_a = function (aka left)&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
right right left / left \\ b / left \\ c&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
((right right) left) / left \\ b / left \\ c&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
(left ((right right) left) \\ b / left \\ c&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
(left ((right right) left) \\ ((left b) c)&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
(left ((right right) left )((left b) c)&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;

Nathan Sanders
Nathan Sanders
10/28/2009 11:15:29 PM #

Using Ocaml&amp;amp;amp;amp;amp;#39;s Very Nice Functional ability to insert side-effects anywhere, redefine apply and reverse-apply like this:&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
open Printf;; (* only needed in Ocaml, not F# *)&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
let (/) a f = (printf &amp;amp;amp;amp;amp;quot;rev\\n&amp;amp;amp;amp;amp;quot;; f a);;&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
let (\\) f a = (printf &amp;amp;amp;amp;amp;quot;app\\n&amp;amp;amp;amp;amp;quot;; f a);;&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
a / left \\ b then prints &amp;amp;amp;amp;amp;quot;rev app&amp;amp;amp;amp;amp;quot; and returns [1;2].&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
Furthermore, &amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
let (//) a f = (printf &amp;amp;amp;amp;amp;quot;rev2\\n&amp;amp;amp;amp;amp;quot;; f a);;&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
let (\\\\) f a = (printf &amp;amp;amp;amp;amp;quot;app2\\n&amp;amp;amp;amp;amp;quot;; f a);;&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
Then evaluating&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
a // left \\\\ b / left \\ c&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
prints &amp;amp;amp;amp;amp;quot;rev2 app2 rev app&amp;amp;amp;amp;amp;quot; and returns [1;2].&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
So it appears that evaluation proceeds as follows (in the imaginary world where OCaml uses normal-order evaluation*):&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
a / left \\ b / left \\ c&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
(left a) \\ b / left \\ c&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
(left a b) / left \\ c&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
(left (left a b) \\ c)&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
(left (left a b) c)&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
then...&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
(left a b)&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
a&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
The secret is that infix functions stop parsing before the next infix function. I think. Let&amp;amp;amp;amp;amp;#39;s try it on your last example:&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
right right left / left \\ b / left \\ c&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
right right (left / left \\ b / left \\ c) &amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
right right (left left) \\ b / left \\ c&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
right right (left left b) / left \\ c&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
right right (left (left left b)) \\ c&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
right right (left (left left b) c)&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
-- start reducing --&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
right right (left left b)&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
right right left&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
left&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
You could also cheat and evaluate outermost right ahead of time --&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
left / left \\ b / left c&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
And now we have exactly my simpler example above, except that the final answer is left instead of a.&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
Compare to the pure prefix&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
right right a bunch of other prefix functions&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
which is parsed as&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
(((((((right right) a) bunch) of) other) prefix) functions)&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
I still haven&amp;amp;amp;amp;amp;#39;t completely convinced myself.&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
*2008 Audience Favourite, Best Evaluation Order for Functional Languages.

Robert Nielsen
Robert Nielsen
7/18/2010 3:55:05 PM #

Nice trick; thanks!&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
Now there even is official documentation stating the F# pipeline operator precedence and associativity.&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
&amp;amp;amp;amp;amp;lt;br /&amp;amp;amp;amp;amp;gt;
msdn.microsoft.com/en-us/library/dd233228.aspx .

Add comment

  Country flag

biuquote
  • Comment
  • Preview
Loading