Fibonacci Variations as a Library-Based Infinite Sequence in F# 3.1

In C#, Fibonacci numbers are usually calculated with a loop. In F#, however, Fibonacci numbers can be calculated in at least eight different ways (with a loop, the Seq module, different kinds of recursion, plus variants thereof). Using a loop would be the least F#-idiomatic approach. This post uses the Seq module.

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.)

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#.)

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

This article has described how to implement Fibonacci numbers with an infinite sequence, using F# core library functions, literals, and .NET types.