Streamline Your Vector Algebra With F#

by Marc Sigrist 21. March 2015 17:29

This blog post explains five F#-specific features who simplify and stabilize the implementation of vector algebra:

We will use these features to define an infix dot product operator who is compile-time type-safe and generic.

 

Dot Product Operator Implementation

let inline (.*) xs ys = Seq.map2 (*) xs ys |> Seq.sum

The above line of code does not contain any type annotations. However, thanks to the F# compiler's built-in Hindley-Milner type inference algorithm with automatic generalization, the code is compiled with the following strongly typed signature:

val inline (.*) :
    xs:seq< ^a> -> ys:seq< ^b> -> ^c
    when (^a or ^b) : (static member (*) : ^a * ^b -> ^c) and
         ^c         : (static member (+) : ^c * ^c -> ^c) and
         ^c         : (static member get_zero : unit -> ^c)

The inline keyword lets the compiler inline the operation's implementation body at the call site, where the types of arguments are well-known. As a consequence, the types of the operation's parameters and result can be resolved statically (i.e., at compile time) according to the contexts of different kinds of call sites. You can recognize such types by the prefix ^ in the statically resolved type parameters (also called head-type parameters) of the inferred signature. Any combination of arguments can be passed to the operation, as long as they satisfy the following constraints:

  • The first (left-hand side) argument must be a sequence of ^as.
  • The second (right-hand side) argument must be a sequence of ^bs.
  • Either the type of ^a, or the type of ^b, must implement a * operator who returns an instance of ^c.
  • The type of ^c must implement a + operator and must have a zero representation.

Any numeric primitive type satisfies the constraints for ^a, ^b, and ^c. You can also define your own compatible F# types (records, unions, classes, structs, or interfaces). Another alternative is to use built-in numeric types together with units of measure, which we are going to demonstrate next.

 

Example 1: Calculate an area

This example uses the m (metre) unit of measure predefined in the FSharp.Core library.

open Microsoft.FSharp.Data.UnitSystems.SI.UnitSymbols

let lengths = [3<m>; 5<m>] // a list of integer metre values
let widths = [4<m>; 2<m>] // another list of integer metre values
let area = lengths .* widths // 22 square metres, typed as 22<m ^ 2>

Example 2: Calculate Speed

This example uses the m (metre) and s (second) units of measure predefined in the FSharp.Core library.

let durations = [10.3<s>; 4.25<s>] // a list of float second values
let accelerations = [3.1<m/s^2>; 4.2<m/s^2>] // a list of float "m per square second" values
let speed = durations .* accelerations // 49.78 metres per second, typed as 49.78<m/s>

Example 3: Calculate Portfolio Value

This example uses custom units of measure.

[<Measure>] type CHF
[<Measure>] type EUR

let quantities = [17M; 12M; 14M] // a list of decimal values
let pricesEUR = [3.75M<EUR>; 4.8M<EUR>; 2.5M<EUR>] // a list of decimal Euro values
let exRate = 1.0542M<CHF/EUR> // a decimal "Swiss Franc per Euro" exchange rate

let totalEUR = quantities .* pricesEUR // 156.35 Euro, typed as 156.35M<EUR>
let totalCHF = totalEUR * exRate // 164.82417 Swiss Francs, typed as 164.824170M<CHF>

Conclusion

Writing just a single line of code, we have defined an operation, with compile-time type safety, for calculating dot products in different domains such as areas, speeds, or portfolio values. The DRY principle (don't repeat yourself) is usually associated with mainstream OO-first languages such as C# or Java. However, the functional-first language F# lets you apply the principle more consequently, without sacrificing OO.

Tags:

F#

Fibonacci Variations, Part 1: A Library-Based Infinite Sequence

by Marc Sigrist 28. February 2015 23:37

This is the first part of an intermittent series of articles about calculating Fibonacci numbers in F#. Each article will present a different kind of implementation. Where available, I will also show a corresponding implementation in C#.

Step 1: Specification

To be truly infite, the sequence has to satisfy three conditions:

  1. it has to be lazy, i.e., the numbers are not cached, but continually generated,
  2. the type of number must not have an upper boundary, and
  3. the algorithm must never cause a stack overflow.

(Theoretically, for extremely large numbers—say, numbers with billions of digits—we would have to add a fourth condition in order to avoid OutOfMemoryExceptions: That the type of number do not keep all digits in memory at once, but somehow produce each digit on-demand. The creation of such a type, and especially its algebraic operators, poses an interesting challenge, but goes beyond the scope of this article.)

 

Step 2: Implementation

let fibs =
    (0I, 1I) 
    |> Seq.unfold (fun (x, y) -> let z = x + y in Some(z, (y, z))) 
    |> Seq.append [0I; 1I]

In F#, The suffix I is a pre-defined marker for literal numbers of type bigint, which maps to the .NET type System.Numerics.BigInteger, representing an arbitrarily large integer number. Thanks to this marker, the F# compiler infers the type of fibs as seq<System.Numerics.BigInteger>. Note that it is also possible to define custom numeric literals in F# (see section 6.3.1 Simple Constant Expressions in the F# 3.0 language specification).

This is all the code you need in F# to create an infinite sequence of Fibonacci numbers. We start from an initial state of zero and one, represented as the tuple (0I, 1I). This is passed to the library function Seq.unfold and is processed in our lambda function as (x, y). Then, both the next number z and the next state (y, z) are generated and returned as a nested tuple (z, (y, z)) inside Some. Some is an option instance. It signals that the number generation shall continue. If we returned None instead, the number generation would stop. However, this algorithm only works from the third Fibonacci number onwards. Therefore, the first two resulting numbers have to be "hard-coded" by inserting [0I; 1I] before the other numbers.

There is no corresponding C# implementation, because the standard .NET libraries do not cointan a method for unfolding. (There is only System.Linq.Enumerable.Aggregate, which is similar to Seq.fold in F#.)

Step 3: Application

Let's print the first 400 Fibonacci numbers:

fibs
|> Seq.take 400
|> Seq.iteri (printfn "fib %3i = %A")

This produces...

fib   0 = 0
fib   1 = 1
fib   2 = 1
fib   3 = 2
fib   4 = 3
fib   5 = 5
fib   6 = 8
fib   7 = 13
fib   8 = 21
fib   9 = 34
fib  10 = 55
fib  11 = 89
fib  12 = 144
fib  13 = 233
fib  14 = 377
fib  15 = 610
fib  16 = 987
fib  17 = 1597
fib  18 = 2584
fib  19 = 4181
fib  20 = 6765
fib  21 = 10946
fib  22 = 17711
fib  23 = 28657
fib  24 = 46368
fib  25 = 75025
fib  26 = 121393
fib  27 = 196418
fib  28 = 317811
fib  29 = 514229
fib  30 = 832040
fib  31 = 1346269
fib  32 = 2178309
fib  33 = 3524578
fib  34 = 5702887
fib  35 = 9227465
fib  36 = 14930352
fib  37 = 24157817
fib  38 = 39088169
fib  39 = 63245986
fib  40 = 102334155
fib  41 = 165580141
fib  42 = 267914296
fib  43 = 433494437
fib  44 = 701408733
fib  45 = 1134903170
fib  46 = 1836311903
fib  47 = 2971215073
fib  48 = 4807526976
fib  49 = 7778742049
fib  50 = 12586269025
fib  51 = 20365011074
fib  52 = 32951280099
fib  53 = 53316291173
fib  54 = 86267571272
fib  55 = 139583862445
fib  56 = 225851433717
fib  57 = 365435296162
fib  58 = 591286729879
fib  59 = 956722026041
fib  60 = 1548008755920
fib  61 = 2504730781961
fib  62 = 4052739537881
fib  63 = 6557470319842
fib  64 = 10610209857723
fib  65 = 17167680177565
fib  66 = 27777890035288
fib  67 = 44945570212853
fib  68 = 72723460248141
fib  69 = 117669030460994
fib  70 = 190392490709135
fib  71 = 308061521170129
fib  72 = 498454011879264
fib  73 = 806515533049393
fib  74 = 1304969544928657
fib  75 = 2111485077978050
fib  76 = 3416454622906707
fib  77 = 5527939700884757
fib  78 = 8944394323791464
fib  79 = 14472334024676221
fib  80 = 23416728348467685
fib  81 = 37889062373143906
fib  82 = 61305790721611591
fib  83 = 99194853094755497
fib  84 = 160500643816367088
fib  85 = 259695496911122585
fib  86 = 420196140727489673
fib  87 = 679891637638612258
fib  88 = 1100087778366101931
fib  89 = 1779979416004714189
fib  90 = 2880067194370816120
fib  91 = 4660046610375530309
fib  92 = 7540113804746346429
fib  93 = 12200160415121876738
fib  94 = 19740274219868223167
fib  95 = 31940434634990099905
fib  96 = 51680708854858323072
fib  97 = 83621143489848422977
fib  98 = 135301852344706746049
fib  99 = 218922995834555169026
fib 100 = 354224848179261915075
fib 101 = 573147844013817084101
fib 102 = 927372692193078999176
fib 103 = 1500520536206896083277
fib 104 = 2427893228399975082453
fib 105 = 3928413764606871165730
fib 106 = 6356306993006846248183
fib 107 = 10284720757613717413913
fib 108 = 16641027750620563662096
fib 109 = 26925748508234281076009
fib 110 = 43566776258854844738105
fib 111 = 70492524767089125814114
fib 112 = 114059301025943970552219
fib 113 = 184551825793033096366333
fib 114 = 298611126818977066918552
fib 115 = 483162952612010163284885
fib 116 = 781774079430987230203437
fib 117 = 1264937032042997393488322
fib 118 = 2046711111473984623691759
fib 119 = 3311648143516982017180081
fib 120 = 5358359254990966640871840
fib 121 = 8670007398507948658051921
fib 122 = 14028366653498915298923761
fib 123 = 22698374052006863956975682
fib 124 = 36726740705505779255899443
fib 125 = 59425114757512643212875125
fib 126 = 96151855463018422468774568
fib 127 = 155576970220531065681649693
fib 128 = 251728825683549488150424261
fib 129 = 407305795904080553832073954
fib 130 = 659034621587630041982498215
fib 131 = 1066340417491710595814572169
fib 132 = 1725375039079340637797070384
fib 133 = 2791715456571051233611642553
fib 134 = 4517090495650391871408712937
fib 135 = 7308805952221443105020355490
fib 136 = 11825896447871834976429068427
fib 137 = 19134702400093278081449423917
fib 138 = 30960598847965113057878492344
fib 139 = 50095301248058391139327916261
fib 140 = 81055900096023504197206408605
fib 141 = 131151201344081895336534324866
fib 142 = 212207101440105399533740733471
fib 143 = 343358302784187294870275058337
fib 144 = 555565404224292694404015791808
fib 145 = 898923707008479989274290850145
fib 146 = 1454489111232772683678306641953
fib 147 = 2353412818241252672952597492098
fib 148 = 3807901929474025356630904134051
fib 149 = 6161314747715278029583501626149
fib 150 = 9969216677189303386214405760200
fib 151 = 16130531424904581415797907386349
fib 152 = 26099748102093884802012313146549
fib 153 = 42230279526998466217810220532898
fib 154 = 68330027629092351019822533679447
fib 155 = 110560307156090817237632754212345
fib 156 = 178890334785183168257455287891792
fib 157 = 289450641941273985495088042104137
fib 158 = 468340976726457153752543329995929
fib 159 = 757791618667731139247631372100066
fib 160 = 1226132595394188293000174702095995
fib 161 = 1983924214061919432247806074196061
fib 162 = 3210056809456107725247980776292056
fib 163 = 5193981023518027157495786850488117
fib 164 = 8404037832974134882743767626780173
fib 165 = 13598018856492162040239554477268290
fib 166 = 22002056689466296922983322104048463
fib 167 = 35600075545958458963222876581316753
fib 168 = 57602132235424755886206198685365216
fib 169 = 93202207781383214849429075266681969
fib 170 = 150804340016807970735635273952047185
fib 171 = 244006547798191185585064349218729154
fib 172 = 394810887814999156320699623170776339
fib 173 = 638817435613190341905763972389505493
fib 174 = 1033628323428189498226463595560281832
fib 175 = 1672445759041379840132227567949787325
fib 176 = 2706074082469569338358691163510069157
fib 177 = 4378519841510949178490918731459856482
fib 178 = 7084593923980518516849609894969925639
fib 179 = 11463113765491467695340528626429782121
fib 180 = 18547707689471986212190138521399707760
fib 181 = 30010821454963453907530667147829489881
fib 182 = 48558529144435440119720805669229197641
fib 183 = 78569350599398894027251472817058687522
fib 184 = 127127879743834334146972278486287885163
fib 185 = 205697230343233228174223751303346572685
fib 186 = 332825110087067562321196029789634457848
fib 187 = 538522340430300790495419781092981030533
fib 188 = 871347450517368352816615810882615488381
fib 189 = 1409869790947669143312035591975596518914
fib 190 = 2281217241465037496128651402858212007295
fib 191 = 3691087032412706639440686994833808526209
fib 192 = 5972304273877744135569338397692020533504
fib 193 = 9663391306290450775010025392525829059713
fib 194 = 15635695580168194910579363790217849593217
fib 195 = 25299086886458645685589389182743678652930
fib 196 = 40934782466626840596168752972961528246147
fib 197 = 66233869353085486281758142155705206899077
fib 198 = 107168651819712326877926895128666735145224
fib 199 = 173402521172797813159685037284371942044301
fib 200 = 280571172992510140037611932413038677189525
fib 201 = 453973694165307953197296969697410619233826
fib 202 = 734544867157818093234908902110449296423351
fib 203 = 1188518561323126046432205871807859915657177
fib 204 = 1923063428480944139667114773918309212080528
fib 205 = 3111581989804070186099320645726169127737705
fib 206 = 5034645418285014325766435419644478339818233
fib 207 = 8146227408089084511865756065370647467555938
fib 208 = 13180872826374098837632191485015125807374171
fib 209 = 21327100234463183349497947550385773274930109
fib 210 = 34507973060837282187130139035400899082304280
fib 211 = 55835073295300465536628086585786672357234389
fib 212 = 90343046356137747723758225621187571439538669
fib 213 = 146178119651438213260386312206974243796773058
fib 214 = 236521166007575960984144537828161815236311727
fib 215 = 382699285659014174244530850035136059033084785
fib 216 = 619220451666590135228675387863297874269396512
fib 217 = 1001919737325604309473206237898433933302481297
fib 218 = 1621140188992194444701881625761731807571877809
fib 219 = 2623059926317798754175087863660165740874359106
fib 220 = 4244200115309993198876969489421897548446236915
fib 221 = 6867260041627791953052057353082063289320596021
fib 222 = 11111460156937785151929026842503960837766832936
fib 223 = 17978720198565577104981084195586024127087428957
fib 224 = 29090180355503362256910111038089984964854261893
fib 225 = 47068900554068939361891195233676009091941690850
fib 226 = 76159080909572301618801306271765994056795952743
fib 227 = 123227981463641240980692501505442003148737643593
fib 228 = 199387062373213542599493807777207997205533596336
fib 229 = 322615043836854783580186309282650000354271239929
fib 230 = 522002106210068326179680117059857997559804836265
fib 231 = 844617150046923109759866426342507997914076076194
fib 232 = 1366619256256991435939546543402365995473880912459
fib 233 = 2211236406303914545699412969744873993387956988653
fib 234 = 3577855662560905981638959513147239988861837901112
fib 235 = 5789092068864820527338372482892113982249794889765
fib 236 = 9366947731425726508977331996039353971111632790877
fib 237 = 15156039800290547036315704478931467953361427680642
fib 238 = 24522987531716273545293036474970821924473060471519
fib 239 = 39679027332006820581608740953902289877834488152161
fib 240 = 64202014863723094126901777428873111802307548623680
fib 241 = 103881042195729914708510518382775401680142036775841
fib 242 = 168083057059453008835412295811648513482449585399521
fib 243 = 271964099255182923543922814194423915162591622175362
fib 244 = 440047156314635932379335110006072428645041207574883
fib 245 = 712011255569818855923257924200496343807632829750245
fib 246 = 1152058411884454788302593034206568772452674037325128
fib 247 = 1864069667454273644225850958407065116260306867075373
fib 248 = 3016128079338728432528443992613633888712980904400501
fib 249 = 4880197746793002076754294951020699004973287771475874
fib 250 = 7896325826131730509282738943634332893686268675876375
fib 251 = 12776523572924732586037033894655031898659556447352249
fib 252 = 20672849399056463095319772838289364792345825123228624
fib 253 = 33449372971981195681356806732944396691005381570580873
fib 254 = 54122222371037658776676579571233761483351206693809497
fib 255 = 87571595343018854458033386304178158174356588264390370
fib 256 = 141693817714056513234709965875411919657707794958199867
fib 257 = 229265413057075367692743352179590077832064383222590237
fib 258 = 370959230771131880927453318055001997489772178180790104
fib 259 = 600224643828207248620196670234592075321836561403380341
fib 260 = 971183874599339129547649988289594072811608739584170445
fib 261 = 1571408518427546378167846658524186148133445300987550786
fib 262 = 2542592393026885507715496646813780220945054040571721231
fib 263 = 4114000911454431885883343305337966369078499341559272017
fib 264 = 6656593304481317393598839952151746590023553382130993248
fib 265 = 10770594215935749279482183257489712959102052723690265265
fib 266 = 17427187520417066673081023209641459549125606105821258513
fib 267 = 28197781736352815952563206467131172508227658829511523778
fib 268 = 45624969256769882625644229676772632057353264935332782291
fib 269 = 73822750993122698578207436143903804565580923764844306069
fib 270 = 119447720249892581203851665820676436622934188700177088360
fib 271 = 193270471243015279782059101964580241188515112465021394429
fib 272 = 312718191492907860985910767785256677811449301165198482789
fib 273 = 505988662735923140767969869749836918999964413630219877218
fib 274 = 818706854228831001753880637535093596811413714795418360007
fib 275 = 1324695516964754142521850507284930515811378128425638237225
fib 276 = 2143402371193585144275731144820024112622791843221056597232
fib 277 = 3468097888158339286797581652104954628434169971646694834457
fib 278 = 5611500259351924431073312796924978741056961814867751431689
fib 279 = 9079598147510263717870894449029933369491131786514446266146
fib 280 = 14691098406862188148944207245954912110548093601382197697835
fib 281 = 23770696554372451866815101694984845480039225387896643963981
fib 282 = 38461794961234640015759308940939757590587318989278841661816
fib 283 = 62232491515607091882574410635924603070626544377175485625797
fib 284 = 100694286476841731898333719576864360661213863366454327287613
fib 285 = 162926777992448823780908130212788963731840407743629812913410
fib 286 = 263621064469290555679241849789653324393054271110084140201023
fib 287 = 426547842461739379460149980002442288124894678853713953114433
fib 288 = 690168906931029935139391829792095612517948949963798093315456
fib 289 = 1116716749392769314599541809794537900642843628817512046429889
fib 290 = 1806885656323799249738933639586633513160792578781310139745345
fib 291 = 2923602405716568564338475449381171413803636207598822186175234
fib 292 = 4730488062040367814077409088967804926964428786380132325920579
fib 293 = 7654090467756936378415884538348976340768064993978954512095813
fib 294 = 12384578529797304192493293627316781267732493780359086838016392
fib 295 = 20038668997554240570909178165665757608500558774338041350112205
fib 296 = 32423247527351544763402471792982538876233052554697128188128597
fib 297 = 52461916524905785334311649958648296484733611329035169538240802
fib 298 = 84885164052257330097714121751630835360966663883732297726369399
fib 299 = 137347080577163115432025771710279131845700275212767467264610201
fib 300 = 222232244629420445529739893461909967206666939096499764990979600
fib 301 = 359579325206583560961765665172189099052367214309267232255589801
fib 302 = 581811569836004006491505558634099066259034153405766997246569401
fib 303 = 941390895042587567453271223806288165311401367715034229502159202
fib 304 = 1523202464878591573944776782440387231570435521120801226748728603
fib 305 = 2464593359921179141398048006246675396881836888835835456250887805
fib 306 = 3987795824799770715342824788687062628452272409956636682999616408
fib 307 = 6452389184720949856740872794933738025334109298792472139250504213
fib 308 = 10440185009520720572083697583620800653786381708749108822250120621
fib 309 = 16892574194241670428824570378554538679120491007541580961500624834
fib 310 = 27332759203762391000908267962175339332906872716290689783750745455
fib 311 = 44225333398004061429732838340729878012027363723832270745251370289
fib 312 = 71558092601766452430641106302905217344934236440122960529002115744
fib 313 = 115783425999770513860373944643635095356961600163955231274253486033
fib 314 = 187341518601536966291015050946540312701895836604078191803255601777
fib 315 = 303124944601307480151388995590175408058857436768033423077509087810
fib 316 = 490466463202844446442404046536715720760753273372111614880764689587
fib 317 = 793591407804151926593793042126891128819610710140145037958273777397
fib 318 = 1284057871006996373036197088663606849580363983512256652839038466984
fib 319 = 2077649278811148299629990130790497978399974693652401690797312244381
fib 320 = 3361707149818144672666187219454104827980338677164658343636350711365
fib 321 = 5439356428629292972296177350244602806380313370817060034433662955746
fib 322 = 8801063578447437644962364569698707634360652047981718378070013667111
fib 323 = 14240420007076730617258541919943310440740965418798778412503676622857
fib 324 = 23041483585524168262220906489642018075101617466780496790573690289968
fib 325 = 37281903592600898879479448409585328515842582885579275203077366912825
fib 326 = 60323387178125067141700354899227346590944200352359771993651057202793
fib 327 = 97605290770725966021179803308812675106786783237939047196728424115618
fib 328 = 157928677948851033162880158208040021697730983590298819190379481318411
fib 329 = 255533968719576999184059961516852696804517766828237866387107905434029
fib 330 = 413462646668428032346940119724892718502248750418536685577487386752440
fib 331 = 668996615388005031531000081241745415306766517246774551964595292186469
fib 332 = 1082459262056433063877940200966638133809015267665311237542082678938909
fib 333 = 1751455877444438095408940282208383549115781784912085789506677971125378
fib 334 = 2833915139500871159286880483175021682924797052577397027048760650064287
fib 335 = 4585371016945309254695820765383405232040578837489482816555438621189665
fib 336 = 7419286156446180413982701248558426914965375890066879843604199271253952
fib 337 = 12004657173391489668678522013941832147005954727556362660159637892443617
fib 338 = 19423943329837670082661223262500259061971330617623242503763837163697569
fib 339 = 31428600503229159751339745276442091208977285345179605163923475056141186
fib 340 = 50852543833066829834000968538942350270948615962802847667687312219838755
fib 341 = 82281144336295989585340713815384441479925901307982452831610787275979941
fib 342 = 133133688169362819419341682354326791750874517270785300499298099495818696
fib 343 = 215414832505658809004682396169711233230800418578767753330908886771798637
fib 344 = 348548520675021628424024078524038024981674935849553053830206986267617333
fib 345 = 563963353180680437428706474693749258212475354428320807161115873039415970
fib 346 = 912511873855702065852730553217787283194150290277873860991322859307033303
fib 347 = 1476475227036382503281437027911536541406625644706194668152438732346449273
fib 348 = 2388987100892084569134167581129323824600775934984068529143761591653482576
fib 349 = 3865462327928467072415604609040860366007401579690263197296200323999931849
fib 350 = 6254449428820551641549772190170184190608177514674331726439961915653414425
fib 351 = 10119911756749018713965376799211044556615579094364594923736162239653346274
fib 352 = 16374361185569570355515148989381228747223756609038926650176124155306760699
fib 353 = 26494272942318589069480525788592273303839335703403521573912286394960106973
fib 354 = 42868634127888159424995674777973502051063092312442448224088410550266867672
fib 355 = 69362907070206748494476200566565775354902428015845969798000696945226974645
fib 356 = 112231541198094907919471875344539277405965520328288418022089107495493842317
fib 357 = 181594448268301656413948075911105052760867948344134387820089804440720816962
fib 358 = 293825989466396564333419951255644330166833468672422805842178911936214659279
fib 359 = 475420437734698220747368027166749382927701417016557193662268716376935476241
fib 360 = 769246427201094785080787978422393713094534885688979999504447628313150135520
fib 361 = 1244666864935793005828156005589143096022236302705537193166716344690085611761
fib 362 = 2013913292136887790908943984011536809116771188394517192671163973003235747281
fib 363 = 3258580157072680796737099989600679905139007491100054385837880317693321359042
fib 364 = 5272493449209568587646043973612216714255778679494571578509044290696557106323
fib 365 = 8531073606282249384383143963212896619394786170594625964346924608389878465365
fib 366 = 13803567055491817972029187936825113333650564850089197542855968899086435571688
fib 367 = 22334640661774067356412331900038009953045351020683823507202893507476314037053
fib 368 = 36138207717265885328441519836863123286695915870773021050058862406562749608741
fib 369 = 58472848379039952684853851736901133239741266891456844557261755914039063645794
fib 370 = 94611056096305838013295371573764256526437182762229865607320618320601813254535
fib 371 = 153083904475345790698149223310665389766178449653686710164582374234640876900329
fib 372 = 247694960571651628711444594884429646292615632415916575771902992555242690154864
fib 373 = 400778865046997419409593818195095036058794082069603285936485366789883567055193
fib 374 = 648473825618649048121038413079524682351409714485519861708388359345126257210057
fib 375 = 1049252690665646467530632231274619718410203796555123147644873726135009824265250
fib 376 = 1697726516284295515651670644354144400761613511040643009353262085480136081475307
fib 377 = 2746979206949941983182302875628764119171817307595766156998135811615145905740557
fib 378 = 4444705723234237498833973519982908519933430818636409166351397897095281987215864
fib 379 = 7191684930184179482016276395611672639105248126232175323349533708710427892956421
fib 380 = 11636390653418416980850249915594581159038678944868584489700931605805709880172285
fib 381 = 18828075583602596462866526311206253798143927071100759813050465314516137773128706
fib 382 = 30464466237021013443716776226800834957182606015969344302751396920321847653300991
fib 383 = 49292541820623609906583302538007088755326533087070104115801862234837985426429697
fib 384 = 79757008057644623350300078764807923712509139103039448418553259155159833079730688
fib 385 = 129049549878268233256883381302815012467835672190109552534355121389997818506160385
fib 386 = 208806557935912856607183460067622936180344811293149000952908380545157651585891073
fib 387 = 337856107814181089864066841370437948648180483483258553487263501935155470092051458
fib 388 = 546662665750093946471250301438060884828525294776407554440171882480313121677942531
fib 389 = 884518773564275036335317142808498833476705778259666107927435384415468591769993989
fib 390 = 1431181439314368982806567444246559718305231073036073662367607266895781713447936520
fib 391 = 2315700212878644019141884587055058551781936851295739770295042651311250305217930509
fib 392 = 3746881652193013001948452031301618270087167924331813432662649918207032018665867029
fib 393 = 6062581865071657021090336618356676821869104775627553202957692569518282323883797538
fib 394 = 9809463517264670023038788649658295091956272699959366635620342487725314342549664567
fib 395 = 15872045382336327044129125268014971913825377475586919838578035057243596666433462105
fib 396 = 25681508899600997067167913917673267005781650175546286474198377544968911008983126672
fib 397 = 41553554281937324111297039185688238919607027651133206312776412602212507675416588777
fib 398 = 67235063181538321178464953103361505925388677826679492786974790147181418684399715449
fib 399 = 108788617463475645289761992289049744844995705477812699099751202749393926359816304226

Conclusion

This article has described how to implement Fibonacci numbers with an infinite sequence, using predefined F# library functions, literals, and .NET types. Future articles will show various other kinds of implementations (recursive, imperative, continuation-passing, monadic, ...).

Tags:

F#

F#, an Ideal Language For Writing .NET Unit Tests

by Marc Sigrist 8. February 2015 20:35

In this post, we are going to test the escaped concact/split functions that we implemented last time. Along the way, it will become apparent why F# is an ideal language for writing .NET unit tests. These are the signatures of the two F# functions to be tested:

val concatEscape : esc:char -> sep:string -> strings:seq<string> -> string
val splitUnescape : esc:char -> sep:string -> string:string -> seq<string>

Seen from C# (e.g., in Visual Studio's object browser), the signatures would look like this:

public static string concatEscape(char esc, string sep, IEnumerable<string> strings);
public static IEnumerable<string> splitUnescape(char esc, string sep, string @string);

We will use Visual Studio's built-in Test Explorer to visualize the results, which will look like this:

Test Explorer results

Step 1: Prepare the Test Project

Create a new F# class library project named e.g. MyCompany.Foundation.Tests, and add the following NuGet packages:

 

Step 2: Define Custom Operators to Further Simplify Testing

Add a new F# source code file called StringTests.fs to the project, with the following code:

namespace MyCompany.Foundation.Tests

open System
open NUnit.Framework
open FsUnit.TopLevelOperators
open MyCompany.Foundation.Core

[<AutoOpen>]
module Operators =
    let throws<'T when 'T :> exn> : (unit -> unit) -> unit = should throw typeof<'T>

    /// Asserts equality of two instances of the same type.
    let (.=) (actual:'T) (expected:'T) = should equal expected actual 
    

throws is a supporting function who tests whether a given function throws a certain type of exception. The .= operator enables a very simple syntax two test if two values of the same type are equal, e.g. x .= y.

Step 3: Begin a Module for the Tests

In the StringTests.fs file, add the following code:

module StringTests =

That's all you need to do to create the test fixture class required by NUnit. It is not necessary to define a full-blown class, and it is not necessary to add a [<TestFixture>] attribute.

Step 4: Implement reusable testing functionality

concatEscape and splitUnescape both require an escape character and a separator string as arguments, which must be validated in the same way. To avoid repetitive code, we define a function testSeparatorValidationOf who

  • takes another function f as parameter,
  • calls f with several combinations of escape character and separator string,
  • tests whether f correctly validates the escape character and separator string.

 

    let private testSeparatorValidationOf f =
        let test sep = f '!' sep

        // Separator must not be null
        (fun _ -> test null |> ignore) |> throws<ArgumentNullException>
        
        // Separator must not be empty
        (fun _ -> test String.Empty |> ignore) |> throws<ArgumentException>

        // Separator must not have same beginning and ending
        for sep in ["xx"; "xax"; "xabx"; "xyxy"; "xyaxy"; "xyabxy"
                    "xyzqwertyabcxyzqwerty"] do
            (fun _ -> test sep |> ignore) |> throws<ArgumentException>

        // Separator must not start with escape character
        (fun _ -> test "!; " |> ignore) |> throws<ArgumentException>

Note that we did not have to write any type annotations. For instance, the F# compiler automatically inferred that the parameter f must be of type char -> string -> 'a, i.e., a function who takes a character parameter and a string parameter and returns a value of generic type. In C#, to achieve something similar, we would have to write:

    static a testSeparatorValidationOf<a>(Func<char, string, a> f){
        Func<string, a> test = sep => f('!', sep);
    
        // Etc. ...
    }

Step 5: Implement Test Functions

The first two tests check whether concatEscape and splitUnescape validate arguments correctly:

    [<Test>]
    let ``concatEscape validates parameters correctly``() = 
        // Test validation of separator
        testSeparatorValidationOf
        <| fun esc sep -> String.concatEscape esc sep ["asdf"; "qwer"; "uiop"]

        // Test validation of input string sequence (must not be null)
        (fun _ -> String.concatEscape '!' "; " null |> ignore) 
        |> throws<ArgumentNullException>

    [<Test>]
    let ``splitUnescape validates parameters correctly``() = 
        // Test validation of separator
        testSeparatorValidationOf 
        <| fun esc sep -> String.splitUnescape esc sep "asdfqwpoiqwe"

        // Test validation of source string (must not be null)
        (fun _ -> String.splitUnescape '!' "; " null |> ignore) 
        |> throws<ArgumentNullException>

Note how F# allows using any kind of expression as identifier when you put it inside pairs of backtick marks, as in ``This :) is " a valid function name``.

The next test checks if concatEscape correctly handles cases where the whole sequence of elements is empty, or some elements are empty strings:

    [<Test>]
    let ``concatEscape handles missing or "" elements correctly``() =
        let concat = String.concatEscape '~' ";"
        let e, ab, cd = String.Empty, "ab", "cd"

        concat []          .= e
        concat [e]         .= e
        concat [e; e]      .= ";"
        concat [e; ab]     .= ";ab"
        concat [ab; e]     .= "ab;"
        concat [e; e; e]   .= ";;"
        concat [e; e; ab]  .= ";;ab"
        concat [e; ab; e]  .= ";ab;"
        concat [ab; e; e]  .= "ab;;"
        concat [e; ab; cd] .= ";ab;cd"
        concat [ab; e; cd] .= "ab;;cd"
        concat [ab; cd; e] .= "ab;cd;"

Note how we have defined the local concat function by partially applying the existing String.concatEscape function (calling it with only the first two of three possible arguments. This results in a new function who has the esc and sep arguments already built-in and expects only the remaining strings argument in its signature). Also note the usage of our custom-defined .= should equal operator. These F#-specific features allow us to test 12 different cases with minimum plumbing, but maximum expressiveness.

The next test checks whether concatEscape handles null strings correctly. This is needed because types who are defined by non-F# languages, such as System.String of mscorlib.dll, can be null. (Types who are defined in F#, even if they are reference types, by default cannot be null.)

    [<Test>]
    let ``concatEscape handles null elements like "" elements``() =
        let concat = String.concatEscape '~' ";"
        let e, ab, cd = String.Empty, "ab", "cd"

        concat [null]             .= concat [e]
        concat [null; null]       .= concat [e; e]
        concat [null; ab]         .= concat [e; ab]
        concat [ab; null]         .= concat [ab; e]
        concat [null; null; null] .= concat [e; e; e]
        concat [null; null; ab]   .= concat [e; e; ab]
        concat [null; ab; null]   .= concat [e; ab; e]
        concat [ab; null; null]   .= concat [ab; e; e]
        concat [null; ab; cd]     .= concat [e; ab; cd]
        concat [ab; null; cd]     .= concat [ab; e; cd]
        concat [ab; cd; null]     .= concat [ab; cd; e]

The following test checks whether concatEscape uses the escape character as specified in the requirements: The escape character should only escape itself (by duplication) if strictly necessary. Note, again, how F# allows to write 49 different test cases with minimum plumbing and maximum expressivity:

    [<Test>]
    let ``concatEscape uses escape character correctly``() =
        let concat = String.concatEscape '&' ";"
  
        // Escape single pre-existing separator
        concat [";"]       .= "&;"
        concat [";ab"]     .= "&;ab"
        concat ["ab;"]     .= "ab&;"
        concat ["ab;cd"]   .= "ab&;cd"
        concat [";"; ""]   .= "&;;"
        concat [";"; "ab"] .= "&;;ab"
        concat [""; ";"]   .= ";&;"
        concat ["ab"; ";"] .= "ab;&;"

        // Escape series of pre-existing separators
        concat [";;"]       .= "&;&;"
        concat [";;ab"]     .= "&;&;ab"
        concat ["ab;;"]     .= "ab&;&;"
        concat ["ab;;cd"]   .= "ab&;&;cd"
        concat [";;"; ""]   .= "&;&;;"
        concat [";;"; "ab"] .= "&;&;;ab"
        concat [""; ";;"]   .= ";&;&;"
        concat ["ab"; ";;"] .= "ab;&;&;"

        // Repeat pre-existing escape characters if followed by pre-existing separator
        // and then escape the pre-existing separator.
        concat ["&;"]          .= "&&&;"
        concat ["&;ab"]        .= "&&&;ab"
        concat ["ab&;"]        .= "ab&&&;"
        concat ["ab&;cd"]      .= "ab&&&;cd"
        concat ["&&;"]         .= "&&&&&;"
        concat ["&&;ab"]       .= "&&&&&;ab"
        concat ["ab&&;"]       .= "ab&&&&&;"
        concat ["ab&&;cd"]     .= "ab&&&&&;cd"
        concat ["&;"; ""]      .= "&&&;;"
        concat ["ab&;"; "cd"]  .= "ab&&&;;cd"
        concat ["&&;"; ""]     .= "&&&&&;;"
        concat ["ab&&;"; "cd"] .= "ab&&&&&;;cd"
        concat [""; "&;"]      .= ";&&&;"
        concat ["ab"; "&;cd"]  .= "ab;&&&;cd"
        concat [""; "&&;"]     .= ";&&&&&;"
        concat ["ab"; "&&;cd"] .= "ab;&&&&&;cd"

        // Repeat pre-existing escape characters if followed by "real" separator.
        concat ["&"; ""]      .= "&&;"
        concat ["ab&"; "cd"]  .= "ab&&;cd"
        concat ["&&"; ""]     .= "&&&&;"
        concat ["ab&&"; "cd"] .= "ab&&&&;cd"

        // Do not repeat pre-existing escape characters 
        // if not followed by pre-existing or real separator.
        concat ["&"]          .= "&"
        concat ["&ab"]        .= "&ab"
        concat ["ab&"]        .= "ab&"
        concat ["ab&cd"]      .= "ab&cd"
        concat ["&&"]         .= "&&"
        concat ["&&ab"]       .= "&&ab"
        concat ["ab&&"]       .= "ab&&"
        concat ["ab&&cd"]     .= "ab&&cd"
        concat [""; "&"]      .= ";&"
        concat ["ab"; "&cd"]  .= "ab;&cd"
        concat [""; "&&"]     .= ";&&"
        concat ["ab"; "&&cd"] .= "ab;&&cd"

        // Use escape character correctly, even if the escape character is a space,
        // and is contained in the separator (but not in first position).
        String.concatEscape ' ' "; "
            [""; "a"; ""; "b"; "c; "; "d"; "; e"; " f"; "g "; "h"; ";i"; "j;"; ""] .= 
            "; a; ; b; c ; ; d;  ; e;  f; g  ; h; ;i; j;; "

The next test checks whether splitUnescape reproduces the input of concatEscape as expected. Note how F#, as an expression-based language, allows us to initialize inputLists (a list of string lists) in a very straight-forward way, with all permutations needed for testing visible at one glance. Using only 30 lines of code (excluding white space and comments), we are testing the concatenation and splitting of 110 lists of input strings with 9 different separators = 990 cases overall:

    [<Test>]
    let ``splitUnescape reverses concatEscape correctly``() = 
        /// Input lists for concatEscape, with '^' as escape and "|" as separator.
        let inputLists = 
            /// 3 permutations are enough to cover all positions (start, inside, and end).
            let permutate3 x y z =
                [[x; y; z]; [x; z; y]; [y; x; z]; [y; z; x]; [z; x; y]; [z; y; x]]

            /// Permutate 3 strings and use 3 variants of the last string
            /// (alone, prefixed, or suffixed).
            let permutate3x3 x y z preZ postZ = 
                let perm a b c = permutate3 x y <| sprintf "%s%s%s" a b c
                List.collect id [perm z preZ postZ; perm preZ z postZ; perm preZ postZ z]

            [ // Singular items
              [ [""]; [null]; ["^"]; ["|"]; ["^|"]; ["a"] ]
              
              // Singular items at start/middle/end of string and/or list
              permutate3 "a" "bc" ""
              permutate3 "d" "ef" null
              permutate3x3 "g" "hi" "^" "jk" "lm"
              permutate3x3 "o" "pq" "^^" "rs" "tu"
              permutate3x3 "v" "wx" "^^^" "yz" "12"
              permutate3x3 "a" "bc" "|" "de" "ef"
              permutate3x3 "g" "hi" "^|" "jk" "lm"
              
              // Some advanced complex input lists
              [ [ "asbc"; ""; "ef"; ""; ""; "gh"; null; "i"; null; null; "kl" ]
                [ "op^q^^rs^^^tu^^^^vw^^^^^x"; "op|q||rs|||t"; "op^|q^|^|rs^|^|^|t" ] ] ]
            |> List.collect id

        let esc = '^'
        let seps = ["x"; "xy"; "x^"; "xxy"; "xx^"; "xyy"; "xy^"; "x^y"; "x^^"]

        for lst in inputLists do
            for sep in seps do
                // Replace "|" placeholder with current separator.
                let concatSource =
                    lst |> List.map (function null -> null | s -> s.Replace("|", sep)) 
                let concatResult = String.concatEscape esc sep concatSource

                // Split result should be like concat source, except for nulls, which are "".
                let expectedSplitResult =
                    concatSource |> List.map (function null -> String.Empty | x -> x)
                let actualSplitResult =
                    String.splitUnescape esc sep concatResult |> Seq.toList
                actualSplitResult .= expectedSplitResult

The following test checks whether we can correctly reproduce lists of lists of lists of input strings by

  • repeatedly concatenating the strings at each nesting level, resulting in a large single string, and then
  • repeatedly splitting back the strings at each level.

 

    [<Test>]
    let ``splitUnescape reverses nested concatEscape correctly``() = 
        let esc, sep = '&', ";"

        let nestedConcatSources = 
            [ [ ["asdf"; "&x; asf & asdf"; "qipwueriuy"]
                ["qwer;qwer&;qerpo"; ""; "qwer"]
                [""; "qiuq"]
                [""]
                [" qwu  ^qpoij&*qwoerui;"] ] 
              [ ["qwieoruy"; "qwopeiurj&&"] ]
              [ ["tyiqwe"; "a"]
                [""; "&^a;lsdkj&q ;  "; "qwer"]
                ["qoidu"; ""; "qwer&qq"] ] ]

        let concatResult = 
            let concat = String.concatEscape esc sep
            let mapConcat = List.map concat
            nestedConcatSources |> List.map mapConcat |> mapConcat |> concat

        let splitResult =
            let split = String.splitUnescape esc sep >> Seq.toList
            let mapSplit = List.map split
            concatResult |> split |> mapSplit |> List.map mapSplit

        splitResult .= nestedConcatSources

In the last line above, note how F#'s built-in structural equality for (nested) lists allowed us to verify that splitResult equals nestedConcatSources with just a single line of code.

 

As is typical for functional code, concatEscape/splitUnescape rely on recursion. An inportant feature of the F# compiler is the ability to optimize recursive code so that stack overflows cannot occur, as long as the recursive calls are in tail position. Our last test checks whether we can pass lists of large strings, as well as large lists of strings, to the concatEscape/splitUnescape functions, without producing a stack overflow.

 

    /// This test will only pass in release mode (when --optimize is set).
    [<Test; Timeout 3000>]
    let ``concatEscape and splitUnescape scale without stack overflow``() =
        let roundTripTest strings =
            let esc, split = '&', ";"
            let concatResult = String.concatEscape esc split strings
            // Causes stack overflow in debug mode (when --optimize is not set).
            let splitResult = String.splitUnescape esc split concatResult |> Seq.toArray
            splitResult .= strings

        // Avoid stack overflow with source strings of 10k length each
        let rep2K = String.replicate 2000
        roundTripTest [| rep2K "qwert"; rep2K "abcd&"; rep2K "ab;cd" |]

        // Avoid stack overflow with source list of 10k items
        roundTripTest [| for i in 1 .. 10000 -> sprintf "%ixg;s&;c" i |]

Conclusion

We have implemented a comprehensive battery of test cases to verify the correctness of the concatEscape and splitUnescape functions. Using the light syntax of the expression-based, functional-first language F#, it is possible to write type-safe unit tests much more succinctly and self-documentary than with C# or any other .NET language.

Tags:

C# | F#

F# for C# developers: Creating escaped concat/split functions in F#

by Marc Sigrist 22. December 2014 03:36

The built-in .NET Join and Split methods for strings do not provide a way for escaping the separator. If the separator is already contained in the input strings before joining, the strings cannot be reproduced by splitting:

open System
let inputStrings = [| "Hello, world."; "How are you?" |]
let separator = ", "
let joinedResult = String.Join(separator, inputStrings)
let reproducedStrings = joinedResult.Split([| separator |], StringSplitOptions.None)
printfn "%A" inputStrings
printfn "%A" reproducedStrings

The output of the above code is:

[|"Hello, world."; "How are you?"|]   // An array with 2 elements
[|"Hello"; "world."; "How are you?"|] // An array with 3 elements

To solve this problem, we are going to implement a pair of functions called concatEscape and splitUnescape. Besides roundtrip concatenation, the functions will provide some additional benefits.

For C# Developers...

In the example, I will explain a total of about 30 different F# concepts that do not exist in C# 6.0. In case F# is completely new to you, here are some important basics:

  • F# uses indentation instead of curly braces { } to define scoped blocks of code.
  • F# (almost never) uses a return keyword. It is an expression-based language, and so the last executed line of a body of code implicitly specifies the return value.
  • It is not necessary to separate function parameters or arguments by commas and wrap them in parentheses. When you see something like let myFunction x y = x + Y - 1, myFunction is the name of the function, and x and y are the names of parameters. Everything after the = is the body of the function.
  • You will see almost no type declarations in the code. Nevertheless, F# is a statically typed language. In some ways, it is even more "strongly" typed than C#. The difference to C# is that the F# compiler automatically infers the types for you, and also automatically makes them generic where appropriate. Again, this greatly simplifies the code, so that you can focus your thinking more on the business logic.

Some Preliminary Remarks

Please note that, by exposing F# features unavailable in C#, I am in no way trying to make the C# language appear unfavorable. I consider C# to be a great language, in which I programmed intensely for about eight years with much joy. However, some C# coders mistakenly believe that learning F# is of not of much use, because "C# will eventually have all the features of F# included anyway". Nothing could be further from the truth. While some of the (rather cosmetic) F# features can be introduced quite smoothly to C#, the more substantial features would be very hard, or almost impossible, to integrate in a sane way. The main reason for this is that C# was not designed from the ground up as an expression-based language, and does not include important concepts such as non-nullability and immutability at its core.

Unit tests will be shown separately in an upcoming blog post. While test-driven development dictates that tests should be written before implementation, this order would be impractical for blogging. Furthermore, implementation and unit testing have a different quality in F# compared to C#. In F#, one normally writes most critical code in a script file first, constantly evaluating and improving each couple of lines in the REPL. Finally, the finished code is copied from the script file to the source file, which usually contains very few or zero bugs.

Step 1: Define the Requirements

For concatenation,

  • process the input strings as a stream (do not load all elements into memory at once)
  • use only a minimum number of escapes, if any. E.g., if the escape character pre-exists in an input string, it should itself be escaped by duplication only in cases where it precedes a real separator or an escaped pre-existing separator.
  • if the separator is empty, raise an ArgumentException
  • in other respects, behave like the built-int .NET Join method:
    • If the separator is null, raise an ArgumentNullException.
    • If the input sequence is null, raise an ArgumentNullException.
    • If the input sequence is empty, treat it like one with a single empty-string element.
    • If the input sequence contains null elements, treat them like empty strings.

For splitting,

  • return the output strings as a stream (do not load all elements into memory at once)
  • accurately reproduce the original input strings when given the same escape character and separator, except for the following cases (which work the same way as the built-in .NET Split method):
    • if the original input sequence was empty, reproduce it as sequence with a single empty-string element
    • if the original input sequence contained null strings, reproduce them as empty strings

Step 2: Define a Namespace

1  namespace MyCompany.Foundation.Core
2  
3  open System
4  open System.Text

Step 3: Implement Supporting Functionality

We are going to need some supporting functions to validate the concat/split function parameters:

 5  [<RequireQualifiedAccess>]
 6  module Assert = 
 7      let notNull argName arg = if arg = null then nullArg argName
 8      
 9      let notNullOrEmpty argName arg = 
10          notNull argName arg
11          if Seq.isEmpty arg then invalidArg argName "Value cannot be empty."

The above code uses the following features not present in C# 6.0:

  • Lines 5–6: Enforcement of qualified access to a module. In C# 6.0, it is now possible to open a static class with the using keyword. In F#, modules are similar to static classes, but allow for much simplified syntax. In addition, the access to modules can be declared with [<AutoOpen>] (open by default) or [<RequireQualifiedAccess>] (non-openable).
  • Line 9: Automatic type inference and generalization. argName is compiled as a string parameter, because it is used to call the notNull function, which itself calls the nullArg function, which requires a string argument. arg is compiled as a parameter of generic type, which must implement the sequence interface, because it is used to call Seq.isEmpty (Seq<> is the same as IEnumerable<>). Furthermore, arg is compiled as a type who "can be null", because it is validated via the notNull function (types declared in F# can never be null, but types declared outside F#—such as String or IEnumerable<T>>— can still be null).

Step 4: Declare the Token Type

To simplify the parsing, we will convert the input strings to token streams and then analyze/decompose the tokens streams via F#'s built-in pattern matching facilities.

12  type private Token = 
13      | Esc of Count:int
14      | Sep
15      | Val of Content:string

The above code uses the following features not present in C# 6.0:

  • Line 12: Private accessibility in namespace declaration groups. The Token type is only accessible by code who has been declared inside the namespace MyCompany.Foundation.Core in the same library.
  • Lines 12–15: Discriminated union type. An instance of Token symbolizes either a consecutive number of escapes (Esc), a separator (Sep), or anything else (Val). Later, when a Token instance is analyzed via pattern matching, the F# compiler will emit a warning if a case has been forgotten by the developer.

Step 5: Implement Tokenization

We define a Tokenizer module with just one function named create. The function takes the escape character and separator as parameters, validates them, and returns another function. The returned function has the escape character and separator already built-in (in the closure). It takes only a single argument, which is the string to be tokenized.

16  [<RequireQualifiedAccess>]
17  module private Tokenizer =
18    /// Returns a function who can convert a given source string to a token stream.
19    let create esc sep = 
20      let sepName = "sep"
21      let sepLen = String.length sep
22      
23      // Validate parameters
24      Assert.notNullOrEmpty sepName sep
25      if sep.[0] = esc then invalidArg sepName "Separator cannot start with escape char."
26      if sepLen > 1 then
27          let iMax = sepLen - 1
28          for i in 0 .. iMax / 2 do
29              if sep.[0 .. i] = sep.[sepLen - i - 1 .. iMax] then
30                  invalidArg sepName "Separator cannot have same beginning and ending."
31        
32      // Return the tokenizer function
33      fun source -> 
34          match String.length source - 1 with
35          | -1 -> Val String.Empty |> Seq.singleton
36          | iMax -> 
37            let (|Esc|_|) = 
38                let rec aux acc i = 
39                    if i <= iMax && source.[i] = esc then aux (acc + 1) (i + 1) else acc
40                aux 0 >> function 0 -> None | count -> Some count
41            
42            let (|Sep|_|) i = 
43                if i <= iMax - sepLen + 1 
44                   && String.CompareOrdinal(source, i, sep, 0, sepLen) = 0 then Some()
45                else None
46            
47            let rec read valLen i = 
48              seq { let wrapVal() = 
49                        if valLen > 0 
50                        then source.Substring(i - valLen, valLen) |> Val |> Seq.singleton
51                        else Seq.empty
52                    if i <= iMax then 
53                        match i with
54                        | Esc count -> 
55                            yield! wrapVal(); yield Esc count; yield! read 0 (i + count)
56                        | Sep -> yield! wrapVal(); yield Sep; yield! read 0 (i + sepLen)
57                        | _ -> yield! read (valLen + 1) (i + 1)
58                    else yield! wrapVal() }
59            read 0 0

The above code uses the following features not present in C# 6.0:

  • Line 18: Simplified XML documentation comments. Comment lines starting with triple slashes /// are converted to what looks in C# like ///<summary>...</summary>. Inside the F# comment, angular brackets can be used deliberately, such as MyType<T, SomeOtherType<U>>.
  • Line 29: Slice expressions allow retrieving a range of values from a collection in a succinct way.
  • Line 34: Syntactic pattern matching. match ... with ... analyzes and decomposes syntactic patterns, who can come in many different shapes with arbitrary nesting and complexity.
  • Line 35: Type functions and automatic inference of type parameters. Seq.singleton is inferred as Seq.singleton<Token>, which is a call to an F#-defined type function.
  • Lines 37, 42: Active patterns. Functions named (| ... |) can define various kinds of active patterns (single-case or optional patterns with or without arguments, multi-case patterns), which provides even more flexibility in pattern matching than is available in other ML-derived languages. The patterns are matched in lines 54 and 56, with completeness checking at compile time.
  • Line 37: Value declaration with arbitrary initialization body. We have pointed out above that let (|Esc|_|) = defines an active pattern function. More precisely, (|Esc|_|) is just an ordinary value who happens to be a lambda function. The value is initialized with the result of the last line of the body below (a new lambda function created by composing the left and right sides of the >> operator). In C#, we can use the var keyword only with very simple initializers (and not at all with delegates); in F#, we can use the let keyword with an arbitrary body of code containing nested scopes of arbitrary depth. Ironically, this feature of the "functional-first" language F# makes it possible to implement the OO principle of encapsulation in an even more fine-grained way than in the "OO-first" language C#.
  • Lines 38, 47: Tail call optimization. rec aux defines a recursive function named aux ("aux" is a common naming convention for an inner auxiliary function within an outer recursive function). The recursive call to aux, aux (acc + 1) (i + 1), is in tail position, which is compiled to a construct that will never cause a stack overflow regardless of recursive depth. The same is true for the rec read function.
  • Line 40: Partial function application. aux 0 calls the aux function with only one parameter, which gets a new, partial version of aux where the first parameter is already "built in", but the second parameter still has to be passed.
  • Line 40: Function composition. The partial version of aux is composed (i.e., "sticked together") with the following function using the >> operator.
  • Line 40: Condensed pattern matching with the function keyword. function 0 ... is an abbreviation for fun x -> match x with 0 .... It defines a lambda function with a parameter whose name we do not care about.
  • Line 40: option types. None and Some ...are the two possible cases of a discriminated union named option<'T>, which we are pattern matching against.
  • Lines 48–58: Computation expressions with unified syntax and custom builders. seq { ... } defines a sequence (compiled as IEnumerable<Token>). This is a kind of computation expression. Instead of seq { ... }, we could also have used [ ... ] to get a list or [| ... |] to get an array of Tokens. The same kind of syntactic principle can also be used with async { ... } for defining asynchronous algorithms or query {...} for defining queries. Furthermore, it is possible in F# to implement custom computation expression builders (e.g., to simplify continuation passing with cont { ... } or to simplify checking of failure conditions with maybe { ... }). Iterators, async methods, and query expressions are also available in C#, but they are hard-wired into the compiler—C# does not have a unified, extensible mechanism for defining monadic constructs.
  • Line 50: Function pipelining. The |> operator "forwards" the argument from the left side to the function or constructor on the right side. This makes it possible to express the "path" of an argument through various transformations in an elegant and self-documenting way.
  • Lines 55–58: yield! keyword for appending multiple elements. C# 6.0 only allows appending single elements using yield. Because of yield!, it is possible to recursively program sequences in an intuitive way (e.g., for traversing directory trees etc.), while at the same time avoiding stack overflows thanks to tail call optimization.

Step 6: Implement Concatenation and Splitting

Now that we have a custom tokenizer, we can use it in our concat/split functions. Instead of doing the parsing on the "character by character" level, we can analyze groups of tokens via syntactic pattern matching, with the added benefit of automatic case completeness checking at compile time.

 60  [<RequireQualifiedAccess>]
 61  module String = 
 62    /// Returns a new string by connecting the given strings with the given separator.
 63    let concatEscape esc sep (strings:seq<_>) = 
 64      Assert.notNull "strings" strings
 65      let sb = StringBuilder()
 66      
 67      let appendTokens areLast ts = 
 68          let appendEsc count = sb.Append(esc, count) |> ignore
 69          let appendVal (v: string) = sb.Append v |> ignore
 70          let appendSep() = appendVal sep
 71          
 72          let rec aux = function
 73              | [] -> ()
 74              | Esc count :: [] -> appendEsc <| if areLast then count else count * 2
 75              | Esc count :: (Sep :: _ as ts) -> appendEsc (count * 2); aux ts 
 76              | Esc count :: ts -> appendEsc count; aux ts
 77              | Sep :: ts -> appendEsc 1; appendSep(); aux ts
 78              | Val v :: ts -> appendVal v; aux ts
 79          
 80          aux ts
 81          if not areLast then appendSep()
 82      
 83      strings
 84      |> Seq.map (Tokenizer.create esc sep >> List.ofSeq)
 85      |> Seq.fold (fun ts1 ts2 -> Option.iter (appendTokens false) ts1; Some ts2) None
 86      |> Option.iter (appendTokens true)
 87      
 88      sb.ToString()
 89      
 90    /// Reproduces the original substrings from a string created with concatEscape.
 91    let splitUnescape esc sep string = 
 92        Assert.notNull "string" string
 93        let emptyVal = Val String.Empty
 94        let sepVal = Val sep
 95        let flipAppend x1 x2 = Seq.append x2 x1
 96        
 97        // Produce token stream
 98        string
 99        |> Tokenizer.create esc sep 
100        
101        // Convert token stream to StringBuilder stream
102        |> flipAppend [emptyVal]
103        |> Seq.scan 
104          (fun (sb:StringBuilder, t1) t2 ->
105              match t1, t2 with
106              | Esc count, Sep when count % 2 = 1 -> sb.Append(esc, count / 2), sepVal
107              | Esc count, Sep -> sb.Append(esc, count / 2), Sep
108              | Esc count, _ -> sb.Append(esc, count), t2
109              | Sep, _ -> StringBuilder(), t2
110              | Val v, _ -> sb.Append v, t2)
111          (StringBuilder(), emptyVal)
112        |> Seq.map fst
113        
114        // Of each series of repeated StringBuilder references, keep only the last
115        // reference (which points to the StringBuilder's completed state). 
116        // Convert the remaining StringBuilder references to strings.
117        |> flipAppend [null]
118        |> Seq.pairwise
119        |> Seq.filter (fun (sb1, sb2) -> sb1 <> sb2)
120        |> Seq.map (fst >> sprintf "%O")

The above code uses the following features not present in C# 6.0:

  • Line 61: Module merging. We give our module the name String. However, there is already a .NET class named System.String and an F# library module named FSharp.Core.String. Now, when someone opens our MyCompany.Foundation.Core namespace and types String., Visual Studio IntelliSense will automatically list all static members and functions together. This is a straightforward and intuitive way of extending pre-existing static library functionality without having to go through a formal "extension member definition" mechanism. (Such a mechanism exists in F#, too, but it is used less often than in C#. It allows you to define not only instance extension methods, but also static extension methods, extension properties, and even extension events.)
  • Line 63: Wildcards. By writing seq<_> using the wildcard symbol _, we force the compiler to declare the strings parameter as a generic sequence (IEnumerable<...>), but let it still infer the type parameter automatically. This is sometimes callled "mumble typing". Because of the way the strings parameter is used in the function, it is ultimately inferred as seq<string>.
  • Lines 73–78: Syntactic pattern matching on union cases and list patterns. [] represents an empty list, and Esc count :: [] represents a list with a single element at the head, who itself represents the Esc case of the Token union type. The variable count is automatically initialized at runtime (if the overall pattern matches) with the number of consecutive escape characters found in the string. Further patterns are used in the remaining lines, and the F# compiler emits a warning if we forget a match.
  • Line 91: Only few reserved keywords in F#. In line 89, we use string as the name of a parameter. This is possible because string is not a keyword in F#; it's a type abbreviation that can be replaced with a custom definition without a problem. The same is true for all other names of "built-in" types, as well as most "built-in" operators (who are just predefined library functions).
  • Line 105–110, 120: Syntactic tuple types with pattern matching support.t1, t2 defines a tuple, which is matched against in the lines 105–110, with case completeness checking at compile time. In line 120, fst is a built-in F# library function who returns the first item of a tuple.
  • Line 120: Statically typed format strings. sprintf "%O" defines a function who takes an object and returns the object's ToString() result. In our example, it gets the string from each StringBuilder instance. (Other available format specifiers would be %i for integer numbers, %s for strings, %b for booleans, and more.)

Summary

I have used string concatenation and splitting as a didactical example to demonstrate many F# features not known in C# 6.0. Using other examples, I could continue with still more features: inlining, pattern matching with records, automatic structural equality and comparison, aggressive optimization of closures and generic calls, units of measure, type providers, custom operators as functions or members, quotations, ...

There is one feature I did not point out explicitly, because it is omnipresent: Immutability. All values in the example are read-only (which is the default in F#); I did not have to declare even a single value as mutable. Immutability simplifies understanding the program flow, because one does not have to worry about the same state being modified in different places. The advantages of immutability are more striking in parallel code, which I did not use in the example. By contrast, in C#, all values are mutable by default (and are consequently called "variables"), and local immutability is not even available, except for constants.

In the next blog post, I will use F# to systematically define an extensive battery of unit tests against the example, using a bare minimum of ceremony.

Tags:

C# | F#

If you don't cover F#...

by Marc Sigrist 13. May 2014 12:08

Listen here what the great Luciano Pavarotti has to say about F# ;)

(Starts at 3m18s. Some non-desktop browsers will take you to the beginning instead, so you might have to wind forward manually.)

Tags:

F#

F# Generic Inlining With Member Constraints

by Marc Sigrist 13. July 2012 16:05

In this post, we are going to create a Converter class who converts values to strings. The conversion rules are speciļ¬ed by passing the name of a culture to the class’ constructor. The culture name can contain just the language (as ISO 639-1 alpha-2 code, e. g. “en”) or the language and region (as ISO 3166 code, e. g. “US”) combined with hyphen, e. g. “en-US”. An empty culture name “” specifies the invariant culture, which falls back to “en”.

The class has only one conversion method ToString, who is generic. It takes a single parameter, which is the value to be converted. The parameter’s type is inferred to have a member constraint, who restricts the type (at compile time) to have an instance member with the signature
ToString: IFormatProvider -> string. The parameter’s member is invoked with a member constraint invocation expression.

open System
open System.Globalization
 
type Converter(cultureName:string) =
    /// The culture used by this converter.
    member val Culture = CultureInfo.GetCultureInfo cultureName

    /// Converts value to a string, based on the specified culture.
    member inline self.ToString value =
        (^T: (member ToString: IFormatProvider -> string) 
        value, self.Culture)
 
// Test
let germanConverter = Converter "de"
let nrString = germanConverter.ToString 1234.643  // "1234,643"
let dtString = germanConverter.ToString <| 
               DateTime(2003, 11, 25, 17, 38, 47) // "25.11.2003 17:38:47"

Edit (Oct 15, 2012)

 The converter's culture is now exposed via a public property, based on F# 3.0 auto property syntax. (The Culture's value is evaluated only once, during class construction time.) Previously, the culture was a private field, and the example could not compile in a regular source file, due to access rule violation. Strangely, it did compile in a scripting file; this is an example where the scripting compiler (wrongly) does not behave in the exact same way as the regular compiler.

This is a blog post in the “Brief tip” category. It is meant as a starting point for further investigation, not as a complete copy/paste solution to a specific concern you may have.

"Super-Strong" Typing, Dynamic Typing, and Type Inference in F#

by Marc Sigrist 23. January 2012 15:19

This article gives an overview how types are accessed in F# with a combination of features related to static typing, dynamic typing, and type inference.

Static Typing

Static type checking ensures, at compile time, that the program is free from most kinds of type errors. The source code editor can highlight such errors as soon as they are written out. Static type checking in F# probably goes further than in any other strongly typed language:

  • By default, types defined in F# cannot be null. This eradicates a whole category of painful and costly errors (Tony Hoare of Microsoft Research Cambridge, who introduced null references in ALGOL in 1965, later regarded this as his "Billion dollar mistake").
      
    
  • Implicit conversions are not allowed. This even includes numeric, precision-preserving coercions. For instance, you cannot pass an integer, when a floating point value is expected, without explicit conversion. However, F# permits passing an argument of a derived type where a parameter of a base type is expected. It is also possible to utilize implicit operator overloads, who have been implemented in other languages, by calling the op_implicit member of the Common Intermediate Language (CIL) type:
      
    
    open System.Drawing
    let rect = Rectangle(23, 12, 17, 13)
    let rectF = RectangleF.op_Implicit rect
    
      
    
  • A new feature introduced by F#, units of measure, lets the compiler verify calculations associated with measurements. This prevents you from passing a number of meters when a number of kilograms is expected. On the other hand, when you multiply a number of meters with another number of meters, the compiler automatically creates type-safe square meters for you:
      
    
    [<Measure>]
    type m
    let meters = 276<m>
    let squareMeters = meters * meters
    // Resolved by the compiler as:
    // val squareMeters : int<m ^ 2> = 76176
    
      
    
    In F# 3.0, the core library will contain the namespace Microsoft.FSharp.Data.UnitSystems.SI, with predefined units of measure types for the International System of Units (SI), such as ampere (A), hertz (Hz), kelvin (k), lux (lx), metre (m), newton (N), second (s), ... Units of measure were originally conceived by Andrew Kennedy, of Microsoft Research Cambridge, in his PhD thesis. He also wrote a great introduction about it in his blog.
      
    
  • F# 3.0 will introduce another pioneering feature: type providers. They let you access any kind of untyped data source, locally or remotely, in a strongly-typed way at compile time, with full autocompletion/IntelliSense support. There will be built-in type providers for database connections, OData services, web services, resource files, and more. You will also be able to create your own custom type providers.

Dynamic typing

With type providers, there is no more need for dynamic typing... almost! For instance, one may still require dynamic typing for calls to arbitrary, untyped data sources unknown at compile time. In F#, this can be achieved by implementing the predefined dynamic operators ? and ?<-. These operators permit, with almost "surgical precision", to access parts of a type in a "weak" (but generic) way, while still keeping the "strong" access to the rest of the type's API intact.

// Implement dynamic operators for System.DataRow 
// to allow getting/setting a generic value.
open System.Data
let (?) (row:DataRow) (columnName:string) = 
    unbox row.[columnName]
let (?<-) (row:DataRow) (columnName:string) value  = 
    row.[columnName] <- value

// Create a DataTable with two columns.
let table = new DataTable()
table.Columns.Add("Name", typeof<string>)
table.Columns.Add("Born", typeof<DateTime>)

// Initialize a DataRow, using the dynamic operator.
let row = table.NewRow()
row?Name <- "John Doe"
row?Born <- DateTime(1983, 7, 26)
table.Rows.Add row

// Read the row content into a strongly-typed record.
type Person = {Name: string; Born: DateTime}
let record = {Name = row?Name; Born = row?Born}

I find this approach preferable to C#, whose dynamic keyword is less granular, as it forces the programmer to access the complete API of a type in a weak way. It is also non-generic, as each access to a dynamic instance returns another dynamic instance.

Type inference

Type inference in F# automatically recognizes the intended types (including generic types) of local values, parameters (including return parameters), and let-bound fields. Is is based on the Hindley–Milner (HM) method. One can always declare a type manually, in various places in the source code. However, declaring a type is usually not necessary. As a consequence, you can write straightforward, simple code, even when the types and signatures involved are highly generic. The following example creates a helper class in F#, which may be used by any client written in a CIL-compatible language (F#, C#, VB.Net, ...).

open System.Linq
type SortHelper =
    static member GetTopN(values, keySelector, n) =
        Enumerable.OrderByDescending(values, keySelector) |> Seq.take n 

The above GetTopN method looks as follows when accessed from C#. Notice how the F# compiler has automatically inferred the types and genericity of the signature from the context:

public static IEnumerable<a> GetTopN<a, b>
    (IEnumerable<a> values, Func<a, b> keySelector, int n)
  

Conclusion

The combination of static typing, dynamic typing, and type inference gives you the best of three worlds. Static typing with type inference has been known for many years in functional languages such as Haskell and functional/object-oriented languages such as OCaml. However, with units of measure and type providers, F# gives you a new kind of "super-strong typing", while still allowing weak typing in cases where it is unavoidable. In addition, F# gives you type-safe access to thousands of types predefined in the .NET Framework (or Mono), and—via CIL interoperability—to a potentially unlimited number of libraries implemented in other languages.

Tags:

F#

List-like expressions in F# 2.0

by Marc Sigrist 16. July 2011 13:13

F# provides literal expressions for tuples, F# lists, arrays, enumerables, and other generic types. The elements of a tuple expression are separated by commas. The elements of all other kinds of list-like expressions are separated by semicolons.

F# Expression F# Type Representation C# Type Representation
17, 3, 8   
int * int * int
Tuple<int, int, int>
[17; 3; 8]
int list
FSharpList<int>
[|17; 3; 8|]
int[]
int[]
seq {yield 17; yield 3; yield 8}
int seq
IEnumerable<int>

Note that F# lists should not be exposed to non-F# programs, because languages such as C# do not have the necessary language constructs for a smooth coding experience (:: operator, pattern matching, etc.).

The expressions can be nested deliberately.

F# Nested Expression F# Type Representation C# Type Representation
[17, 3, 8]
(int * int * int) list
FSharpList<Tuple<int, int, int>>
[|17, 3, 8|]
(int * int * int)[]
Tuple<int, int, int>[]
[|[|17; 3; 8|]; [|5; 2|]|]
int[][]
int[][]
array2D [[1; 5]; [7;9]]
int[,]
int[,]
[|array2D [[1; 3]; [1; 3]]|]
int[,][]
int[][,]
[|2.7M, true; 3.9M, false|]
(decimal * bool)[]
Tuple<decimal, bool>[]
(1, 'c'), (3.3, 20I, "abc")
(int * char) *
(float * bigint * string)
Tuple<Tuple<int, char>, 
Tuple
<double, BigInteger, string>>
Etc.
   

Note that in F#, jagged multidimensional arrays are represented in reverse order compared to C#: The F# type int[,][] corresponds to the C# type int[][,]. This is to keep it consistent with other F# postfix type names, such as int option list, an example of which would be [None; Some(1); Some(2)].

Instead of using semicolons, one can put each element on its own line, as in this array of type int[]:

[| 17
   3
   8 |]

F# contains many more kinds of expressions to simplify working with list-like types. The following range expression defines an IEnumerable<decimal> from 3 to 1275, with steps of 0.25 in between: 3, 3.25, 3.50, 3.75...

seq { 3M .. 0.25M .. 1275M }

The following code defines an array of type int[] with squares of positive whole numbers: 1, 4, 9, 16, ...

[| for i in 1 .. 1000 -> i * i |]

All the list-like types in F# are supported by a wealth of keywords, symbols and operators, and helper functions in FSharp.Core.dll. The following code defines an "infinite" IEnumerable<UInt64> of binomial results, calculated from each consecutive pair of natural numbers starting at zero: 1, 9, 25, 49, ...

Seq.initInfinite uint64
|> Seq.pairwise
|> Seq.map(fun (a, b) -> pown (a + b) 2)

Further information on list-like expressions in F# can be found in the F# 2.0 Language Specification and Visual F# documentation.

Tags:

F#

Covariance and Contravariance in C# 4.0

by Marc Sigrist 20. March 2011 02:07

C# 4.0 allows to declare variance compatibility for delegates and interfaces. This means, for instance, that one can assign an IEnumerable<Cat> to an IEnumerable<Animal>.  The term variance compatibility, in this context, defines the kind of assignment compatibility between two closed generic types, which exists when the parameters of those types are derived from each other (or are themselves variant to each other). In other words: Given two types T1<P1> and T2<P2>,  variance defines how T1 is assignment compatible with T2 in cases where P1 is in an inheritance relationship with P2 (or is itself variant to P2). A more detailed definition can be found in the C# 4.0 language specification, section 13.1.3 Variant type parameter lists. There are three kinds of variance:

Kind of Variance Delegate Example Interface Example
Invariance
delegate T Clone<T>(T t);
interface IList<T>{
    T this[int index] { getset; }
    // Etc.
}
Covariance
delegate T Func<out T>();
interface IEnumerator<out T>{
T Current { get; }
};
Contravariance
delegate void Action<in T>(T t);
interface IComparer<in T>{
int Compare(T x, T y);
}

Invariance

In the above table, Clone<T> and IList<T> are invariant in T. As a consequence, it is not possible to assign Clone<Dog> to Clone<Animal>, or vice versa. This is because T is used both as an incoming parameter and an outgoing parameter at the same time. Imagine what would happen if one could actually assign an IList<Dog> to an IList<Animal>. If we then retrieved animals[0], we would get a dog as animal. So far, so good. However, what would happen if we set animals[0] = new Cat()? What should the underlying IList<Dog> do when it gets the cat assigned? Should it perhaps throw an InvalidCastException? There is no way this can be handled without violation of the strong typing principle. Therefore, the core languages of the .Net Framework: C#, F#, and VB.NET (with option strict on) do not allow covariance or contravariance in this situation.

IList<Animal> animals = new Collection<Animal>();
IList<Cat> cats = new Collection<Cat>();
// The following line would produce a compiler error.
// animals = cats;
// Thanks to the above compiler error, we can always be sure
// that the following line will not produce a runtime exception.
animals.Add(new Dog());

Unfortunately, ever since C# 1.0, strong typing has not been completely enforced with regards to arrays (many other languages, e.g. Java, have the same problem). The following programming error is not prevented by the compiler:

Cat[] cats = { new Cat(), new Cat() };
Animal[] animals = cats; // Compiler allows covariance, eventhough in parameters exist.
animals[0] = new Dog(); // --> ArrayTypeMismatchException at runtime!

Here is an interesting side note: It is sometimes argued that breaking type safety with arrays was a planned, pragmatic decision at the time of C# 1.0, because generics did not exist yet. However, according to Don Syme, who was responsible for generics in the CLR, back then it was not even certain whether generics would ever be introduced at all. Microsoft was reluctant, and the responsible research team was underfunded. The feature could only be introduced in C# 2.0 under extreme pressure at the very last minute. Luckily, things are different now. Runtime-integrated generics, and the many technologies built open them (such as Lambda expressions, Linq, and F#), have become a great success story, and they clearly distinguish Microsoft .Net and Mono from other popular development frameworks.

Covariance

In the above table, Func<out T> and IEnumerator<out T> are covariant in T. As a consequence, it is possible to assign Func<Cat> to Func<Animal>. Strong typing can be enforced by the compiler, because T is only used as outgoing parameter, never as incoming parameter. To enable covariance in T, T must be explicitly annotated with the generic modifier out.

Func<Animal> createAnimal = () => new Animal();
Func<Cat> createCat = () => new Cat();
createAnimal = createCat;
var a = createAnimal(); // Gets a cat as animal.

Contravariance

In the above table, Action<in T> and IComparer<in T> are contravariant. Therefore, it is possible to assign Action<Animal> to Action<Cat> or IComparer<Animal> to IComparer<Cat>. Strong typing can be enforced by the compiler, because T is only used as incoming parameter, never as outgoing parameter. To enable contravariance in T, it must be explicitly annotated with the generic modifier in.

Action<Animal> animalAction = animal => animal.Sleep();
Actionn<Cat> catAction = cat => cat.Meow();
catAction(new Cat()); // Meow...
catAction = animalAction;
catAction(new Cat()); // Zzz...

Other Considerations

Classes and structs cannot be declared as covariant or contravariant. Even if such a syntax were allowed, the feature would be useless in most cases. For instance, it would be logically impossible to assign a Collection<Cat> to a Collection<Animal>, because Collection<T> uses T both as an incoming parameter and an outgoing parameter. Every kind of collection, even if it is immutable, somehow needs a way to be built up (using T as incoming parameter) and a way to be read from (using T as outgoing parameter). Still, in some cases, where T is used only as incoming parameter or only as outgoing parameter, the feature might be practical (imagine some kind of Builder<out T> or Deserializer<out T>). However, the complexity of the C# compiler is stunning already today. For instance, given something as simple as an interface I1<out T>, it has to enforce type safety for extreme situations like I1<I1<I1<I2<I1<Pet>, I3<I2<Dog, I1<Cat>>>>>>>. But even if it can be proved that it is theoretically possible to create a compiler for C# who is sophisticated enough to check type safety for covariant or contravariant classes, it still does not necessarily make sense to spend the immense amount of time and resources it takes. Rather than doing this, I would prefer Microsoft to implement other features for the language, who take less effort, but are more urgent, such as read-only local "variables", an internal protected access modifier (as opposed to protected internal), and (my favorite wish) non-nullable reference types (if we have int? i, why not also have string! s? :)

I have covered the basics about variance in C#, the rest can mostly be concluded by logical deduction and combination (e.g., dealing with ref and out method parameters, etc.). However, if you truly want to dive into the matter, I recommend Eric Lippert's (of the C# compiler team) excellent twenty-one-part blog series on the subject.

Calculating a range of arbitrarily large prime numbers in F# 2.0

by Marc Sigrist 15. November 2010 20:30

The library System.Numerics.dll, who was introduced in .Net 4.0, contains a System.Numerics.BigInteger structure. BigInteger represents a whole number of arbitrary size (or precision). Before .Net 4.0, the largest number that could be represented "out of the box" was System.Double.MaxValue. Written in decimal notation, this would be a whole number with 309 digits (more than 179 thousand centillion). However, using Double for whole number calculations is error-prone. Double is internally stored with floating point logic; the larger the number, the less exact it becomes. For instance, you cannot exactly represent the number ten quadrillion (i.e., ten million billion):

let x = 1.0e+16
let y = x - 1.0
printf "%b" (x = y)
// Prints true! 

Through the introduction of System.Numerics.BigInteger, it is now possible for any .Net Framework language to exactly represent any whole number whatsoever. In the following example, we will use this type to implement a function that calculates a range of arbitrarily large prime numbers. We will design it as a static library method which can be called by any .Net 4.0 client application. The signature, seen from C#, should be as follows:

Desired Signature, as Seen From C#

using System.Collections.Generic;
using System.Numerics;

namespace MyCompany.MyProduct{
    public static class BigMath{
        public static IEnumerable<BigInteger> 
        PrimesBetween(BigInteger i, BigInteger j){
            // etc.

Implementation in F#

To implement the library method, proceed as follows:

  • (If not done yet: Install the F# Power Pack)
  • Create a new F# class library project
  • Set the .Net Framework 4 client profile as the compilation target
  • Add references to System.Numerics.dll and FSharp.PowerPack.dll
  • Add a new source file BigMath.fs with the following code:
/// Provides static methods for mathematical functions involving 
/// arbitrarily large numbers. 
module MyCompany.MyProduct.BigMath

/// <summary>Gets a lazily evaluated sequence of prime numbers.</summary>
/// <param name="i">The beginning of the interval for the prime numbers.</param>
/// <param name="j">The end of the interval for the prime numbers.</param>
/// <returns>
/// A sequence with the prime numbers between <paramref name="i"/> 
/// and <paramref name="j"/>.
/// </returns>
let PrimesBetween(i, j) =
    /// Approximates the square root of a BigInteger with a 
    /// BigRational, according to the "babylonian method". 
    let sqrtI i =
        let iN = BigRational.FromBigInt i
        let half n = n / 2N
        let rec approachWith n =
            let diff = BigRational.PowN(n, 2) - iN
            if diff >= 0N && diff < 1N then n
            else approachWith(half(n + iN / n))
        approachWith(half iN)

    /// Gets true if i can be divided by a number >= 2,
    /// where i is a non-negative BigInteger.
    let hasDivisor i =
        let maxDiv = 
            let sr = sqrtI i
            min (sr.Numerator / sr.Denominator + 1I) (i - 1I)
        let rec hasDiv div =
            if div > maxDiv then false
            elif i % div = 0I then true
            else hasDiv(div + 1I)
        hasDiv 2I   

    /// Gets true if i is a prime number. 
    let isPrime i =
        match i with
        | _ when i < 2I -> false
        | _ when i = 2I -> true
        | _ -> not (hasDivisor i)

    /// The sequence of numbers between i and j.
    let range =
        let step = i |> compare j
        match step with
        | 0 -> Seq.singleton i
        | _ -> seq {i .. bigint step .. j}

    /// The resulting sequence of prime numbers between i and j.
    range |> Seq.filter isPrime  

Usage from C#

The compiled F# library can be used from C# as follows:

// using System;
// using MyCompany.MyProduct;
var primes = BigMath.PrimesBetween(10000200, 10000150);
foreach (var p in primes)
    Console.WriteLine(p.ToString("#,#"));
// Produces:
// 10,000,189
// 10,000,169

Concluding Remarks

The parameters of the PrimesBetween function are declared in tupled (not curried) form, which corresponds to par. 4.2 "Object and Member Design" of the F# Component Design Guidelines, which says "Do not use currying of parameters in vanilla .NET APIs".

All recursive functions are implemented tail recursively, using accumulator arguments, so that no stack overflow will ever occur.

The result is a strongly typed generic enumerable of BigInteger. At any given time, no more than one prime number is held in memory, regardless of the size of the interval between i and j.

The square root calculation in the sqrtI function is an optimization. To know whether a number has a divisor, it is sufficient to try division by all numbers between 2 and the square root. For the calculation of the square root, we use the type Microsoft.FSharp.Math.BigRational from FSharp.PowerPack.dll.

To calculate extremely large prime numbers in a productive situation, we would have to speed up the function using a cache. Perhaps unexpectedly, this cache would not necessarily store the resulting prime numbers. Instead, it would be gradually built with all prime numbers from the bottom up, starting at 2, whenever the recursive hasDiv function is called. The hasDiv function would then be modified to no more try out all whole numbers starting from 2 as potential divisors, but only all (recursively cached) primary numbers starting from 2, which is sufficient. This would enormously reduce the amount of divisions. The next step would then be to persist the cache in a database. The resulting library could be run for many years, returning larger and larger prime numbers, until (presumably) the currently calculated BigInteger number would be so large as to overstrain the system memory. I leave it up to you to speculate approximately when this might happen...