Archive | ghci

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!

Consider this function:

``````headInTail :: [a] -> [a]
headInTail l = (tail l) ++ [head l]``````

Pretty straightforward, right? It takes a list, extracts the head and sticks it in the tail. Surely you’ve written something like this before. It should be fine, right?

``````*Main> headInTail [1,2,3]
[2,3,1]``````

…checks out. Let’s try a few more:

``````*Main> headInTail "hello"
"elloh"
["cat"]``````

…good. And the moment we’ve all been waiting for:

``````*Main> headInTail []
*** Exception: Prelude.tail: empty list``````

Oh yeah, `head` and `tail` don’t work for empty lists… Normally, we have some choices on how to proceed here. We could wrap the function in a `Maybe`:

``````maybeHeadInTail :: [a] -> Maybe [a]
maybeHeadInTail [] = Nothing
maybeHeadInTail l = Just \$ headInTail l``````

…which introduces an annoying `Maybe` to deal with just to stick our heads in our tails. Or, we could just do something with the empty list:

``````headInTail :: [a] -> [a]
headInTail [] = []
headInTail l = (tail l) ++ [head l]``````

…but what if returning the empty list isn’t the correct thing to do?

Another choice is to document this behavior (as `head` and `tail` do), and just never call `headInTail []`. But how can we guarantee that we never attempt to call this function on an empty list? Shouldn’t this be the type system’s problem?

Unfortunately, not all is roses and puppies. Sometimes the type system cannot help us. Sometimes somebody thought it’d be a good idea to use Haskell’s Evil exception system. Whatever the case, there are tools to help us.

Liquid Haskell is a static code analysis tool that is used to catch just these sorts of problems. Liquid Haskell allows us to define invariants which will be enforced by the tool. Liquid Haskell is a research project that is still in development. As such, it has some rough spots, however it’s still very much capable of helping us with our problem here. But before we begin, we need to get the tool installed.

To install the tool, execute:

``cabal install liquidhaskell``

…simple right? Unfortunately, we’re not quite done. We need to install an SMT solver. This tool is used by Liquid Haskell. Currently, the tool defaults to Z3. I’m not sure how to use a different solver (and Z3 works just fine), so I suggest you you Z3. You’ll have to build Z3, and place the binary somewhere on the `PATH`. After this is done, and assuming your `.cabal/bin` directory is also on the `PATH`, testing your source file is a simple as:

``liquid [FILE].hs``

Let’s Have A Look

Create a haskell source file that contains the following:

``````headInTail :: [a] -> [a]
headInTail l = (tail l) ++ [head l]``````

After that’s done, let Liquid Haskell analyze your file:

``liquid [YOUR_FILE].hs``

A bunch of stuff should scroll by, then in a second you’ll see something similar to the following:

``````**** UNSAFE *********************************************

Doop.hs:5:22: Error: Liquid Type Mismatch
Inferred type
VV : [a] | VV == l && len VV >= 0

not a subtype of Required type
VV : [a] | len VV > 0

In Context
VV : [a] | VV == l && len VV >= 0
l  : [a] | len l >= 0``````

If you go to the line and column indicated, you’ll find the argument to tail. Conveniently, it seems that Liquid Haskell comes pre-loaded with definitions for some library functions. Normally, you’ll have to define those yourself. In fact, let’s do just that.

The next logical step here is to write a specification for our function. This specification is a statement about what sorts of values the function can take. Add the following to your source file, in the line above the signature for headInTail:

``{-@ headInTail :: {l:[a] | len l > 0} -> [a] @-}``

If you re-run `liquid` on your source file, you’ll see that the warning went away, and the program now indicates that your source is “SAFE”. So, what does this refinement mean?

Basically, these refinements are machine-checked comments. They have no impact on the program, they exist for Liquid Haskell. Think of it as being like an enhanced type signature. Like a normal type signature, we start with the name of the function, then two colons. This part, however:

``{l:[a] | len l > 0}``

…should be new. Basically, this part says that the list should not be empty. You should read it as “l is a [a] such that len l is greater than zero.” A lot of the notation used by Liquid Haskell comes from formal logic. Let’s break this down some more:

``l:[a]``

Here we bind a symbol, l, to the first list argument. At any point to the right of this symbol until the end of the scope defined by `{}`, we can reference this symbol.

``{... | ...}``

The pipe symbol indicates that we are going to make some statement about the type on the left hand side.

``len l > 0``

Here we state that the length of l must be greater than 0. It looks like we are calling a function, and we sort of are; len is a measure which is a special function that is used in specifications. However, the subject of measures is a post for another day.

You may now be thinking: “Well this is all well and good, but what’s to stop me from calling this function on an empty list?” To answer that, let’s implement main:

``````main =
do i <- getLine
putStrLn \$ headInTail i``````

Add this to your source file, and then run `liquid [YOUR_FILE].hs` and you’ll notice that Liquid Haskell has a problem with your attempt to call `headInTail`:

``````**** UNSAFE *********************************************

Doop.hs:3:29: Error: Liquid Type Mismatch
Inferred type
VV : [Char] | VV == i && len VV >= 0

not a subtype of Required type
VV : [Char] | len VV > 0

In Context
VV : [Char] | VV == i && len VV >= 0
i  : [Char] | len i >= 0``````

Liquid Haskell is telling you that it can’t prove that the length of `i` is greater than 0. If you execute your main function, you should see that it works as expected. Type in a string, and it’ll do the right thing. Push enter right away and you’ll get an exception.

``````*Main> main
hello
elloh
*Main> main

*** Exception: Prelude.tail: empty list``````

…ick… Let’s fix this:

``````main =
do i <- getLine
case i of
[] -> putStrLn "Get your head checked."
_ -> putStrLn \$ headInTail i``````

Now if you analyze your file, Liquid Haskell should be happy. Honestly, you should be happy too: the tool caught this problem for you. It didn’t go to testing messed up, and the bug certainly didn’t escape testing unfound. Your program is now objectively better:

``````*Main> main
isn't that neat?
sn't that neat?i

*Main> main

I Wonder… Trinary Operators in Haskell

Often, while out for my daily run, I think about programming. Sometimes I think about my project, sometimes I think about upcoming projects, sometimes I think about the blog. Then there’s the times where I think about completely silly things like “I wonder if you can make an operator that takes three arguments?”

Wouldn’t that be grand.

I suppose I could just google it, but where’s the fun in that? Let’s give it a shot!

``````(+++) :: (Num a)
=> a
-> a
-> a
-> a
(+++) a b c = a + b + c``````

Here I’ve created a fairly straight-forward function: It takes three arguments, and adds them, returning the sum. Let’s load this up in `ghci` and see if it barfs.

``````Prelude> :l SuperSum.hs
[1 of 1] Compiling SuperSum             ( SuperSum.hs, interpreted )
Ok, modules loaded: SuperSum.
*SuperSum>``````

…so far so good, let’s put it through the paces!

``````*SuperSum> :t (+++)
(+++) :: Num a => a -> a -> a -> a``````

…this checks out, let’s call it as prefix…

``````*SuperSum> (+++) 1 2 3
6``````

…check! Let’s partially apply it with two arguments like a regular operator…

``````*SuperSum> :t 1 +++ 2
1 +++ 2 :: Num a => a -> a``````

…makes sense, this returns a function that takes a `Num` and returns a `Num`. Let’s quit beating around the bush and call it!

``````*SuperSum> 1 +++ 2 3

<interactive>:21:3:
No instance for (Num a0) arising from a use of `+++'
The type variable `a0' is ambiguous
Possible fix: add a type signature that fixes these type variable(s)
Note: there are several potential instances:
instance Num Double -- Defined in `GHC.Float'
instance Num Float -- Defined in `GHC.Float'
instance Integral a => Num (GHC.Real.Ratio a)
-- Defined in `GHC.Real'
...plus three others
In the expression: 1 +++ 2 3
In an equation for `it': it = 1 +++ 2 3

<interactive>:21:7:
No instance for (Num (a1 -> a0)) arising from the literal `2'
Possible fix: add an instance declaration for (Num (a1 -> a0))
In the expression: 2
In the second argument of `(+++)', namely `2 3'
In the expression: 1 +++ 2 3

<interactive>:21:9:
No instance for (Num a1) arising from the literal `3'
The type variable `a1' is ambiguous
Possible fix: add a type signature that fixes these type variable(s)
Note: there are several potential instances:
instance Num Double -- Defined in `GHC.Float'
instance Num Float -- Defined in `GHC.Float'
instance Integral a => Num (GHC.Real.Ratio a)
-- Defined in `GHC.Real'
...plus three others
In the first argument of `2', namely `3'
In the second argument of `(+++)', namely `2 3'
In the expression: 1 +++ 2 3``````

Yikes! It’s like we’re doing some Java! Well, that message is certainly unhelpful, let’s see what ghci thinks the type of this is:

``````*SuperSum> :t 1 +++ 2 3
1 +++ 2 3 :: (Num a, Num (a1 -> a), Num a1) => a -> a``````

Also unhelpful. As far as I can tell, the issue here is precedence. Basically, if we add some parenthesis or a dollar sign, this will work just fine:

``````*SuperSum> (1 +++ 2) 3
6
*SuperSum> :t (1 +++ 2) 3
(1 +++ 2) 3 :: Num a => a
*SuperSum> 1 +++ 2 \$ 3
6
*SuperSum> :t 1 +++ 2 \$ 3
1 +++ 2 \$ 3 :: Num a => a``````

When we are explicit about our precedence, the functions work as expected, and we get an “infix function with more than two arguments”. The moral of the story? You can do it, but you shouldn’t.

Now that we’ve solved this mystery by ourselves, let’s see if there’s any documentation on the issue.

Google turns up very little on the subject, however the first result seems promising. From the bottom of that page:

for a function taking more than two arguments, you can do it but it’s not nearly as nice

Now let us never speak of this again…

You may recall, earlier this year I wrote about object orientation in C. The basic Idea being that “Object Oriented Programming” is more a mindset, then a language feature. You can do object orientation and access control in C using free-floating functions and opaque structs. Well, guess what? You can do Object Oriented Programming in Haskell as well!

As a quick recap, if you didn’t read "C With Classes", for our purposes there are three components that need to be present to be considered “an object”: data consolidation, access control, and method calling. Inheritance is also important to real “Object Oriented Programming” (or OOP, as I’ll start calling it), but is really just gravy. Inheritance is largely supported by typeclasses in Haskell, so I won’t be going into it today.

Functional OOP

What would OOP look like in Haskell? Thanks to the magic of higher-order functions, we can actually very closely approximate what you’d see in a traditional OOP language, such as Java or C++.

Data

This part is trivial, there is literally a `data` keyword for this purpose. You should have this down by now.

Access Control

Access Control can be accomplished by way of the `module` keyword. Simply expose what you’d like to be public, and don’t expose your private members. Obviously, if you have private fields in your “Class”, you should make a factory function for your class instead of exposing its constructor. This is all pretty standard stuff.

Method Calls

This is an area that Haskell shines, and C shows its ugly side. In Haskell, we can actually create a method call operator, and create something that looks very much like the traditional `Class.method` calling convention that we’re used to!

The Method Call Operator

First, we need some contrived classes. Let’s go with everybody’s favorite: the `Employee`!

``````data Employee = Employee {name :: String,
employeeId :: Integer,
title :: String}``````

Nothing fancy or non-standard here. We created an `Employee` “Class” in the traditional Haskell way. Due to our use of record syntax, we already have three getters: `name`, `employeeId`, and `title`.

Let’s make another function, so that we can have a method that takes arguments:

``````isSeniorTo :: Employee
-> Employee
-> Bool
isSeniorTo s f = (employeeId s) > (employeeId f)``````

There is something extremely important to note about this function: the last argument is the object, not the first as it was in “C With Classes”. The reason for this is to allow us to partially apply this function, this will be crucial.

Now, let’s give it a shot to make sure everything is working:

``````*ghci> let boss = newEmployee "Chris" 1 "Author"

*ghci> let notBoss = newEmployee "Geoffrey" 2 "Associate"

*ghci> name boss
"Chris"

*ghci> isSeniorTo notBoss boss
True``````

All looks well, we create two Employee objects. Since `Chris`‘s employee ID is lower than `Geoffrey`‘s, the `isSeniorTo` method returns `True`. But this is all very wonky still, let’s create that method call operator already!

``````(>-) :: a
-> (a -> b)
-> b
(>-) o f = f o``````

Since `.` and `->` are already spoken for, I’ve gone with `>-` for my method call operator. The method call operator takes an arbitrary type `a`, and a function that takes the same type `a`, and returns a type `b`. Finally a type `b` is returned. The definition of this function couldn’t be simpler: we call the function on the passed-in object! Let’s see this in action:

``````*ghci> notBoss >- title
"Associate"

*ghci> boss >- isSeniorTo notBoss
True``````

This is just about as elegant as it gets; using the method call operator we just defined, we call a method on an object! In the case of `isSeniorTo`, we partially apply the function with all but the last argument, then the method call operator is able to use it just as any other function.

But something doesn’t sit right. Isn’t the definition of `isSeniorTo` a bit smelly? It calls methods on objects, shouldn’t it use the method call operator? Now that we have our method call operator, let’s fix that function:

``````isSeniorTo :: Employee
-> Employee
-> Bool
isSeniorTo s f = (s >- employeeId) > (f >- employeeId)``````

There, that’s better. `isSeniorTo` now properly calls methods on `s` and `f`, and all is again well in the world.

Here’s The Kicker

You may be experiencing some deja vu from all of this. It feels like we’ve done this sort of thing before. But where? You may recall this little operator:

``````*ghci> :t (>>=)
(>>=) :: Monad m => m a -> (a -> m b) -> m b``````

That’s right, the monadic bind operator looks suspiciously like our method call operator. But does it behave the same?

``````*ghci> 1 >- (+) 1
2

*ghci> Just 1 >>= (\a -> return \$ a + 1)
Just 2``````

Let’s ignore for a second that we had to use a monad for the bind operator, and see the fact that the two basically did the same thing. In fact, to further illustrate the point, let’s make a `Class` monad:

``````data Class a = Class a deriving (Show)

instance Monad Class where
(Class a) >>= f = f a
return = Class``````

Unlike most monads, which do important work, our `Class` monad does nothing but prove a point. However, you should note that the implementation of the bind operator is essentially the same as the implementation of the method call operator. Now, let’s see our monad in action!

``````let boss = Employee "Chris" 1 "Author"

*ghci> boss >- name
"Chris"

*ghci> Class boss >>= return . name
Class "Chris"``````

As you can see, they essentially do the same thing. It turns out that Haskell had classes all along!

Of course, this isn’t exactly true. I’d say that the `State` monad serves many of the same purposes as objects in OOP languages. However, the semantics of things like `Reader`, `Maybe`, and `IO` have little in common with objects. But much like we implemented Objects in Haskell, the various OOP languages are implementing monads into their standard libraries.

Indeed, OOP and functional programming are not supported by languages, they are supported by programmers. Some languages may make one or the other easier, but the differences are small, and get smaller as time passes.

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``

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      ||
------------------------------``````

List as a Monad

Much ink has been spilled on the subject of “Lists as Monads”. Just the fact that they are of course, not what it means for you. This doesn’t really seem surprising to me; there are better monads to use to describe how monads work. Additionally, lists have their own special functions for working with them; you don’t `fmap` a list, you just call `map`.

Presumably, Lists as Monads is something that seasoned Monadimancers understand. Maybe it’s some sort of rite of passage. But no more. Today I’ll shed light on the arcane mysteries of Lists as Monads.

Motivation

But first we need a problem to solve. For my example I’ll be using the cartesian product of two lists. The cartesian product of two sets (we’ll be using lists) is defined as:

``````A X B is the set of all ordered pairs (a, b) such that:

a is a member of set A and
b is a member of set B``````

…translated into Haskell we should get a function with the following signature:

``cartProd :: [a] -> [b] -> [(a, b)]``

How might this function look? Well, we’d need three functions. The first function should have the signature:

`` cartProd'' :: a -> b -> (a, b)``

This function is pretty straight forward, it pairs an `a` and a `b`. Next we’d need the function:

``cartProd' :: [b] -> a -> [(a, b)]``

This function maps `(cartProd'' a)` over `b`, producing the list `[(a, b)]`. Finally, we need a function to tie it all together:

``cartProd :: [a] -> [b] -> [(a, b)]``

This function maps `(cartProd' b)` over `a`, then `concat`s the resulting list of lists. An implementation might look like this:

``````cartProd :: [a] -> [b] -> [(a, b)]
cartProd l r = concat \$ map (cartProd'' r) l
where cartProd' :: [b] -> a -> [(a, b)]
cartProd' r l = map (cartProd''' l) r
where cartProd'' :: a -> b -> (a, b)
cartProd'' l r = (l, r)``````

Did you go cross-eyed? Not exactly the most concise function that’s ever been written. Surely there is a better way…

Binding Our Lists

You may remember a few weeks back I talked about using the Maybe Monad. The gist of that post being that if you’re inside a `do` block, you can treat your `Maybe` as if it were just a plain value. It turns out that we can do something similar with Lists.

The `Monad` instance for `[]` is somewhat complicated, but it’s operation is straight forward. If `>>=` takes a `Monad a`, a function that takes an `a` and returns a `Monad b`, and returns a `Monad b`, what happens if we bind a simple function to `[1]`?

``````Prelude> [1] >>= (\a -> return \$ a + 1)
[2]``````

…ok, so it added 1 to 1, and stuffed it into a list. Seems pretty straight forward. Let’s try something a little more complicated:

``````Prelude> [1, 2] >>= (\a -> return \$ a + 1)
[2,3]``````

…so this time it added 1 to each list node, as if we’d called `map ((+) 1) [1, 2]`. Let’s try something else:

``````Prelude> [1] >>= (\a -> [(a + 1), (a - 1)])
[2,0]``````

…this time we tried it in reverse. We bound `[1]` to a function that returns a list with two elements. The resulting list contained two elements. Again, nothing ground breaking here, but what if we do both?

``````Prelude> [1, 2] >>= (\a -> [(a + 1), (a - 1)])
[2,0,3,1]``````

…now we get a list with four elements: 1+1, 1-1, 2+1, and 2-1. To replicate this behavior we can’t just map the lambda over the original list. We need to add a call to concat. Let’s expand this our a bit further:

``````Prelude> [1, 2] >>= (\a -> [(a + 1), (a - 1)]) >>= (\b -> [b, b])
[2,2,0,0,3,3,1,1]``````

…all simple functions, but if we were to try to do this without the use of List’s monadic functions it’d become a mess like my `cartProd` function. Speaking of which…

The Better Way

Getting back to our original topic. Now that we have a feel for how List’s monadic interface works, how could we re-implement `cartProd` to not be terrible? Simple:

``````cartProd :: [a] -> [b] -> [(a, b)]
cartProd l r = do l' <- l
r' <- r
[(l', r')]``````

I’m often hesitant to toot my own horn and call something I wrote “elegant”, but it’s hard to argue that this function isn’t. In three short lines, I managed to re-implement that nested monstrosity I wrote before. There is one fairly massive gotcha here…

In the first and second lines, we bind our two lists to a label. It’s important to note that the order of these matters. The lists will be cycled through from the bottom up. Meaning that for each element of l, all elements of r will be evaluated. For example, using our `cartProd`:

``````Prelude> cartProd [1,2] [3,4]
[(1,3),(1,4),(2,3),(2,4)]``````

1 is paired with 3, then 1 is paired with 4, then 2 is paired with 3 and 2 is paired with 4. Were we to swap the order in which we bind l and r to look like this:

``````cartProd :: [a] -> [b] -> [(a, b)]
cartProd l r = do r' <- r
l' <- l
[(l', r')]``````

Then the output would look like this:

``````Prelude> cartProd [1,2] [3,4]
[(1,3),(2,3),(1,4),(2,4)]``````

1 is paired with 3, then 2 is paired with 3, then 1 is paired with 4, then 2 is paired with 4. Before the first element of the tuple was grouped together where here the second element is. For our purposes, both results are valid per the definition of cartesian product, but that may not hold for you so be careful.

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)

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

first <- Nothing

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.