Did it with .NET - I'm Really Digging F#

Friday, October 26, 2007

Lately, I've been spending some quality time with Microsoft's F# language. So far, I'm completely enamored with the brevity and clarity of the language. It just feels right to me.

I recently wrote up some articles on how one might use currying, partial application and function composition along with C# and delegates to produce the factorial function from two higher-order functions. The result of this labor is below.

static void Main()

{

  var reduce = HigherOrder.GetReduce<Int64>().Curry();

  var getProduct = reduce((x, y) => x * y)(1);

  var sequence = HigherOrder.GetSequence<Int64>().Curry();

  var naturalsFromOne = sequence(x => ++x)(1);

  var equals = HigherOrder.GetEquals<Int64>().Curry();

  var naturalsFromOneToX = HigherOrder.Compose(equals, naturalsFromOne);

  var factorial = HigherOrder.Compose(naturalsFromOneToX, getProduct);

  var factorialOf10 = factorial(10);

  Console.WriteLine("Factorial of 10 is {0:#,#}", factorialOf10);

}

That code is a truly magnificent beast. While it's academically interesting to torture delegates like this, it isn't all that fruitful when the language (i.e. C#, VB) doesn't really support these shenanigans. Try that in some production code and see how quickly you lose your development job.

As an exercise, here's how I might build factorial using the same techniques in F#:

#light

let getProduct = Seq.fold ( * ) 1

let naturalsFromOneToX n = [1 .. n]

let factorial = naturalsFromOneToX >> getProduct

printf "Factorial of 10 is %i" (factorial 10)

The first thing I should point out is that no delegates are used in this sample. F# natively supports functions as values so it's unnecessary to create delegates for them (and no, it doesn't create delegates under the covers). Secondly, functions are automatically curried in F#. You can declare functions so that they aren't curried, but that's really only useful if you're writing code that should be callable from other .NET languages. And finally, F# provides an operator (>>) for function composition.

To be fair, I should point out that the above implementation is pretty naive. It's not necessary to use function composition. This will suffice:

#light

let factorial n = Seq.fold ( * ) 1 [1 .. n]

printf "Factorial of 10 is %i" (factorial 10)

If compiled with fsc.exe, that code will print the following to the console:

Factorial of 10 is 3628800

That's great, but what if I try to calculate the factorial of 1000?

Factorial of 1000 is 0

Hmmm... what's going on here? Well, it turns out that the F# compiler inferred the type of "factorial" to be:

val factorial : int -> int

"int" maps to the standard .NET type, System.Int32, so this factorial function expects an Int32 and returns an Int32. However, Int32 isn't actually large enough to hold the factorial of 1000. This is a job for F#'s "bigint" type. "bigint" maps to the Microsoft.FSharp.Math.Types.BigInt type which can represent arbitrarily large integer values. With a few minor modifications, the factorial function can use "bigint," and the factorial of 1000 can be properly calculated.

#light

let factorial n = Seq.fold ( * ) 1I [1I .. n]

printf "Factorial of 1000 is %A" (factorial 1000I)

Now, the F# compiler infers the type of "factorial" to be:

val factorial : bigint -> bigint

And what does that program print to the console?

Factorial of 1000 is 40238726007709377354370243392300398571937486421071463254379

99104299385123986290205920442084869694048004799886101971960586316668729948085589

01323829669944590997424504087073759918823627727188732519779505950995276120874975

46249704360141827809464649629105639388743788648733711918104582578364784997701247

66328898359557354325131853239584630755574091142624174743493475534286465766116677

97396668820291207379143853719588249808126867838374559731746136085379534524221586

59320192809087829730843139284440328123155861103697680135730421616874760967587134

83120254785893207671691324484262361314125087802080002616831510273418279777047846

35868170164365024153691398281264810213092761244896359928705114964975419909342221

56683257208082133318611681155361583654698404670897560290095053761647584772842188

96796462449451607653534081989013854424879849599533191017233555566021394503997362

80750137837615307127761926849034352625200015888535147331611702103968175921510907

78801939317811419454525722386554146106289218796022383897147608850627686296714667

46975629112340824392081601537808898939645182632436716167621791689097799119037540

31274622289988005195444414282012187361745992642956581746628302955570299024324153

18161721046583203678690611726015878352075151628422554026517048330422614397428693

30616908979684825901254583271682264580665267699586526822728070757813918581788896

52208164348344825993266043367660176999612831860788386150279465955131156552036093

98818061213855860030143569452722420634463179746059468257310379008402443243846565

72450144028218852524709351906209290231364932734975655139587205596542287497740114

13346962715422845862377387538230483865688976461927383814900140767310446640259899

49022222176590433990188601856652648506179970235619389701786004081188972991831102

11712298459016419210688843871218556461249607987229085192968193723886426148396573

82291123125024186649353143970137428531926649875337218940694281434118520158014123

34482801505139969429015348307764456909907315243327828826986460278986432113908350

62170950025973898635542771967428222487575867657523442202075736305694988250879689

28162753848863396909959826280956121450994871701244516461260379029309120889086942

02851064018215439945715680594187274899809425474217358240106367740459574178516082

92301353580818400969963725242305608559037006242712434169090041536901059339838357

77939410970027753472000000000000000000000000000000000000000000000000000000000000

00000000000000000000000000000000000000000000000000000000000000000000000000000000

00000000000000000000000000000000000000000000000000000000000000000000000000000000

00000000000000000000000000000I

Awesome.

One last point: writing factorial in F# is completely unnecessary. It already exists.

#light

open Microsoft.FSharp.Math.BigInt

printf "Factorial of 1000 is %A" (factorial 1000I)

C# | F# | Functional Programming | Quality Code

posted on Friday, October 26, 2007 3:02:36 PM (Eastern Standard Time, UTC-05:00)

Comments [3]

Saturday, October 27, 2007 7:46:56 PM (Eastern Standard Time, UTC-05:00)

It would be nice to see the C# code that Reflector shows for:
let factorial n = Seq.fold ( * ) 1I [1I .. n]

Dan

Tuesday, October 30, 2007 7:32:49 AM (Eastern Standard Time, UTC-05:00)

You should take a look at OCaml. It's cross-platform and the inspiration for F#. It also has one of the most optimized compilers on the planet.

Jeff

Monday, November 05, 2007 1:43:43 PM (Eastern Standard Time, UTC-05:00)

@Dan,

The F# statement:

let factorial n = Seq.fold ( * ) 1I [1I .. n]

Reflects in C# as:

public static BigInt factorial(BigInt n)
{
BigInt num = BigIntModule.of_string("1");
BigInt num2 = n;
return Seq.fold<BigInt, BigInt, List<BigInt>>(new factorial@1(), BigIntModule.of_string("1"), Seq.to_list<IEnumerable<BigInt>, BigInt>(BigInt.op_Range(num, num2)));
}

When you use Reflector on an F# assembly, it requests the binding for fslib, the primary assembly for the F# language. The collateral for BigInt, Seq (with Seq.Fold), etc. are in fslib.

@Dustin - I've been a believer in F# for some time now. Love this post.

---O

optionsScalper

Comments are closed.