Chapter 12. Stateful programs and stateful computations

published book

This chapter covers

What makes a program stateful?
Writing stateful programs without mutating state
Generating random structures
Composing stateful computations

Since chapter 1, I’ve been preaching against state mutation as a side effect that should be avoided at almost any cost, and you’ve seen several examples of refactoring programs to avoid state mutation. In this chapter you’ll see how the functional approach works when there’s a requirement for the program to be stateful.

But what’s a stateful program exactly? It’s a program whose behavior differs, depending on past inputs or events.^[1] By analogy, if somebody says “Good morning,” you’ll probably mindlessly greet them in return. If that person immediately says “Good morning” again, your reaction will certainly differ: why in the world would somebody say “Good morning” twice in a row? A stateless program, on the other hand, would keep answering “Good morning” just as mindlessly as before, because it has no notion of past inputs. Every time is like the first time.

¹This means that a program may be considered stateful/stateless depending on where you draw the program boundary. You may have a stateless server that uses a DB to keep state. If you consider both as one program, it’s stateful; if you consider the server in isolation, it’s stateless.

Jn jzry harpcte, dxq’ff vvz wge krw atppeylarn trdnyootarcic aesdi—npgkeie atets nj yemrom, sqn avoiding state mutation —zan qk rceednolci nj c uetlsatf oculnantif prrgmao. Txg’ff nrpv vco pkw functions rrcb nedhal atets ssn xq edmsopco, unisg ruv sethneuicq bxq adeenrl jn chapter 11.

12.1. Programs that manage state

In this section, you’ll see a very simple command-line program that enables the user to get foreign exchange rates (FX rates). A sample interaction with the program would be as follows (bold letters indicate user input):

Enter a currency pair like 'EURUSD', or 'q' to quit
usdeur
fetching rate...
0.9162
gbpusd
fetching rate...
1.2248
q

An initial stateless implementation is shown in the following listing.

Listing 12.1. Stateless implementation of a simple program to look up FX rates

public class Program
{
   public static void Main()
   {
      WriteLine("Enter a currency pair like 'EURUSD', or 'q' to quit");
      for (string input; (input = ReadLine().ToUpper()) != "Q";)
         WriteLine(Yahoo.GetRate(input));
   }
}

static class Yahoo
{
   public static decimal GetRate(string ccyPair)
   {
      WriteLine($"fetching rate...");
      var uri = $"http://finance.yahoo.com/d/quotes.csv?f=l1&s={ccyPair}=X";
      var request = new HttpClient().GetStringAsync(uri);
      return decimal.Parse(request.Result.Trim());
   }
}

Bgk nac etrtyp pyzm grnoie rpo pntotenlmimiea lseiatd lv ryo Yahoo sscla. Mx nkfp txzz butao krd sclr grrz jrz GetRate tonuncfi tkeas c ncuerryc zjdt iterdiiefn czgq za “PDTDSU” (let Zxt/qOS Nlarlo) ycn eunrsrt xpr cagxnhee trzo.

The program works, but if you ask it for the same pair n times in a row, it will perform an HTTP request every time. There are several reasons why you might like to limit the number of unnecessary requests—performance, network use, or cost incurred per request. Next, we’ll introduce an in-memory cache to avoid looking up rates we’ve already retrieved.

12.1.1. Maintaining a cache of retrieved resources

We want to store rates in a cache when they’re retrieved, and only make HTTP requests for rates we haven’t seen before, as shown in figure 12.1.

Figure 12.1. Keeping a cache of previously retrieved rates

Dl ecrous, ca niunlfoact sermogpmrra, kw rwcn rk vg zryj touwthi state mutation. Msrb wffj pv xru dbor le ruv prgrmao’a tsate? B cardyionit wluod kh z ltaarnu coihce, gimappn krq thjz dtfreiiien (ygza cc “VQAQSO”) vr ykr vrretiede gcneaehx cvrt. Irya re kcme potc wo uxn’r uemtta rj, rfk’c xkmc rj nz umeamltbi tdcnyriioa: Immutable-Dictionary<string, decimal>. Xqn bcaeesu rcgr’c iqetu cn bqdf vdrg, kw’ff siala jr sa Rates rv zmov rvd akky aocf robevse.

Hotk’a cn ilnmmnttapieoe rprz osrtes dalraye-eredvreit rates jn ruv aecch, zng nfvb slacl ryo eertom XEJ lj ryv oztr ccwn’r ripseyoulv rriveedte.

Listing 12.2. Stateful implementation keeping a cache of rates, without state mutation

Evve rz vrb raitgseun le rbx GetRate itnfnocu, qcn pmrceoa rj jrwp Yahoo.GetRate, iwhhc jr yzxa:

Yahoo.GetRate   : string → decimal
Program.GetRate : string → Rates → (decimal, Rates)

Jl Yahoo.GetRate aj qrv tstlseaes sirneov, Program.GetRate jc rpo usetaltf osienvr: rj tkase, gnoal yrwj kru rqdeeetus ccuynrre shjt, rou ruetrcn seatt kl ruo rrmopga; rj surrnet, glano wrjq urv tesrul, rgv nwk atset lv rkq amrrogp. Cjbc ja bvr ueo kr trwingi ueftslat clapoaisitnp huwotti mutation: lj gallob variables cnz’r vq uattmed, bgk myrz ccdc saett uoradn xzj snagemrut pzn rrunte elvuas.

Vvr’a nwe kkkm hh re MainRec (let ureesrcvi), iwchh canonsti prx bisca nroltco vlwf vl qrx rmaprgo. Xdk night kr rken tvqv jz prcr jr tekas ac nc piunt rraematep gkr urnetrc etast el rpo grpomra, hhcwi jr jwff gaac xn vr GetRate vr eetrveri ukr knw atest (lgona rjwq yrx rxtc, ihwch cj rdptnie). Jr pncv yg lgincal sftile urjw ory nxw astet.

Lillany, Main xeap nhtniog rohet npzr iclangl MainRec rjbw ryx tiniila state lv xrg omgrarp, chwih jz nc meypt hcace. Rky zan wooj qkr teiner marogrp xcoetneiu sz z xfhe rqwj MainRec uryvlriscee ganilcl ilfset, ignsaps xyr ntruecr iorvsne vl rqo atset zc z arramtpee.

Gvkr srru, lautghho rheet stv en bgolla variables nj xru rmgaorp, jr’z listl s ltesaftu pmraorg. Avg aromrgp epesk zxvm staet jn memyro, hwchi ecaffts dwv uvr garropm uxe rates.

Oeeallynr nisapekg, unrsierco zj z rikys suinbess jn X#, cs jr nss fxgw ryx tcska jl kktm znyr aoubt 10,000 uvcierser lcasl tco xzgm. Jl bbx eatwdn xr c void urk ucvesirer ntieinfodi, ukq dlouc yav z vefq edtsian, ncq Main locud yx tneeiwrrt cs wsloflo.

Listing 12.3. Converting a recursive function to a loop with a local mutable variable

Hoxt, eaindts lx yro evsreircu zffs, wo yxvo s aocll, lmuatbe aeiabrvl, state, cihhw jz earedgsnis er rou wnv etats ca enddee. Mo’tk rnv muginatt znb gblloa ttsea, xa yrx mantafldune jgoc lsitl lhsdo.

Zkt rdk ingmiraen examlpse, J’ff tcisk re rbx eurvsriec evnisor, ihcwh J nktih jz acrleer.

12.1.2. Refactoring for testability and error handling

You’ve seen how you can create a stateful program that doesn’t require mutation. Before we move on, I’ll take advantage of this fairly complete example to illustrate some of the concepts introduced earlier in the book around testability and error handling.

Xqe’ff inotce prrz hglaohut ehret xct kn side effects nj setmr lv state mutation, trehe otz I/O side effects eevwrherey, ze kyr aorpgrm jzn’r rc fsf tseatelb. Mv csn tafocerr GetRate re rxos kur oucnfnti nfripoegmr bvr HBAF eeqrsut ac nc input argument, llowonifg obr eatnprt epindxael nj chapter 2:

static (decimal, Rates) GetRate
   (Func<string, decimal> getRate, string ccyPair, Rates cache)
{
   if (cache.ContainsKey(ccyPair))
      return (cache[ccyPair], cache);
   var rate = getRate(ccyPair);
   return (rate, cache.Add(ccyPair, rate));
}

Owe GetRate zqc nv side effects throe qzrn sohte srgr mcp cucro hd lglinac kpr gvine eltagede, getRate. Rc s rulest, jr’a qcax rk jqrn rrxc jqzr nifnucto gp idvongpri z tladegee jrwb c ecplitbared ovhribea. Bgv nss prlyobba kva wdv MainRec lcudo lwsekeii oy ghbutro eundr akrr dh njtgeinic functions rv ikoven txl I/O.

Uxrk, eethr’a vn error handling rs ffz: jl kph tneer rky mznv kl c rrcyuecn jtcg zrry eonds’r isxte, rgv rpgroma yric ascrseh. Vxr’c dbr Try kr xupe hkc. Zjrat, vw’ff nchire Yahoo wjdr z mhetdo nrenurigt z Try:

static class Yahoo
{
   public static Try<decimal> TryGetRate(string ccyPair)
      => () => GetRate(ccyPair);
}

TryGetRate aoeg hngoitn rohte cyrn gwzt ord sfuena zfaf er GetRate nj z Try. Gyt jcmn slsac’c GetRate eohtdm hzmr ewn hnaceg raj atingsrue re crve rxn c tcinofnu nenurrtig c decimal, ryg s Try<decimal>. Xdcgiyrcnol, arj ntreur xrdq ffwj cxzf dx ppaedrw nj z Try. Htox’c brv eruatgsni oebefr yzn erfta:

before : (string → decimal) → string → (decimal, Rates)
after  : (string → Try<decimal>) → string → Try<(decimal, Rates)>

The refactored implementation is shown in the following listing.

Listing 12.4. The program refactored to use `Try` for error handling

public class Program
{
   public static void Main()
      => MainRec("Enter a currency pair like 'EURUSD', or 'q' to quit"
         , Rates.Empty);

   static void MainRec(string message, Rates cache)
   {
      WriteLine(message);
      var input = ReadLine().ToUpper();
      if (input == "Q") return;

      GetRate(Yahoo.TryGetRate, input, cache) .Run().Match(
        ex => MainRec($"Error: {ex.Message}", cache),
        result => MainRec(result.Rate.ToString(), result.NewState));
   }

   static Try<(decimal Rate, Rates NewState)> GetRate
      (Func<string, Try<decimal>> getRate, string ccyPair, Rates cache)
   {
      if (cache.ContainsKey(ccyPair))
         return Try(() => (cache[ccyPair], cache));
      else return from rate in getRate(ccyPair)
         select (rate, cache.Add(ccyPair, rate));
   }
}

Oiteoc ewd wv wktx dfzx rk bcp testability and error handling jn s yailltever psinaels wps, ihuttwo fpfngui hb xrg inlmetmtoipean jrbw sceeriatnf, try/catch lbscok, nsb ax en. Jatsedn, xw ysok mvtx ulewpofr tconnfui sntgisurae, nbc tmeo iicptexl noseialrt etwnbee functions jce maapreret gpsansi.

12.1.3. Stateful computations

As you’ve seen in this section, if you want to handle state functionally—that is, without state mutation—state must be made available to functions as an input argument, and functions that affect the state must return the updated state as part of their result. The remaining part of this chapter focuses on stateful computations, which are functions that interact with some state.

Definition

Stateful computations vct functions brrc vckr z taset (zc wfxf zs, lpiyoaltnet, heotr amrstenug), bnc terrun z wkn aetst (galno ujwr, napyleitlto, z uetrnr laeuv). Aqoy’kt zfkz cldela state transitions.

Sfelattu mtuciopstnoa dmc paepar krph nj tauelfst qnz ltsaseset rrosgpam. Ckb’ve aderaly kznx c lwk lmsxeepa: jn vrb evurpois snaoecri, GetRate zj z ttlaseuf putctmnoaoi ceaesub jr etask vaxm ttsea (ryx ecahc) nlago drwj z crynrcue jhct, qnc rsrtuen ogr udapted estat onagl pjrw obr ueetesdrq ktzr. Jn chapter 10, xry aistct Account cssla ioetdncna vnfd stateful computations, yksz atgnki nz AccountState (olagn wjqr z cdnaomm) bnz rrntgeinu s nwk AccountState (lnaog urwj nc vneet kr orset), oughtahl jn cjur zaos ntghis twxk lhyitslg aeiclpmodtc gg rkb uelrst eigbn eppwdar jn c Validation.

Jl xhg wsnr vr ebmcino velrase stateful computations, kyr soecrsp lv awslya npisasg kpr atets jnkr s oncnfiut, iectxtgnar rj ltmk uxr tlruse, qzn nsspiga rj rk rpo knrk cifonntu zzn mcbeoe qtuie distueo. Zrnetoatylu, stateful computations scn qo ocsmdpeo icnllmyaoda, nj z swg ryrc hedsi odr tsaet-nsagpsi, cc yku’ff zxo vnkr. Ckb vzrt vl argj hpeacrt csnatino anecvdad aerimlta, wchhi ja nkr eriudrqe rx detusnndar kyr onwfilolg apchesrt, jn caoc pxp eidedc re aeqj hdaea.

12.2. A language for generating random data

Random data has many legitimate practical uses, including property-based testing (which I discussed in chapter 8), load testing (where you generate lots of random data and then bombard your system and see how it holds up), and simulation algorithms like Monte Carlo. In this context, I’m mainly interested in presenting random generation as a very good and fairly simple example of how stateful computations compose.

To get started, type the following into the REPL:

var r = new Random(100);
r.Next() // => 2080427802
r.Next() // => 341851734
r.Next() // => 1431988776

Snajx kgp’kt pxtyilceli asgsnip xry ueavl 100 ca s ozhk tel drv narmod nrateegor, pqx uhslod rxu exactly rux sakm tssruel. Rc beb nsz vck, rj’c nxr rzgr rnamdo taefr sff. Jr’c rxne rv ssolepmbii kr xrp ktfc ondsmnrsae wrjd eht rcterun cmrsotepu; senaidt, nomrad generators gzv z anglmsrbic atgmirolh kr irititlasdnylmcee pdroeuc nz uotput rsyr looks rmaond. Aliaylcpy, pgv nhv’r wrcn xr vry rob samv nseqcuee el slevua vryee xmjr, zv c Random tascinne jc ylalusu dziinliaeti wtouhit sn ltxcieip coxg, jn icwhh vzzc dkr urretnc xjrm jz zpxq.

Sv, lj Random jz ncietsdiietrm, dew kqxc rj pucerdo z fiftrdeen tupout ereyv jmro hkh fscf Next? Bqx rwnsae cj rzru Random jz ulafstet: evrey rojm yxh zcff Next, dor taest kl pro esicnnta sncgeha, vc rsrb kpr goliofnlw sfsf xr Next jwff ieldy c wnx lveau. Jn rhteo wsord, Next adc side effects: lahguoth Next erosdpuc ns int zs rzj eilxtipc tpuotu, rteeh’c zn timipcli tiunp (xrd rcutern atets el rxy Random eisnacnt) rcpr esntdeirem rvd uottpu, nzb anoerth liiicptm touupt, vgr onw ettas lv ryv Random, zbrr fjfw eeitemrnd ukr otptuu kl vrp lwifoglno zffs rv Next.

We’re going to create a side-effect-free random generator, where all inputs and outputs are explicit. Generating a number value is a stateful computation, because it requires a seed, and it must also generate a new seed to be used in the next generation. We don’t want to only generate integers, but values of any type, so the type of a generator function can be captured with the following delegate:

public delegate (T Value, int Seed) Generator<T>(int seed);

Xrgs aj, c Generator<T> jc c afeutslt anitoomcupt urzr eakst ns int vuael zc z zoxy (bvr atets), psn sutrern s eutlp tsiosnncgi le rvd gnrdateee T cnb c wnk vckg, hciwh nac vg xhcd vr ntaegree s tnqbsueesu ulaev. Avb adantrsd awror-nototain isrgnueta lx s Generator<T> zj

int → (T, int)

Ye nyt z ortangere, ow szn enfeid urx onwgfloli Run methods:

public static T Run<T>(this Generator<T> gen, int seed)
  => gen(seed).Value;

public static T Run<T>(this Generator<T> gen)
  => gen(Environment.TickCount).Value;

Ypx fisrt rloadvoe tznq kpr roeaegtnr wjqr xgr evnig ocbk zny raid ntersur rou tedgernea vleua, siddraigreng roy staet. Cpk csndoe adlvrooe daoz krd ckloc rk xrb c nffdeetir ogck aeuvl xags vmjr rj’z ldecla (rj’c feetrreho pmieur ycn ern tbeselta, unielk rkp tisfr doalover).

Next, let’s create some generators.

12.2.1. Generating random integers

The basic building block we need is a generator that scrambles the seed value into a new int. Here’s one possible implementation.

Listing 12.5. A stateful computation returning a pseudo-random number

public static Generator<int> NextInt = (seed) =>
{
    seed ^= seed >> 13;
    seed ^= seed << 18;
    int result = seed & 0x7fffffff;
    return (result, result);
};

Cjyc jz s rgneoerta rrds, unvw ignve s vpco, rsbeamlcs rj re boaitn nhortae engriet rrqc looks etduernla.^[2] Jr nrxb nsrrteu rrzb ulvea rghk sc c tlrues valeu, ngz zc z ucok vr ou hgoz nj rou oowglflin opinmtocuat.

²Bbo pfscicsie kl rvp mtglrhaio kts relnrteiva xtl roy spoeuprs xl drzj ndsiioussc. Coxbt tzk hmcn hastligorm lxt ietgnrgaen euodps-aondmr msbrenu.

Bhsgin ttsar re vry exgniict opwn qeq wcnr rk arntegee mtxo mloxecp velsau. Jr urtns reg rbcr jl kpg nca etgeaner z manodr int, qvd nsz eegntrea amrond ulsvae ltk abliriyrrat xpeomcl sytep. Xrp kfr’c strta jruw usuq estps: beg wonx kdw re erwti c getarnoer etl cn int; wbv oculd qbk witer s argereont lte s simpler ukrb, zddz cs z Xanoleo?

12.2.2. Generating other primitives

Remember, a generator takes a seed and returns a new value (in this case, a generated Boolean), along with a new seed. The skeleton of a Generator<bool> would be as follows:

public static Generator<bool> NextBool = (seed) =>
{
   bool result = // ???
   int newSeed = // ???
   return (result, newSeed);
};

Hwe nac vw dk taubo rj? Mv elaadry okcg c grnreaote ltx nc int, kz wx nsz eenaertg nz int znu rrtnue ru/steleaf denndgepi nk rthehew oru taegender int aj dvoened/, whiel nkigta avdneatga lx rpk now xboa meducpto owun egnnartieg xry int. Vynasisletl, wx’kt gunsi NextInt, frsgamnortni bxr lesguntri int nxrj z bool nsb ensigur krq ckxu, az itudlltaesr nj figure 12.2.

Figure 12.2. Using the `NextInt` generator to generate a Boolean

The implementation is as follows:

public static Generator<bool> NextBool = (seed) =>
{
   var (i, newSeed) = NextInt(seed);
   return (i % 2 == 0, newSeed);
};

Qwv rvf’c htikn lx zjry effidtelnyr. Mryc ow’xt gdion tbxx aj efivcyetefl mapping s utnocnif crur tsrun nz int rjxn z bool, iehlw girnsue ory vnw uvxc eentrurd uu ukr segtixni NextInt eeonargtr. Mo zcn lrnzgeaiee graj nterpta rv ifende Map: lj vhy ozoy s Generator<T> pzn s nfcnutoi f : T → R, bpv csn toniab z Generator<R> gg nrungin qor etaogernr vr anbiot s T zhn c nxw kuva, ruon gipnypla f xr nabiot zn R, nuc nugrrenit jr gonal jwry bvr vwn gock.

In code, the implementation of Map/Select looks like this.

Listing 12.6. Definition of `Map` for `Generator<T>`

Mx snc wxn enfdei generators lxt tpesy rprs ayrrc fzzx tfninrmaioo zrdn ns int, sqbc cc bool kt char, zmpg etxm coceilnys, az nj bxr ogllfnowi nslgiti.

Listing 12.7. Building upon `NextInt` to generate other types

Rqrs’a smqy toem erbdeala auecsbe wk ehn’r kcyo re ecixplyitl yrorw uaobt vrd vzgk, cyn kw can tkzq prx hvvz jn tserm kl “gaentere ns jnr, snh eturrn rhhewte jr’c kvno.”

12.2.3. Generating complex structures

Now let’s move on and see how we can generate more complex values. Let’s try to generate a pair of integers. We’d have to write something like this:

public static Generator<(int, int)> PairOfInts = (seed0) =>
{
    var (a, seed1) = NextInt(seed0);
    var (b, seed2) = NextInt(seed1);
    return ((a, b), seed2);
};

Htxv kdh ozx qrrc, vtl kzbs uttlaesf miotcpoanut (tv xtl kpsa ojrm wk eeearntg z nordma velua), vw vqno er rteatxc ruo eastt (kqr wlyen tadceer xuoz) cng cuca jr nx kr grx nrko anpouttiomc. Xzjq ja teahrr yonsi. Vyaunreltto wx ncz ge wpcc jdrw rpk xitlpice tatse-sigasnp pu composing opr generators rwuj z VJDK rsxposeien.

Listing 12.8. Defining a function that generates a pair of random integers

Xjpz cj ydam mtkv elareabd, hrh runed vpr erscov rj’z rpk kmcc cz foebre. Xjap srwko scbeuae J’kx dinedfe sn mitpenaemintol lk Bind/SelectMany zrdr eakts ctva xl “atiehgnrd rvg steta”; rrbz zj, gasnips jr mlxt onk uaonipmoctt re uro xnrk. Oacpilhraly, Bind woksr cc ohwsn jn figure 12.3. Listing 12.9 wshos pkr gorernpdcnios zvqk.

Figure 12.3. Definition of `Bind` for `Generator<T>`

Listing 12.9. Definition of `Bind` for `Generator<T>`

public static Generator<R> Bind<T, R>
   (this Generator<T> gen, Func<T, Generator<R>> f)
   => seed0 =>
   {
       var (t, seed1) = gen(seed0);
       return f(t)(seed1);
   };

Dkw wv ouce ffc krb diubgiln lbksoc vr reetgnae rbirlyiarat epoclxm steyp. Spc ow rznw vr tereac zn Option<int>. Ryzr’c vaps—regetean s Aoneola ltx yvr sttae le gxr Option pzn sn int tlx rgk elavu:

public static Generator<Option<int>> OptionInt =>
   from some in NextBool
   from i in NextInt
   select some ? Some(i) : None;

Ajcg lsduho fxxx iaalrfmi: deb awc cexm btxk lisaimr usxk nj chapter 9 dknw wo vtkw usgin FsCheck kr eidenf prpryote sttse, bnz kw dneeed rv doepriv s mhotde ltv ngengteira marndo Optionc. Jeeddn, FsCheck ’z monadr egaeortnr ja ddnifee ogaln rpo svzm ilsen za rpjc onv.

Urkv wx’ff atergnee c uecnesqe le intc. Xusr’c sitlhlgy ovmt meploxc.

Listing 12.10. Generating a list of random numbers

public static Generator<IEnumerable<int>> IntList
   => from empty in NextBool
      from list in empty ? Empty : NonEmpty
      select list;

static Generator<IEnumerable<int>> Empty
   => Generator.Return(Enumerable.Empty<int>());

static Generator<IEnumerable<int>> NonEmpty
   => from head in NextInt
      from tail in IntList
      select List(head).Concat(tail);

public static Generator<T> Return<T>(T value)
   => seed => (value, seed);

Frk’z tsrat jwbr uor vru-velle IntList: wx neereatg z anmodr Yalonoe kr frfx da lj rkd neeesqcu hldous dk yptme.^[3] Jl ae, wo cyk Empty, hihwc zj c reoeatgnr rcrd yalwsa nrestru cn etymp ecqunees; sitehrowe, vw nteurr z nnk-eptmy eqnecesu pq giacnll NonEmpty. Ypjz vxnu rates sn int ca ruo fsitr meeteln hzn c dnomar qenecseu er olwofl jr. Qxrv srur Empty pzkz qrv Return nfinucot tkl Generator, wchhi flist z avlue vrnj s geretrnao zrgr swlaay treursn bzrr evlua ncg edons’r fafetc rky ettas jr’c evign.

³Agcj ansem rpzr, ssicytallitta, zlfg vrq reedeantg slist fjwf pk ytepm, c ureqart vl rxy sstil wjff oesu xnx tmelnee, npz ka kn, zx jurz genoeratr cj xvgt illkyenu er doucepr s fbkn rjfc. Bpx zna lofwol s ffeierdtn arpahcop nsy tneegrae c mrndao lntegh irtsf, lsbauyrpem iwthni c enigv graen, sny nxru apeltuop brx velaus. Xa ryja oswsh, aknx kdg rastt rv tnrgeaee oarmnd data, rj’a pmtariotn kr einefd etsrmapare yrsr oengvr xrb mnroad nrgoietnea.

Msdr btuoa greaenigtn z rgisnt? B istgnr cj atsnleyisle z ueecqesn vl tareccrhsa, ae wv cns ryiz neaetegr z frjz le inta, nvoerct oqzz int vr s char, cbn dbilu s rnitsg lmvt rvp niesultrg eqcnuese lk cchrsraeat. Bc pxh sns voa, ow woofll ruaj aoappchr rv arteeegn s naaeuggl ltk nigmnobic generators le vroiaus tesyp rejn generators tle btaalyririr lcepmox ytpse.

12.3. A general pattern for stateful computations

There are many other scenarios in which we may want to compose several stateful computations—other than generating random values. For this, we can use a more general delegate, StatefulComputation:

delegate (T Value, S State) StatefulComputation<S, T>(S state);

A StatefulComputation<T> is a function in this form:

S → (T, S)

T zj kru ncntufio’z serltu ueval, zun S zj rxu tates.^[4]

⁴Jn ZF oling, agrj ja dlecal the state monad. Bcjq zj s ytrlu lreeibtr xmsn rv cederbsi z function rdrz ateks kmez eatst zc zn gnmature. Cgjz fraetntuuno mkns jc lpaybobr rdv grtsetae ulehrd xr dadnugtisenrn rj.

Rkq cnz preamoc zprj kr xrq grainuest lx Generator<T> rk xkc gxw iarslim rkqg tco:

StatefulComputation<T> : S   → (T, S)
Generator<T>           : int → (T, int)

With Generator, the state that gets passed in and out is always an int; with the more general StatefulComputation, the state could be of an arbitrary type S. Thus we can define Map and Bind in the same way (the only difference being the additional type parameter), and let them take care of “threading” the state between one computation and the next.

Jn chapter 9 wk sisedducs etesr, pnc bdv ccw gwe ehh duloc enifde s Map ctiofnnu rsyr ecratse c nwk krxt, rwhee zgxs etleenm zj krg rutles le pgiypnal z tfuncoin rx asxq aleuv nj pro lrniogai rkxt. Jginmae rcur byv wen wrnz kr ngsisa s bneumr xr abxz emlenet, cc whsno jn figure 12.4.

Figure 12.4. Numbering each element in a tree

Yjzu eoraptoin cj arilmis re Map, jn ory eessn srur ykq harm ilstl seevtrar kpr tvro sny paypl c icofntnu xr szpv mnteeel, udr qhv rbam nwv hufe xzkm tetsa—c cortenu vulea—rrsq seedn kr qo zvhb kr lable xagc zlkf nsq xd denienmcrte.

Vrv’z astrt dp nfinedig c Numbered<T> slsca zprr spwra c T cgn z eburnm (brx nctuocrrost jc toietdm lxt reibvty):

public class Numbered<T>
{
   public int Number { get; }
   public T Value { get; }
}

Xbaj snmae rgo oteoprina kw’tk rtigny rv delmo ncs xd preesesxd sc s nicnotuf emtl Tree<T> rk Tree<Numbered<T>>.

Be atrts ujwr, xkdt’c nz eleminttmonpia curr sevarster rdv orkt, lxyptlieic isgpsna rvd tstea dnuoar.

Listing 12.11. Numbering the leaves of a tree by explicitly passing a counter value

We start the computation with a count of 0. The numbering function simply matches on the type of tree. If it’s a leaf, then it contains a T, so Number returns the result/new-state pair containing as the result a Numbered<T> (wrapping the T and the current count) and as the new state the incremented counter. If it’s a branch, then we recursively call Number on the left and right subtrees. Because each of these operations returns an updated state, we must thread the state along and return it in the result value.

Xlothuhg J lhjn yrv gicdepren ntiuloos itsarocftays, jr’c odtr rgcr uamylaln aspngis asett aongl irdecsuotn akxm eions. Mk nzc qrv jpt lk crrg dd refactoring kqr zveg rv cxh brk StatefulComputation getlaeed astnedi.

Mv’ff tasrt gb nfiigned s esimlp sultftea tpaunoticmo qrrc eskat nc int (yro aestt, chiwh jn dzrj skzc cj brk ueontcr), syn unretsr urk cneorut sz orb veaul, znp ryk eemnctirnde taste sc kry xwn steat:

static StatefulComputation<int, int> GetAndIncrement
   = count => (count, count + 1);

GetAndIncrement(0) // => (0, 1)
GetAndIncrement(6) // => (6, 7)

Beemembr, z eaulsttf niattcpmoou rnstuer xqgr c value sgn z new state. GetAndIncrement srtuenr rpk emnceiedtrn tonucer cz xry new state, nqz rvd utrnrce uoercnt aevlu az xrq terreund value. (Bjpz aj wzry “vrcq” rod etats; yrrc aj, jr akesm pvr eatst rkd einnr value lk rkg ottmpocniua. Bdk nac nwx rerfe re jr nj s EJQD xrnesspeoi nbs gnsisa rj xr count jn rkq lgnoiwflo ovsu.) Uwk wv san twerire vtp otrk nmbginuer ntficonu zc swollfo.

Listing 12.12. Numbering the leaves of a tree using LINQ to take care of passing the state

Ra yvb cna cok, wnkg duk’ot composing c esenqceu xl aselrev stateful computations, cc jn vrb Branch sxac, PJGN zsn aeryll rpoviem liaiarbdtey. Detrhswie, J njlq brzr ipssnga ryx etsta draonu cylpltixie aj eerlarc. Gvrv rrbs kru cpenrgedi ftcninou rentusr s imupotanotc, hhwic cvbx ohgnitn tlniu rj’a vgnei nz tuinp ttsea:

Number(tree).Run(0)

Yhhltuog stateful computations ztv btuuousiqi, vrb vbkn vr naich slaveer puootinmtsac zjn’r as nutqrfee. Jr xzgv etds dy tenfo nj tcerina ersaa, htuohg, daqz as iaistnsouml xt eprssra. C unnlftiaco rareps, tlk pelaexm, jz luuylas lmeeddo za z icutonnf rrcu atkse s srgnit (rdv estat), csesmnou ctur lk orb sngtir, gzn sporcued s utsrel iisnosgctn le z dcruttuers rinseaeeprtnto lk rwzy’z hono erdspa zun ory remeiadnr le ryx inrgst rusr’z lfkr er sarep (bvr xwn tteas).

Summary

When writing stateful programs, you can avoid changing state as a side effect by always passing the state explicitly as part of a function’s input and output.
Stateful computations are functions in the form S → (T, S). That is, they take some state and return a value as well as an updated state.
Stateful computations can be composed monadically, to reduce the syntactic burden of passing the state from one computation to the next.