Handy F# snippets


Answers

Multi-Line Strings

This is pretty trivial, but it seems to be a feature of F# strings that is not widely known.

let sql = "select a,b,c \
           from table \
           where a = 1"

This produces:

val sql : string = "select a,b,c from table where a = 1"

When the F# compiler sees a back-slash followed by a carriage return inside a string literal, it will remove everything from the back-slash to the first non-space character on the next line. This allows you to have multi-line string literals that line up, without using a bunch of string concatenation.

Question

There are already two questions about F#/functional snippets.

However what I'm looking for here are useful snippets, little 'helper' functions that are reusable. Or obscure but nifty patterns that you can never quite remember.

Something like:

open System.IO

let rec visitor dir filter= 
    seq { yield! Directory.GetFiles(dir, filter)
          for subdir in Directory.GetDirectories(dir) do 
              yield! visitor subdir filter} 

I'd like to make this a kind of handy reference page. As such there will be no right answer, but hopefully lots of good ones.

EDIT Tomas Petricek has created a site specifically for F# snippets http://fssnip.net/.




Code-golf: generate pascal's triangle

J, another language in the APL family, 9 characters:

p=:!/~@i.

This uses J's builtin "combinations" verb.

Output:

   p 10
1 1 1 1 1  1  1  1  1   1
0 1 2 3 4  5  6  7  8   9
0 0 1 3 6 10 15 21 28  36
0 0 0 1 4 10 20 35 56  84
0 0 0 0 1  5 15 35 70 126
0 0 0 0 0  1  6 21 56 126
0 0 0 0 0  0  1  7 28  84
0 0 0 0 0  0  0  1  8  36
0 0 0 0 0  0  0  0  1   9
0 0 0 0 0  0  0  0  0   1



Elegant Snippets of F#

My favorite is recursively listing all files under a folder in a four-line sequence expression:

open System.IO

let rec filesUnderFolder basePath =
    seq {
        for file in Directory.GetFiles(basePath) do
            yield file
        for subDir in Directory.GetDirectories(basePath) do
            yield! filesUnderFolder subDir
        }






Haskell, 58 characters:

r 0=[1]
r(n+1)=zipWith(+)(0:r n)$r n++[0]
p n=map r[0..n]

Output:

*Main> p 5
[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1],[1,5,10,10,5,1]]

More readable:

-- # row 0 is just [1]
row 0     = [1]
-- # row (n+1) is calculated from the previous row
row (n+1) = zipWith (+) ([0] ++ row n) (row n ++ [0])
-- # use that for a list of the first n+1 rows
pascal n  = map row [0..n]



It's true but not useful to observe that any collection of mutually recursive functions can be turned into a tail-recursive function. This observation is on a par with the old chestnut fro the 1960s that control-flow constructs could be eliminated because every program could be written as a loop with a case statement nested inside.

What's useful to know is that many functions which are not obviously tail-recursive can be converted to tail-recursive form by the addition of accumulating parameters. (An extreme version of this transformation is the transformation to continuation-passing style (CPS), but most programmers find the output of the CPS transform difficult to read.)

Here's an example of a function that is "recursive" (actually it's just iterating) but not tail-recursive:

factorial n = if n == 0 then 1 else n * factorial (n-1)

In this case the multiply happens after the recursive call. We can create a version that is tail recursive by putting the product in an accumulating parameter:

factorial n = f n 1
   where f n product = if n == 0 then product else f (n-1) (n * product)

The inner function f is tail-recursive and compiles into a tight loop.


I find the following distinctions useful:

  • In an iterative or recursive program, you solve a problem of size n by first solving one subproblem of size n-1. Computing the factorial function falls into this category, and it can be done either iteratively or recursively. (This idea generalizes, e.g., to the Fibonacci function, where you need both n-1 and n-2 to solve n.)

  • In a recursive program, you solve a problem of size n by first solving two subproblems of size n/2. Or, more generally, you solve a problem of size n by first solving a subproblem of size k and one of size n-k, where 1 < k < n. Quicksort and mergesort are two examples of this kind of problem, which can easily be programmed recursively, but is not so easy to program iteratively or using only tail recursion. (You essentially have to simulate recursion using an explicit stack.)

  • In dynamic programming, you solve a problem of size n by first solving all subproblems of all sizes k, where k<n. Finding the shortest route from one point to another on the London Underground is an example of this kind of problem. (The London Underground is a multiply-connected graph, and you solve the problem by first finding all points for which the shortest path is 1 stop, then for which the shortest path is 2 stops, etc etc.)

Only the first kind of program has a simple transformation into tail-recursive form.




Tags