Archive | Functor

# Pure Functional Memoization

There are many computation problems that resonate through the ages. Important Problems. Problems that merit a capital P.

The Halting Problem…

P versus NP…

The Fibonacci sequence…

The Fibonacci sequence is a super-important computation Problem that has vexed mathematicians for generations. It’s so simple!

``````fibs 0 = 0
fibs 1 = 1
fibs n = (fibs \$ n - 1) + (fibs \$ n - 2)``````

Done! Right? Let’s fire up ghci and find out.

``````*Fibs> fibs 10
55``````

… looking good…

``````*Fibs> fibs 40

``````

… still waiting…

``````
102334155
``````

… Well that sure took an unfortunate amount of time. Let’s try 1000!

``````*Fibs> fibs 1000
*** Exception: <<You died before this returned>>``````

To this day, science wonders what `fibs(1000)` is. Well today we solve this!

## Memoization

The traditional way to solve this is to use Memoization. In an imperative language, we’d create an array of size n, and prepopulate `arr[0] = 0` and `arr[1] = 1`. Next we’d loop over 2 to n, and for each we’d set `arr[i] = arr[i-1] + arr[i-2]`.

Unfortunately for us, this is Haskell. What to do… Suppose we had a map of the solutions for 0 to i, we could calculate the solution for i + 1 pretty easily right?

``````fibsImpl _ 0 = 0
fibsImpl _ 1 = 1
fibsImpl m i = (mo + mt)
where
mo = Map.findWithDefault undefined (i - 1) m
mt = Map.findWithDefault undefined (i - 2) m``````

We return 0 and 1 for i = 0 and i = 1 as usual. Next we lookup n – 1 and n – 2 from the map and return their sum. This is all pretty standard. But where does the map come from?

It turns out that this is one of those times that laziness is our friend. Consider this code:

``````fibs' n = let m = fmap (fibsImpl m)
(Map.fromList (zip [0..n]
[0..n])) in
Map.findWithDefault undefined n m``````

When I first saw this pattern (which I call the Wizard Pattern, because it was clearly invented by a wizard), I was completely baffled. We pass the thing we’re creating into the function that’s creating it? Unthinkable!

It turns out that this is just what we need. Because of laziness, the fmap returns immediately, and `m` points to an unevaluated thunk. So, for i = 0, and i = 1, fibsImpl will return 0 and 1 respectively, and the map will map 0 -> 0 and 1 -> 1. Next for i = 2, Haskell will attempt to lookup from the map. When it does this, it will be forced to evaluate the result of i = 0 and i = 1, and it will add 2 -> 1 to the map. This will continue all the way through i = n. Finally, this function looks up and returns the value of fibs n in linearish time. (As we all know, Map lookup isn’t constant time, but this is a lot better than the exponential time we had before)

So let’s try it out.

``````*Fibs> fibs' 1
1
*Fibs> fibs' 10
55
*Fibs> fibs' 40
102334155``````

… so far so good…

``````*Fibs> fibs' 100
354224848179261915075
*Fibs> fibs' 1000
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
*Fibs> fibs' 10000
33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875
*Fibs> fibs' 100000
2597406934722172416615503402127591541488048538651769658472477070395253454351127368626555677283671674475463758722307443211163839947387509103096569738218830449305228763853133492135302679278956701051276578271635608073050532200243233114383986516137827238124777453778337299916214634050054669860390862750996639366409211890125271960172105060300350586894028558103675117658251368377438684936413457338834365158775425371912410500332195991330062204363035213756525421823998690848556374080179251761629391754963458558616300762819916081109836526352995440694284206571046044903805647136346033000520852277707554446794723709030979019014860432846819857961015951001850608264919234587313399150133919932363102301864172536477136266475080133982431231703431452964181790051187957316766834979901682011849907756686456845066287392485603914047605199550066288826345877189410680370091879365001733011710028310473947456256091444932821374855573864080579813028266640270354294412104919995803131876805899186513425175959911520563155337703996941035518275274919959802257507902037798103089922984996304496255814045517000250299764322193462165366210841876745428298261398234478366581588040819003307382939500082132009374715485131027220817305432264866949630987914714362925554252624043999615326979876807510646819068792118299167964409178271868561702918102212679267401362650499784968843680975254700131004574186406448299485872551744746695651879126916993244564817673322257149314967763345846623830333820239702436859478287641875788572910710133700300094229333597292779191409212804901545976262791057055248158884051779418192905216769576608748815567860128818354354292307397810154785701328438612728620176653953444993001980062953893698550072328665131718113588661353747268458543254898113717660519461693791688442534259478126310388952047956594380715301911253964847112638900713362856910155145342332944128435722099628674611942095166100230974070996553190050815866991144544264788287264284501725332048648319457892039984893823636745618220375097348566847433887249049337031633826571760729778891798913667325190623247118037280173921572390822769228077292456662750538337500692607721059361942126892030256744356537800831830637593334502350256972906515285327194367756015666039916404882563967693079290502951488693413799125174856667074717514938979038653338139534684837808612673755438382110844897653836848318258836339917310455850905663846202501463131183108742907729262215943020429159474030610183981685506695026197376150857176119947587572212987205312060791864980361596092339594104118635168854883911918517906151156275293615849000872150192226511785315089251027528045151238603792184692121533829287136924321527332714157478829590260157195485316444794546750285840236000238344790520345108033282013803880708980734832620122795263360677366987578332625485944906021917368867786241120562109836985019729017715780112040458649153935115783499546100636635745448508241888279067531359950519206222976015376529797308588164873117308237059828489404487403932053592935976454165560795472477862029969232956138971989467942218727360512336559521133108778758228879597580320459608479024506385194174312616377510459921102486879496341706862092908893068525234805692599833377510390101316617812305114571932706629167125446512151746802548190358351688971707570677865618800822034683632101813026232996027599403579997774046244952114531588370357904483293150007246173417355805567832153454341170020258560809166294198637401514569572272836921963229511187762530753402594781448204657460288485500062806934811398276016855584079542162057543557291510641537592939022884356120792643705560062367986544382464373946972471945996555795505838034825597839682776084731530251788951718630722761103630509360074262261717363058613291544024695432904616258691774630578507674937487992329181750163484068813465534370997589353607405172909412697657593295156818624747127636468836551757018353417274662607306510451195762866349922848678780591085118985653555434958761664016447588028633629704046289097067736256584300235314749461233912068632146637087844699210427541569410912246568571204717241133378489816764096924981633421176857150311671040068175303192115415611958042570658693127276213710697472226029655524611053715554532499750843275200199214301910505362996007042963297805103066650638786268157658772683745128976850796366371059380911225428835839194121154773759981301921650952140133306070987313732926518169226845063443954056729812031546392324981793780469103793422169495229100793029949237507299325063050942813902793084134473061411643355614764093104425918481363930542369378976520526456347648318272633371512112030629233889286487949209737847861884868260804647319539200840398308008803869049557419756219293922110825766397681361044490024720948340326796768837621396744075713887292863079821849314343879778088737958896840946143415927131757836511457828935581859902923534388888846587452130838137779443636119762839036894595760120316502279857901545344747352706972851454599861422902737291131463782045516225447535356773622793648545035710208644541208984235038908770223039849380214734809687433336225449150117411751570704561050895274000206380497967960402617818664481248547269630823473377245543390519841308769781276565916764229022948181763075710255793365008152286383634493138089971785087070863632205869018938377766063006066757732427272929247421295265000706646722730009956124191409138984675224955790729398495608750456694217771551107346630456603944136235888443676215273928597072287937355966723924613827468703217858459948257514745406436460997059316120596841560473234396652457231650317792833860590388360417691428732735703986803342604670071717363573091122981306903286137122597937096605775172964528263757434075792282180744352908669606854021718597891166333863858589736209114248432178645039479195424208191626088571069110433994801473013100869848866430721216762473119618190737820766582968280796079482259549036328266578006994856825300536436674822534603705134503603152154296943991866236857638062351209884448741138600171173647632126029961408561925599707566827866778732377419444462275399909291044697716476151118672327238679208133367306181944849396607123345271856520253643621964198782752978813060080313141817069314468221189275784978281094367751540710106350553798003842219045508482239386993296926659221112742698133062300073465628498093636693049446801628553712633412620378491919498600097200836727876650786886306933418995225768314390832484886340318940194161036979843833346608676709431643653538430912157815543512852077720858098902099586449602479491970687230765687109234380719509824814473157813780080639358418756655098501321882852840184981407690738507369535377711880388528935347600930338598691608289335421147722936561907276264603726027239320991187820407067412272258120766729040071924237930330972132364184093956102995971291799828290009539147382437802779051112030954582532888721146170133440385939654047806199333224547317803407340902512130217279595753863158148810392952475410943880555098382627633127606718126171022011356181800775400227516734144169216424973175621363128588281978005788832454534581522434937268133433997710512532081478345067139835038332901313945986481820272322043341930929011907832896569222878337497354301561722829115627329468814853281922100752373626827643152685735493223028018101449649009015529248638338885664893002250974343601200814365153625369199446709711126951966725780061891215440222487564601554632812091945824653557432047644212650790655208208337976071465127508320487165271577472325887275761128357592132553934446289433258105028633583669291828566894736223508250294964065798630809614341696830467595174355313224362664207197608459024263017473392225291248366316428006552870975051997504913009859468071013602336440164400179188610853230764991714372054467823597211760465153200163085336319351589645890681722372812310320271897917951272799656053694032111242846590994556380215461316106267521633805664394318881268199494005537068697621855231858921100963441012933535733918459668197539834284696822889460076352031688922002021931318369757556962061115774305826305535862015637891246031220672933992617378379625150999935403648731423208873977968908908369996292995391977217796533421249291978383751460062054967341662833487341011097770535898066498136011395571584328308713940582535274056081011503907941688079197212933148303072638678631411038443128215994936824342998188719768637604496342597524256886188688978980888315865076262604856465004322896856149255063968811404400429503894245872382233543101078691517328333604779262727765686076177705616874050257743749983775830143856135427273838589774133526949165483929721519554793578923866762502745370104660909382449626626935321303744538892479216161188889702077910448563199514826630802879549546453583866307344423753319712279158861707289652090149848305435983200771326653407290662016775706409690183771201306823245333477966660525325490873601961480378241566071271650383582257289215708209369510995890132859490724306183325755201208090007175022022949742801823445413711916298449914722254196594682221468260644961839254249670903104007581488857971672246322887016438403908463856731164308169537326790303114583680575021119639905615169154708510459700542098571797318015564741406172334145847111268547929892443001391468289103679179216978616582489007322033591376706527676521307143985302760988478056216994659655461379174985659739227379416726495377801992098355427866179123126699374730777730569324430166839333011554515542656864937492128687049121754245967831132969248492466744261999033972825674873460201150442228780466124320183016108232183908654771042398228531316559685688005226571474428823317539456543881928624432662503345388199590085105211383124491861802624432195540433985722841341254409411771722156867086291742124053110620522842986199273629406208834754853645128123279609097213953775360023076765694208219943034648783348544492713539450224591334374664937701655605763384697062918725745426505879414630176639760457474311081556747091652708748125267159913793240527304613693961169892589808311906322510777928562071999459487700611801002296132304588294558440952496611158342804908643860880796440557763691857743754025896855927252514563404385217825890599553954627451385454452916761042969267970893580056234501918571489030418495767400819359973218711957496357095967825171096264752068890806407651445893132870767454169607107931692704285168093413311046353506242209810363216771910420786162184213763938194625697286781413636389620123976910465418956806197323148414224550071617215851321302030684176087215892702098879108938081045903397276547326416916845445627600759561367103584575649094430692452532085003091068783157561519847567569191284784654692558665111557913461272425336083635131342183905177154511228464455136016013513228948543271504760839307556100908786096663870612278690274831819331606701484957163004705262228238406266818448788374548131994380387613830128859885264201992286188208499588640888521352501457615396482647451025902530743172956899636499615707551855837165935367125448515089362904567736630035562457374779100987992499146967224041481601289530944015488942613783140087804311431741858071826185149051138744831358439067228949408258286021650288927228387426432786168690381960530155894459451808735197246008221529343980828254126128257157209350985382800738560472910941184006084485235377833503306861977724501886364070344973366473100602018128792886991861824418453968994777259482169137133647470453172979809245844361129618997595696240971845564020511432589591844724920942930301651488713079802102379065536525154780298059407529440513145807551537794861635879901158192019808879694967187448224156836463534326160242632934761634458163890163805123894184523973421841496889262398489648642093409816681494771155177009562669029850101513537599801272501241971119871526593747484778935488777815192931171431167444773882941064615028751327709474504763922874890662989841540259350834035142035136168819248238998027706666916342133424312054507359388616687691188185776118135771332483965209882085982391298606386822804754362408956522921410859852037330544625953261340234864689275060526893755148403298542086991221052597005628576707702567695300978970046408920009852106980295419699802138053295798159478289934443245491565327845223840551240445208226435420656313310702940722371552770504263482073984454889589248861397657079145414427653584572951329719091947694411910966797474262675590953832039169673494261360032263077428684105040061351052194413778158095005714526846009810352109249040027958050736436961021241137739717164869525493114805040126568351268829598413983222676377804500626507241731757395219796890754825199329259649801627068665658030178877405615167159731927320479376247375505855052839660294566992522173600874081212014209071041937598571721431338017425141582491824710905084715977249417049320254165239323233258851588893337097136310892571531417761978326033750109026284066415801371359356529278088456305951770081443994114674291850360748852366654744869928083230516815711602911836374147958492100860528981469547750812338896943152861021202736747049903930417035171342126923486700566627506229058636911882228903170510305406882096970875545329369434063981297696478031825451642178347347716471058423238594580183052756213910186997604305844068665712346869679456044155742100039179758348979935882751881524675930878928159243492197545387668305684668420775409821781247053354523194797398953320175988640281058825557698004397120538312459428957377696001857497335249965013509368925958021863811725906506436882127156815751021712900765992750370228283963962915973251173418586721023497317765969454283625519371556009143680329311962842546628403142444370648432390374906410811300792848955767243481200090309888457270907750873638873299642555050473812528975962934822878917619920725138309388288292510416837622758204081918933603653875284116785703720989718832986921927816629675844580174911809119663048187434155067790863948831489241504300476704527971283482211522202837062857314244107823792513645086677566622804977211397140621664116324756784216612961477109018826094677377686406176721484293894976671380122788941309026553511096118347012565197540807095384060916863936906673786627209429434264260402902158317345003727462588992622049877121178405563348492490326003508569099382392777297498413565614830788262363322368380709822346012274241379036473451735925215754757160934270935192901723954921426490691115271523338109124042812102893738488167358953934508930697715522989199698903885883275409044300321986834003470271220020159699371690650330547577095398748580670024491045504890061727189168031394528036165633941571334637222550477547460756055024108764382121688848916940371258901948490685379722244562009483819491532724502276218589169507405794983759821006604481996519360110261576947176202571702048684914616894068404140833587562118319210838005632144562018941505945780025318747471911604840677997765414830622179069330853875129298983009580277554145435058768984944179136535891620098725222049055183554603706533183176716110738009786625247488691476077664470147193074476302411660335671765564874440577990531996271632972009109449249216456030618827772947750764777446452586328919159107444252320082918209518021083700353881330983215894608680127954224752071924134648334963915094813097541433244209299930751481077919002346128122330161799429930618800533414550633932139339646861616416955220216447995417243171165744471364197733204899365074767844149929548073025856442942381787641506492878361767978677158510784235702640213388018875601989234056868423215585628508645525258377010620532224244987990625263484010774322488172558602233302076399933854152015343847725442917895130637050320444917797752370871958277976799686113626532291118629631164685159934660693460557545956063155830033697634000276685151293843638886090828376141157732003527565158745906567025439437931104838571313294490604926582363108949535090082673154497226396648088618041573977888472892174618974189721700770009862449653759012727015227634510874906948012210684952063002519011655963580552429180205586904259685261047412834518466736938580027700252965356366721619883672428226933950325930390994583168665542234654857020875504617520521853721567282679903418135520602999895366470106557900532129541336924472492212436324523042895188461779122338069674233980694887270587503389228395095135209123109258159006960395156367736067109050566299603571876423247920752836160805597697778756476767210521222327184821484446631261487584226092608875764331731023263768864822594691211032367737558122133470556805958008310127481673962019583598023967414489867276845869819376783757167936723213081586191045995058970991064686919463448038574143829629547131372173669836184558144505748676124322451519943362182916191468026091121793001864788050061351603144350076189213441602488091741051232290357179205497927970924502479940842696158818442616163780044759478212240873204124421169199805572649118243661921835714762891425805771871743688000324113008704819373962295017143090098476927237498875938639942530595331607891618810863505982444578942799346514915952884869757488025823353571677864826828051140885429732788197765736966005727700162592404301688659946862983717270595809808730901820120931003430058796552694788049809205484305467611034654748067290674399763612592434637719995843862812391985470202414880076880818848087892391591369463293113276849329777201646641727587259122354784480813433328050087758855264686119576962172239308693795757165821852416204341972383989932734803429262340722338155102209101262949249742423271698842023297303260161790575673111235465890298298313115123607606773968998153812286999642014609852579793691246016346088762321286205634215901479188632194659637483482564291616278532948239313229440231043277288768139550213348266388687453259281587854503890991561949632478855035090289390973718988003999026132015872678637873095678109625311008054489418857983565902063680699643165033912029944327726770869305240718416592070096139286401966725750087012218149733133695809600369751764951350040285926249203398111014953227533621844500744331562434532484217986108346261345897591234839970751854223281677187215956827243245910829019886390369784542622566912542747056097567984857136623679023878478161201477982939080513150258174523773529510165296934562786122241150783587755373348372764439838082000667214740034466322776918936967612878983488942094688102308427036452854504966759697318836044496702853190637396916357980928865719935397723495486787180416401415281489443785036291071517805285857583987711145474240156416477194116391354935466755593592608849200546384685403028080936417250583653368093407225310820844723570226809826951426162451204040711501448747856199922814664565893938488028643822313849852328452360667045805113679663751039248163336173274547275775636810977344539275827560597425160705468689657794530521602315939865780974801515414987097778078705357058008472376892422189750312758527140173117621279898744958406199843913365680297721208751934988504499713914285158032324823021340630312586072624541637765234505522051086318285359658520708173392709566445011404055106579055037417780393351658360904543047721422281816832539613634982525215232257690920254216409657452618066051777901592902884240599998882753691957540116954696152270401280857579766154722192925655963991820948894642657512288766330302133746367449217449351637104725732980832812726468187759356584218383594702792013663907689741738962252575782663990809792647011407580367850599381887184560094695833270775126181282015391041773950918244137561999937819240362469558235924171478702779448443108751901807414110290370706052085162975798361754251041642244867577350756338018895379263183389855955956527857227926155524494739363665533904528656215464288343162282921123290451842212532888101415884061619939195042230059898349966569463580186816717074818823215848647734386780911564660755175385552224428524049468033692299989300783900020690121517740696428573930196910500988278523053797637940257968953295112436166778910585557213381789089945453947915927374958600268237844486872037243488834616856290097850532497036933361942439802882364323553808208003875741710969289725499878566253048867033095150518452126944989251596392079421452606508516052325614861938282489838000815085351564642761700832096483117944401971780149213345335903336672376719229722069970766055482452247416927774637522135201716231722137632445699154022395494158227418930589911746931773776518735850032318014432883916374243795854695691221774098948611515564046609565094538115520921863711518684562543275047870530006998423140180169421109105925493596116719457630962328831271268328501760321771680400249657674186927113215573270049935709942324416387089242427584407651215572676037924765341808984312676941110313165951429479377670698881249643421933287404390485538222160837088907598277390184204138197811025854537088586701450623578513960109987476052535450100439353062072439709976445146790993381448994644609780957731953604938734950026860564555693224229691815630293922487606470873431166384205442489628760213650246991893040112513103835085621908060270866604873585849001704200923929789193938125116798421788115209259130435572321635660895603514383883939018953166274355609970015699780289236362349895374653428746875``````

Neat. Even that last one only took a few seconds to return!

# Again, This Time In Reverse!

Today we’ll be doing Exercise 5 from The C Programming Language. Today’s exercises aren’t terribly challenging, but there is some good stuff in here. The problem is:

Modify the temperature conversion program to print the table in reverse order, that is, from 300 degrees to 0.

I bet you thought we were done with temperature conversion, didn’t you? I’m right there with you, but luckily for us, this is also the section that introduces the `for` loop, so this is much less tedious. The new program for modification:

``````#include <stdio.h>

int main (int argc, char ** argv)
{
for (int fahr = 0; fahr <= 300; fahr = fahr + 20)
{
printf("%3d %6.1f\n", fahr, (5.0/9.0)*(fahr-32));
}
}``````

I made a few minor modifications. I gave `main` the correct signature to keep gcc from complaining, and I also moved the initialization of `fahr` to the loop. As you may know this is not valid C, and the compiler will throw an error. You might also know that this was made to be valid C in the C 99 revision. To compile this, you just need to add the `-std=c99` flag to your gcc call.

To complete this exercise, you only need to modify the loop declaration. Change this line…

``for (int fahr = 0; fahr <= 300; fahr = fahr + 20)``

…to this…

``for (int fahr = 300; fahr >= 0; fahr = fahr - 20)``

Pretty straight forward stuff here. `fahr` starts at 300 instead of 0, and the loop continues so long as it remains greater than 0. Instead of adding 20 each iteration, we subtract it. This can be compiled like so:

``gcc -std=c99 -Wall ex5.c -o ex5``

## In Haskell

Unfortunately, the authors of The C Programming Language did not see fit to include a starting Haskell program for us to modify. This seems like a pretty serious oversight to me, but we’ll just have to make due. Luckily for us, we can use the temperature conversion program I wrote for the last entry in this series. This program handles conversions, and we can use it to produce a table of all conversions between 0 and 300 degrees.

While I’ve established that Haskell does in fact have loops, we won’t be using them here. Instead we’ll be using ranges, functors, and sequencing to solve this problem in a more functional way.

First, we need a list of every 20th number between 0 and 300:

``[300.0, 280.0 .. 0.0]``

The `..` there basically says “You get the idea, do that.” If you put enough information into it so that the compiler can figure out the pattern, and start and end points, the compiler will fill the rest in. In this case, I gave the first two values, telling the compiler I want increments of 20, and I gave it the last value so it knows where to stop.

Unfortunately, as you recall, my conversion program needs members of the `Temperature` typeclass. Surely I don’t plan to make `Double` a member, right? Right. We need to map a function over this list to produce a list of `Temperature`s. But what function should we use?

Something that beginning Haskellers may not realize is that constructors are in fact functions!

``````Prelude> :t Just
Just :: a -> Maybe a

Prelude> :t Left
Left :: a -> Either a b``````

…and of course…

``````*Main> :t Fahrenheit
Fahrenheit :: Double -> Fahrenheit``````

That’s right, we can `map Fahrenheit` over a functor just like any other function!

``map Fahrenheit [300.0, 280.0 .. 0.0]``

This will produce a list of every 20th `Fahrenheit` temperature between 300 and 0. However, we aren’t done yet. We actually need a list of `Conversion`s, because this type is required for our `insertConv` function. To get this we can `map toConversion` over this list:

``map toConversion \$ map Fahrenheit [300.0, 280.0 .. 0.0]``

…but that’s starting to get a bit ugly, there must be a better way. Normally, I’m not terribly fond of function composition, in this case it will make our life easier.

## Function Composition

Haskell provides an operator `.` that is used for function composition. Let’s take a look at its type:

``````Prelude> :t (.)
(.) :: (b -> c) -> (a -> b) -> a -> c``````

The composition operator takes a function that takes some type `b` as an argument, and that returns some type `c`. It takes a second function that takes some type `a` as an argument, and that returns some type `b`. Finally, it returns some type `c`.

What does this do for us? Basically, it takes a function `a -> b`, and a function `b -> c`, and turns them into a function `a -> c`. Let’s see an example:

``````Prelude> :t show
show :: Show a => a -> String``````

The function `show` takes a member of the `Show` typeclass and returns a `String`.

``````Prelude> :t putStr
putStr :: String -> IO ()``````

The function `putStr` takes a `String`, and returns an `IO` action.

``````Prelude> :t putStr . show
putStr . show :: Show a => a -> IO ()``````

When we compose the two functions, we get a function that takes a member of the `Show` typeclass, and returns an `IO` action.

Logically, calling `putStr . show someShowable` is the same as calling `putStr \$ show someShowable` or `putStr (show someShowable)`. However, `putStr . show` is a valid function, where `putStr \$ show` and `putStr (show)` are compiler errors if you don’t give `show` an argument.

How does this help us?

``````*Main> :t Fahrenheit
Fahrenheit :: Double -> Fahrenheit

*Main> :t toConversion
toConversion :: (Temperature a, Temperature b) => a -> (a, b)

*Main> :t toConversion . Fahrenheit
toConversion . Fahrenheit :: Temperature b => Double -> (Fahrenheit, b)``````

By composing `toConversion` and `Fahrenheit`, we end up with a function that takes a `Double` as an argument and returns a `Conversion` from `Fahrenheit`. We can then `map` this function over our list of `Double`s:

``map (toConversion . Fahrenheit) [300.0, 280.0 .. 0.0]``

Next, we need to turn these `Conversion`s into `TableBuilder`s. This is a simple matter of composing `insertConv`:

``map (insertConv . toConversion . Fahrenheit) [300.0, 280.0 .. 0.0]``

The type of this new function is:

``````:t (insertConv . toConversion . Fahrenheit)
(insertConv . toConversion  . Fahrenheit) :: Double -> TableBuilder ()``````

…or at least it would be if the type inferrer could figure out the type of `toConversion`. Unfortunately for us, it can’t because the implementation is purposely ambiguous. We need to add a type signature to it:

``````(insertConv . (toConversion :: Fahrenheit -> (Fahrenheit, Celsius))
. Fahrenheit)``````

## Sequencing

Now we are ready to create our table. This part is actually very easy. Thanks to the library function `sequence_` we won’t even need a `do` block. What does this function do? Let’s look at its signature:

``````Prelude> :t sequence_
sequence_ :: Monad m => [m a] -> m ()

Prelude> :t sequence
sequence :: Monad m => [m a] -> m [a]``````

There are two variations of this function. The first, `sequence_` evaluates each monadic action, and ignores the results. Basically, suppose we have some function: `func :: a -> Monad b`

``````let mList = map func ["foo", "bar", "baz"]
in sequence_ mList``````

…is equivalent to…

`````` do func "foo"
func "bar"
func "baz"
return ()``````

The second variation evaluates each monadic action, and returns a list of all the results. Suppose we have our same function: `func :: a -> Monad b`

``````let mList = map func ["foo", "bar", "baz"]
in sequence mList``````

…is equivalent to…

``````do foo <- func "foo"
bar <- func "bar"
baz <- func "baz"
return [foo, bar, baz]``````

If you have a list of monads, you can use `sequence` or `sequence_` to have them all evaluated. Use `sequence` if you care about the resulting values, use `sequence_` if you only care about the monad’s side effect. Which do we want? Let’s look at the signature of `insertConv`:

``````*Main> :t insertConv
insertConv
:: (Temperature a, Temperature b) =>
Conversion a b -> TableBuilder ()``````

If we were to use `sequence`, we’d get a resulting value with the type `TableBuilder [()]`. Since nobody has any use for a list of empty tuples, we’ll be using `sequence_`.

So, what does our main look like?

``````main = do temps <- return (map (insertConv . (toConversion :: Fahrenheit -> (Fahrenheit, Celsius))
. Fahrenheit)
[300.0, 280.0 .. 0.0])
putStrLn \$ prettyPrint \$ buildTable \$ do sequence_ temps``````

This produces the following output:

``````------------------------------
|| Fahrenheit || Celsius    ||
------------------------------
|| 300.0      |> 148.9      ||
|| 280.0      |> 137.8      ||
|| 260.0      |> 126.7      ||
|| 240.0      |> 115.6      ||
|| 220.0      |> 104.4      ||
|| 200.0      |> 93.3       ||
|| 180.0      |> 82.2       ||
|| 160.0      |> 71.1       ||
|| 140.0      |> 60.0       ||
|| 120.0      |> 48.9       ||
|| 100.0      |> 37.8       ||
|| 80.0       |> 26.7       ||
|| 60.0       |> 15.6       ||
|| 40.0       |> 4.4        ||
|| 20.0       |> -6.7       ||
|| 0.0        |> -17.8      ||
------------------------------``````

# A Trip To The Magical Land Of Monads

Monads can be a tricky topic. On the surface, they’re not hard at all. Taking `Maybe` for instance:

``````Prelude> Just 1
Just 1
Prelude> Nothing
Nothing``````

That couldn’t possibly be easier. Something is either `Just [something]`, or it is `Nothing`. However Monad world is the magical world of gotchas, unenforceable rules, and magical syntax. I had been planning on writing a post on Monads, much like I did with Applicatives and Functors. While researching this topic, I’ve determined that I’m not qualified to speak on this subject yet.

I am qualified to discuss the usage of Monads. I feel that say you are going to “learn how to do Monads” is similar to saying you are going to “learn how to do data structures”. Data structures are similar to each other in that they serve a common purpose: to contain data. However, a Vector is nothing like a Linked List, which is nothing like a Hash Map.

Similarly, a `Maybe` is nothing like an `IO`, which is nothing like a `Writer`. While they are all Monads, they serve different purposes. Today, I’d like to lay some groundwork on the topic and talk about binding functions.

## On Magical Syntax

Much like `Functor` and `Applicative`, `Monad` brings functions that allow you to use normal values with monadic values. `Monad` brings the `>>=` operator. This operator is called the bind operator. (this is important for monads in general, but I won’t get into this today. Just know that the operator’s name is bind) The signature for `>>=` is:

``(>>=) :: m a -> (a -> m b) -> m b``

As you can see, it takes a `Monad` that contains an `a`, a function that takes an `a` and returns a `Monad b`, and returns a `Monad b`. Basically, it calls the function on the value contained in the monad, and does whatever additional action is appropriate for the monad, and returns a monad containing the result. In short: it is `fmap` for `Monad`s. Let’s take a look at a quick example for `Maybe`:

``````Prelude> Just 1 >>= (\a -> Just \$ a + 5)
Just 6``````

As you can see, we bind `Just 1` to a function that takes a value, adds it to 5, and wraps the result in a `Just`, which results in `Just 6`. Bind will correctly handle `Nothing` as well:

``````Prelude> Nothing >>= (\a -> Just \$ a + 5)
Nothing``````

Still with me? Good, because things are about to get magical.

## Do Notation

Monads are so special, they have their own magical syntax! When working with monads, you may use `do` notation. What does do notation look like? Let’s take a look at a sample function:

``````justAdd :: (Num a) => a -> a -> Maybe a
justAdd a b = Just \$ a + b``````

This function takes 2 numbers, adds them, and wraps them up in a `Maybe`. Nothing earth shattering here. Let’s take a look at how to work with these using Bind:

``````justAddDemoBind = justAdd 2 2 >>= (justAdd 4)

justAddDemoBindNothing = Nothing >>= (justAdd 4)``````

I’ve defined 2 simple functions here. The first calls `justAdd 2 2`, which returns `Just 4`. The function `(justAdd 4)` is then applied to it using the bind operator, which will return `Just 8`. The second attempts to apply the function `(justAdd 4)` to `Nothing`. Since the bind operator is smart enough to handle this, the final result of this function is `Nothing`. Simple, really. Now, let’s see `do` notation in action:

``````justAddDemoDo = do
first <- justAdd 2 2
justAdd 4 first

justAddDemoDoNothing = do
first <- Nothing
justAdd 4 first``````

Looks like a completely different language, right? In fact, these two functions do the exact same thing as the previous two. The purpose of `do` notation is to make working with Monads easier. In practice, if your logic is non-trivial, you end up with hugely nested statements. To see what’s going on, let’s break `justAddDemoDo` down:

``justAddDemoDo = do``

In the first line, we open our `do` block.

``first <- justAdd 2 2``

In the second line, we call `justAdd 2 2`, and assign the result to the name `first`. Notice that `<-` operator? That works basically the same as it does in list comprehensions, it does the assigning.

``justAdd 4 first``

Finally, we add 4 to first, resulting in `Just 8`, which is the value returned from the function. It seems like we’re treating our monad contained in `first` as a regular value. This is part of the magic of `do` notation. In fact, if this line were written as:`justAdd first 4` it would have worked.

Another very important thing to note is that the last line of a do block must be an expression that returns a Monad! GHCI will throw a fit if it’s not.

## The Pervasiveness Of Do

As you can see, under the hood, `do` notation just uses the `>>=` operator. You can also see that it is much simpler and cleaner looking than using the bind operator. However, that doesn’t mean that `do` is better. Like many things, it comes down to personal choice.

When reading literature on Haskell, you should be prepared to interpret `do` blocks, and usage of the bind operator. Like any tool, `do` and bind are not always the correct one. Picking the correct tool for the job is part of being a programmer. Hopefully this tutorial gave you enough familiarity to be able to use both.

# The Point Of Applicative Functors

A few weeks ago, we talked about Functors. In case you’ve forgotten, you might want to click that link and read the post, but long story short: Functors allow you to call functions that take “bare” values on “dressed up” values.

Functors had one big weakness though: you can only call a function that takes one argument. I justified this using function currying, but there is another way. Today, we’ll be talking about that other way: Applicative functors.

## Let’s Recap

Functors use a function called `fmap` to call a function on a functor. This function is called on the value within the functor, and a new functor containing the result is returned. This looks like this:

``````Prelude> fmap show \$ Just 1
Just "1"``````

I `fmap`‘d `show` over `Just 1`, which returns `Just "1"`. Let’s try another one:

``````Prelude> fmap (+ 1) \$ Just 1
Just 2``````

Here, we’ve used function currying to `fmap (+ 2)` over `Just 1`, which returns `Just 2`. This is all fine and good in a contrived situation such as adding 1 to 1, but what about the real world? As you probably know, you often don’t have some nice constants ready to use in your function. There must be a better way…

## Applicatives To The Rescue

To put it in layman’s terms, Applicative Functors are the middle ground. Let’s take a look at another example:

``````Prelude> let example = fmap (+) \$ Just 1
Prelude> :t example
example :: Maybe (Integer -> Integer)``````

If we `fmap (+)` over `Just 1`, the result is a function that takes an Integer and returns an Integer, wrapped in a `Maybe`. To do anything useful with this, you need to find a way to call this function on something else. That’s what Applicative Functors do for us. Let’s take a look at part of the class definition of Applicative:

``````class (Functor f) => Applicative f where
pure :: a -> f a
(<*>) :: f (a -> b) -> f a -> f b``````

We have two functions here: `pure`, which takes a value and wraps it in a minimal Functor, and `(<*>)`, which takes a functor that contains a function, and calls it on another functor which contains a value, returning a value. In a nutshell, this allows us to call multi-argument functions with functors. There’s one more function exported by `Control.Applicative` that bears mentioning: `(<\$>)`. `(<\$>)` is basically an alias for `fmap` that allows us to use `fmap` as infix:

``````Prelude> fmap (+1) \$ Just 2
Just 3

Prelude> (+1) <\$> Just 2
Just 3``````

As you can see, they function identically. Feel free to use `(<\$>)`, just know that it requires you to `import Control.Applicative`. Anyways, with that out of the way, here’s how you use an applicative. For this example, I will be adding 2 to 2. But 2 will be wrapped in a `Maybe` requiring extra steps:

``````Prelude> (+) <\$> Just 2  <*> pure 2
Just 4``````

Let’s talk about what just happened. First, I `fmap`‘d `(+)` over `Just 2` using the `(<\$>)` operator. This returns a function that takes an Integer and returns an integer wrapped in a `Maybe`. Next I used the `(<*>)` operator to call that function on `pure 2`, which returns `Just 4`.

You may be wondering why I used `pure 2` instead of `Just 2`. Sure, `Just 2` would have worked, but `pure 2` would have worked for any type of Applicative. Let’s take a look at another example:

``````Prelude> (+) <\$> [1,2,99,100]  <*> pure 2
[3,4,101,102]``````

As you can see, this is the exact same expression, except I used a List instead of a Maybe. This is where `pure` comes in handy. It allows you to write more generic code. `pure` works for any type of Applicative, therefore you needn’t concern yourself with what kind of Applicative is being passed into your function. You can rest easy knowing that it will work regardless.

## Hopefully That All Made Sense

Applicatives are a pretty abstract concept, and it can be difficult to visualize how they can be useful. This is a topic that I don’t feel is documented very well. It’s a topic I had trouble with for a while.

Since I suspect that most readers will find this post with a google search term like “what is the point of applicative functors”, hopefully I’ve shed some light on the topic for you.

# What Functors Can Do For You

One of the major aspects of Functional Programming, its lack of side effects, can be one of its major stumbling blocks. Sure, taking a value as a parameter and using it without creating a variable is a simple matter for basic types, but what of more complicated structures? How does one go about unwrapping a structure, operating on its value, and re-wrapping the value in said structure without losing it’s data? The answer is by using a convoluted set of functions that take way too many arguments just to preserve the state. Or, you could use a functor.

## So I Overload Operator()?

No, we aren’t talking about C++ Classes with an `operator()` implementation to make it look like a function. Functors in Haskell are a completely different animal. The easiest way to explain it is to look at an example. By way of example, let’s take a look at the `Maybe` monad:

``````data  Maybe a = Nothing | Just a
deriving (Eq, Ord)``````

As you can see, `Maybe` has two type constructors: `Nothing` or `Just something`. `Maybe` is used to represent a calculation that may have failed. If the calculation failed, `Nothing` is returned. If it succeeded, `Just whatever` is returned. This is all fine and good, but `Just whatever` isn’t the same thing as `whatever`; it is encapsulated in a `maybe`, and must be extracted if it is to be used.

How do you do that? Well, first you have to account for a `Nothing` value. Assuming you have a `Just`, you have to extract it, probably using a new function. Then you have to use the value. Afterwards, you probably want to put it back into the `Maybe`. Sounds like a lot of work, right? Let’s take a look at what `Functor` has to offer us:

``````class Functor f where
fmap :: (a -> b) -> f a -> f b``````

So, a functor defines 1 function (actually it defines more, but they have default implementations and can be ignored in 99% of cases) `fmap`, which takes a function that takes 1 argument of type `a` and returns a result of type `b`, a `Functor a`, and returns a `Functor b`. Basically, this amounts to fmap takes a function, calls it on the passed in functor, and returns a functor with the resulting value.

## Maybe This Is Helpful?

Let’s take a look at how this works with `Maybe`. Here is `Maybe`‘s `Functor` implementation:

``````instance Functor Maybe where
fmap _ Nothing  = Nothing
fmap f (Just a) = Just (f a)``````

Basically, if `fmap Nothing` is called, `Nothing` is returned. Otherwise, the passed in function is called on the value contained in the `Just`, and a new `Just` is returned with the result. This is a much more elegant way to deal with structures, there is no checking required, `fmap` knows how to do the right thing.

## A Bit Limiting

You may be thinking to yourself “Isn’t this a bit limiting? I can only `fmap` using a function that takes 1 argument!” You’d be right, if not for Haskell’s partial function application. Say we want to add 2 to the `Int` contained in a `Just`. If we didn’t have partial function application, we would have to do something ugly like this:

``fmap (\a -> a + 2) (Just 2)``

… or maybe something truly awful like this:

``````addTwo :: Int -> Int
addTwo a = a + 2``````

Luckily for us, we live in a just and righteous world where we can just partially apply `+`:

``fmap (+2) (Just 2)``

While this is a trivial example, I feel it adequately illustrates the point; you can `fmap` a function that takes any amount of arguments if you partially apply it!

This leads me to an important point that most literature leaves out: you must apply arguments from left to right, the order of arguments is important! When you’re writing functions, think about how users might want to partially apply them. Take these two functions for example:

``````padString1 :: String -> Int -> String
padString1 s 0 = s
padString1 s n = padString1 (s ++ "-") (n - 1)

padString2 :: Int -> String -> String
padString2 0 s = s
padString2 n s = padString2 (n - 1) (s ++ "-")``````

Both of these functions do the same thing: they take a `String` and an `Int`, and append n -‘s to the string. The difference is how they can be partially applied: `padString1` has the `String` first, so it can only be partially applied with the `String`. Conversely, `padString2` has the `Int` first, so it can only be partially applied with the `Int`. For this reason, when creating functions, take time to consider these issues. There’s probably a whole blog post to be written about not messing this up. Maybe when I feel qualified, I’ll write it! For now, just keep it in mind.

## Sounds Familiar

You’ve heard this word before, right? Map… But where?

``````instance Functor [] where
fmap = map``````

That’s right, `List`s are `Functor`s!. The `fmap` implementation for `List` just calls the `map` function that you’re probably familiar with. (if you need a refresher, it takes a function, a list, and returns a list with the function called on all members of the original list)

In fact, most structures in Haskell are `Functor`s. All `Monad`s in the standard library are `Functor`s, so it’s a good bet that you can `fmap` them. Either way, judicious use of `fmap` and `Functor`s can make your code much cleaner and more manageable.