Archive | Haskell Platform RSS for this section

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!

Might It Be Case Sensitive?

So today I thought I’d mess around with the new SDL2 Bindings for Haskell.

I set up a cabal project and added my build-depends:

build-depends: base >=4.8 && <4.9, sdl2 >= 2, openglraw

OK! Let’s do this!

$ cabal install Resolving dependencies... cabal: Could not resolve dependencies: trying: gl-tut-0.1.0.0 (user goal) next goal: openglraw (dependency of gl-tut-0.1.0.0) Dependency tree exhaustively searched. Note: when using a sandbox, all packages are required to have consistent dependencies. Try reinstalling/unregistering the offending packages or recreating the sandbox.

What is this nonsense? No possible build plan? I don’t believe it!

$ cabal install sdl2-2.0.0 openglraw Resolving dependencies... Notice: installing into a sandbox located at ...

OK, that works…

Many_Hours_Later

Maybe it’s magically case sensitive?

build-depends: base >=4.8 && <4.9, sdl2 >= 2.0, OpenGLRaw

…work this time you POS! I COMMAND YOU!

$ cabal install Resolving dependencies... Notice: installing into a sandbox located at ...

…and of course it works…

nbc_the_more_you_know

It turns out that cabal packages can be case sensitive. Sometimes.

Checking Our Heads With Liquid Haskell

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" *Main> headInTail ["cat"] ["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

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 Get your head checked.

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…

Object Oriented Haskell

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

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 Temperatures. 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 Conversions, 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 Doubles:

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

Next, we need to turn these Conversions into TableBuilders. 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 || ------------------------------

K&R Challenge 2: The Specter of Undefined Behavior

Continuing with the K&R Challenge, today we’ll be doing exercise 2:

Experiment to find out what happens when printf‘s argument string contains \c, where c is some character not listed above.

Basically, we’ll be trying to print “\c” to the screen, and seeing what C does.

In C

The code for this is very simple:

int main (int argc, char ** argv) { printf("Trying to print: \c\n"); return 0; }

Like last time, we’ll compile it using:

gcc -Wall ex2.c -o ex2

Right away, you should get a compiler warning:

ex2.c: In function ‘main’: ex2.c:10:11: warning: unknown escape sequence: '\c' [enabled by default] printf("Trying to print: \c\n");

Notice that it is a warning, not an error, and that the compilation still succeeded and produced an executable. My friends, you have just witnessed Undefined Behavior. Undefined behavior is one of the defining aspects of C. Technically, it’s a feature, not a bug, and it is both a blessing and a curse.

It’s a blessing in that it’s one of the things that enables C’s unmatched performance. It’s a curse in that the compiler is allowed by the spec to do whatever it wants when it encounters undefined behavior: it could do something really helpful, it could segfault, or it could delete your hard drive. It could even unleash lions in your house and there’s nothing the police or congress could do about it.

Moral of the story: don’t use undefined behavior unless you really know what you’re doing. Even then, I’d argue it’s a code smell.

So, what happens when you run the compiled executable? Always fearless in the pursuit of truth, I ran it. The following was printed to the console:

Trying to print: c

The GNU C Compiler decided to be nice and just strip the “\”, then print the message. It’s a good thing I have managed to avoid angering Richard Stallman, because gcc could very well have kidnapped my wife. That would have been a problem.

And In Haskell

Nothing about this exercise relies on the behavior of printf, therefore even though Haskell has it, I’ve elected not to use it. The implementation of this exercise in Haskell looks like this:

main :: IO () main = putStrLn "Trying to print: \c\n"

As before, this can be run using:

runhaskell ex2.hs

…but when you try it, the following error is displayed, and compilation fails:

ex2.hs:2:62: lexical error in string/character literal at character 'c'

Where C allowed the undefined escape sequence as undefined behavior, Haskell throws a compilation error. This is a Good Thing. Undefined behavior is a prolific source of bugs, and while I understand why it’s allowed, I can’t say that I agree that the tradeoff is worth it. Luckily for us, this isn’t a feature unique to Haskell. Most high level languages don’t have undefined behavior. Unfortunately, this is one of the reasons that most programming languages are orders of magnitude slower than C.

Regardless, undefined behavior is a fact of life for the C programmer. It’s one of the tradeoffs they make to use the language. These design decisions were made decades ago, and are unlikely to change. For this reason, this is a good exercise.

The families of those who were turned to stone by their compilers after doing this exercise are in our prayers…

%d bloggers like this: