<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml"
><head
><title
>Implementing Pointer Algorithms in Haskell — Exercises</title
><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"
/><meta name="generator" content="pandoc"
/><meta name="author" content="Péter Diviánszky"
/><meta name="date" content="CEFP, Budapest & Komárno, 25-30 May 2009"
/><style type="text/css"
>
table.sourceCode, tr.sourceCode, td.lineNumbers, td.sourceCode, table.sourceCode pre
{ margin: 0; padding: 0; border: 0; vertical-align: baseline; border: none; }
td.lineNumbers { border-right: 1px solid #AAAAAA; text-align: right; color: #AAAAAA; padding-right: 5px; padding-left: 5px; }
td.sourceCode { padding-left: 5px; }
pre.sourceCode { }
pre.sourceCode span.Normal { }
pre.sourceCode span.Keyword { color: #007020; font-weight: bold; }
pre.sourceCode span.DataType { color: #902000; }
pre.sourceCode span.DecVal { color: #40a070; }
pre.sourceCode span.BaseN { color: #40a070; }
pre.sourceCode span.Float { color: #40a070; }
pre.sourceCode span.Char { color: #4070a0; }
pre.sourceCode span.String { color: #4070a0; }
pre.sourceCode span.Comment { color: #60a0b0; font-style: italic; }
pre.sourceCode span.Others { color: #007020; }
pre.sourceCode span.Alert { color: red; font-weight: bold; }
pre.sourceCode span.Function { color: #06287e; }
pre.sourceCode span.RegionMarker { }
pre.sourceCode span.Error { color: red; font-weight: bold; }
</style
><!-- configuration parameters -->
<meta name="defaultView" content="slideshow" />
<meta name="controlVis" content="hidden" />
<style type="text/css" media="projection" id="slideProj">
/* Do not edit or override these styles! The system will likely break if you do. */
div#header, div#footer, div#controls, .slide {position: absolute;}
html>body div#header, html>body div#footer,
html>body div#controls, html>body .slide {position: fixed;}
.handout {display: none;}
.layout {display: block;}
.slide, .hideme, .incremental {visibility: hidden;}
#slide0 {visibility: visible;}
/* The following styles size, place, and layer the slide components.
Edit these if you want to change the overall slide layout.
The commented lines can be uncommented (and modified, if necessary)
to help you with the rearrangement process. */
/* target = 1024x768 */
/* img { float: right; padding-left: 10%; padding-bottom: 30px } */
div#header, div#footer, .slide {width: 100%; top: 0; left: 0;}
div#header {top: 0; height: 3em; z-index: 1;}
div#footer {top: auto; bottom: 0; height: 2.5em; z-index: 5;}
.slide {top: 0; width: 92%; padding: 3.5em 4% 4%; z-index: 2; list-style: none;}
div#controls {left: 50%; bottom: 0; width: 50%; z-index: 100;}
div#controls form {position: absolute; bottom: 0; right: 0; width: 100%;
margin: 0;}
#currentSlide {position: absolute; width: 10%; left: 45%; bottom: 1em; z-index: 10;}
html>body #currentSlide {position: fixed;}
/*
div#header {background: #FCC;}
div#footer {background: #CCF;}
div#controls {background: #BBD;}
div#currentSlide {background: #FFC;}
*/
/* Following are the presentation styles -- edit away! */
body {background: #FFF url(bodybg.gif) -16px 0 no-repeat; color: #000; font-size: 2em;}
:link, :visited {text-decoration: none; color: #00C;}
#controls :active {color: #88A !important;}
#controls :focus {outline: 1px dotted #227;}
h1, h2, h3, h4 {font-size: 100%; margin: 0; padding: 0; font-weight: inherit;}
ul, pre {margin: 0; line-height: 1em;}
html, body {margin: 0; padding: 0;}
blockquote, q {font-style: italic;}
blockquote {padding: 0 2em 0.5em; margin: 0 1.5em 0.5em; text-align: center; font-size: 1em;}
blockquote p {margin: 0;}
blockquote i {font-style: normal;}
blockquote b {display: block; margin-top: 0.5em; font-weight: normal; font-size: smaller; font-style: normal;}
blockquote b i {font-style: italic;}
kbd {font-weight: bold; font-size: 1em;}
sup {font-size: smaller; line-height: 1px;}
.slide code {padding: 2px 0.25em; font-weight: bold; color: #533;}
.slide code.bad, code del {color: red;}
.slide code.old {color: silver;}
.slide pre {padding: 0; margin: 0.25em 0 0.5em 0.5em; color: #533; font-size: 90%;}
.slide pre code {display: block;}
.slide ul {margin-left: 5%; margin-right: 7%; list-style: disc;}
.slide li {margin-top: 0.75em; margin-right: 0;}
.slide ul ul {line-height: 1;}
.slide ul ul li {margin: .2em; font-size: 85%; list-style: square;}
.slide img.leader {display: block; margin: 0 auto;}
div#header, div#footer {background: #EEE; color: #AAB;
font-family: Verdana, Helvetica, sans-serif;}
div#header {background: #EEE url(bodybg.gif) -16px 0 no-repeat;
line-height: 1px;}
div#footer {font-size: 0.5em; font-weight: bold; padding: 1em 0;}
#footer h1, #footer h2 {display: block; padding: 0 1em;}
#footer h2 {font-style: italic;}
div.long {font-size: 0.75em;}
.slide h1 {position: absolute; top: 0.7em; left: 0px; z-index: 1;
margin: 0; padding: 0.3em 0 0 50px; white-space: nowrap;
font: bold 150%/1em Helvetica, sans-serif;
color: #028; background: #EEE;}
.slide h3 {font-size: 130%;}
h1 abbr {font-variant: small-caps;}
div#controls {position: absolute; left: 50%; bottom: 0;
width: 50%;
text-align: right; font: bold 0.9em Verdana, Helvetica, sans-serif;}
html>body div#controls {position: fixed; padding: 0 0 1em 0;
top: auto;}
div#controls form {position: absolute; bottom: 0; right: 0; width: 100%;
margin: 0; padding: 0;}
#controls #navLinks a {padding: 0; margin: 0 0.5em;
background: #EEE; border: none; color: #779;
cursor: pointer;}
#controls #navList {height: 1em;}
#controls #navList #jumplist {position: absolute; bottom: 0; right: 0; background: #DDD; color: #227;}
#currentSlide {text-align: center; font-size: 0.5em; color: #449;}
#slide0 {padding-top: 3.5em; font-size: 90%;}
#slide0 h1 {position: static; margin: 1em 0 0; padding: 0;
font: bold 2em Helvetica, sans-serif; white-space: normal;
color: #000; background: transparent;}
#slide0 h2 {font: bold italic 1em Helvetica, sans-serif; margin: 0.25em;}
#slide0 h3 {margin-top: 1.5em; font-size: 1.5em;}
#slide0 h4 {margin-top: 0; font-size: 1em;}
ul.urls {list-style: none; display: inline; margin: 0;}
.urls li {display: inline; margin: 0;}
.note {display: none;}
.external {border-bottom: 1px dotted gray;}
html>body .external {border-bottom: none;}
.external:after {content: " \274F"; font-size: smaller; color: #77B;}
.incremental, .incremental *, .incremental *:after {color: #DDE; visibility: visible;}
img.incremental {visibility: hidden;}
.slide .current {color: #B02;}
/* diagnostics
li:after {content: " [" attr(class) "]"; color: #F88;}
*/
</style>
<style type="text/css" media="projection" id="operaFix">
/* DO NOT CHANGE THESE unless you really want to break Opera Show */
.slide {
visibility: visible !important;
position: static !important;
page-break-before: always;
}
#slide0 {page-break-before: avoid;}
</style>
<style type="text/css" media="screen" id="outlineStyle">
/* don't change this unless you want the layout stuff to show up in the outline view! */
.layout div, #footer *, #controlForm * {display: none;}
#footer, #controls, #controlForm, #navLinks, #toggle {
display: block; visibility: visible; margin: 0; padding: 0;}
#toggle {float: right; padding: 0.5em;}
html>body #toggle {position: fixed; top: 0; right: 0;}
/* making the outline look pretty-ish */
#slide0 h1, #slide0 h2, #slide0 h3, #slide0 h4 {border: none; margin: 0;}
#slide0 h1 {padding-top: 1.5em;}
.slide h1 {margin: 1.5em 0 0; padding-top: 0.25em;
border-top: 1px solid #888; border-bottom: 1px solid #AAA;}
#toggle {border: 1px solid; border-width: 0 0 1px 1px; background: #FFF;}
</style>
<style type="text/css" media="print" id="slidePrint">
/* The following rule is necessary to have all slides appear in print! DO NOT REMOVE IT! */
.slide, ul {page-break-inside: avoid; visibility: visible !important;}
h1 {page-break-after: avoid;}
body {font-size: 12pt; background: white;}
* {color: black;}
#slide0 h1 {font-size: 200%; border: none; margin: 0.5em 0 0.25em;}
#slide0 h3 {margin: 0; padding: 0;}
#slide0 h4 {margin: 0 0 0.5em; padding: 0;}
#slide0 {margin-bottom: 3em;}
h1 {border-top: 2pt solid gray; border-bottom: 1px dotted silver;}
.extra {background: transparent !important;}
div.extra, pre.extra, .example {font-size: 10pt; color: #333;}
ul.extra a {font-weight: bold;}
p.example {display: none;}
#header {display: none;}
#footer h1 {margin: 0; border-bottom: 1px solid; color: gray; font-style: italic;}
#footer h2, #controls {display: none;}
/* The following rule keeps the layout stuff out of print. Remove at your own risk! */
.layout, .layout * {display: none !important;}
</style>
<script type="text/javascript">
// S5 v1.1 slides.js -- released into the Public Domain
//
// Please see http://www.meyerweb.com/eric/tools/s5/credits.html for information
// about all the wonderful and talented contributors to this code!
var undef;var slideCSS='';var snum=0;var smax=1;var incpos=0;var number=undef;var s5mode=true;var defaultView='slideshow';var controlVis='visible';var isIE=navigator.appName=='Microsoft Internet Explorer'&&navigator.userAgent.indexOf('Opera')<1?1:0;var isOp=navigator.userAgent.indexOf('Opera')>-1?1:0;var isGe=navigator.userAgent.indexOf('Gecko')>-1&&navigator.userAgent.indexOf('Safari')<1?1:0;function hasClass(object,className){if(!object.className)return false;return(object.className.search('(^|\\s)'+className+'(\\s|$)')!=-1);}
function hasValue(object,value){if(!object)return false;return(object.search('(^|\\s)'+value+'(\\s|$)')!=-1);}
function removeClass(object,className){if(!object)return;object.className=object.className.replace(new RegExp('(^|\\s)'+className+'(\\s|$)'),RegExp.$1+RegExp.$2);}
function addClass(object,className){if(!object||hasClass(object,className))return;if(object.className){object.className+=' '+className;}else{object.className=className;}}
function GetElementsWithClassName(elementName,className){var allElements=document.getElementsByTagName(elementName);var elemColl=new Array();for(var i=0;i<allElements.length;i++){if(hasClass(allElements[i],className)){elemColl[elemColl.length]=allElements[i];}}
return elemColl;}
function isParentOrSelf(element,id){if(element==null||element.nodeName=='BODY')return false;else if(element.id==id)return true;else return isParentOrSelf(element.parentNode,id);}
function nodeValue(node){var result="";if(node.nodeType==1){var children=node.childNodes;for(var i=0;i<children.length;++i){result+=nodeValue(children[i]);}}
else if(node.nodeType==3){result=node.nodeValue;}
return(result);}
function slideLabel(){var slideColl=GetElementsWithClassName('*','slide');var list=document.getElementById('jumplist');smax=slideColl.length;for(var n=0;n<smax;n++){var obj=slideColl[n];var did='slide'+n.toString();obj.setAttribute('id',did);if(isOp)continue;var otext='';var menu=obj.firstChild;if(!menu)continue;while(menu&&menu.nodeType==3){menu=menu.nextSibling;}
if(!menu)continue;var menunodes=menu.childNodes;for(var o=0;o<menunodes.length;o++){otext+=nodeValue(menunodes[o]);}
list.options[list.length]=new Option(n+' : '+otext,n);}}
function currentSlide(){var cs;if(document.getElementById){cs=document.getElementById('currentSlide');}else{cs=document.currentSlide;}
cs.innerHTML='<span id="csHere">'+snum+'<\/span> '+'<span id="csSep">\/<\/span> '+'<span id="csTotal">'+(smax-1)+'<\/span>';if(snum==0){cs.style.visibility='hidden';}else{cs.style.visibility='visible';}}
function go(step){if(document.getElementById('slideProj').disabled||step==0)return;var jl=document.getElementById('jumplist');var cid='slide'+snum;var ce=document.getElementById(cid);if(incrementals[snum].length>0){for(var i=0;i<incrementals[snum].length;i++){removeClass(incrementals[snum][i],'current');removeClass(incrementals[snum][i],'incremental');}}
if(step!='j'){snum+=step;lmax=smax-1;if(snum>lmax)snum=lmax;if(snum<0)snum=0;}else
snum=parseInt(jl.value);var nid='slide'+snum;var ne=document.getElementById(nid);if(!ne){ne=document.getElementById('slide0');snum=0;}
if(step<0){incpos=incrementals[snum].length}else{incpos=0;}
if(incrementals[snum].length>0&&incpos==0){for(var i=0;i<incrementals[snum].length;i++){if(hasClass(incrementals[snum][i],'current'))
incpos=i+1;else
addClass(incrementals[snum][i],'incremental');}}
if(incrementals[snum].length>0&&incpos>0)
addClass(incrementals[snum][incpos-1],'current');ce.style.visibility='hidden';ne.style.visibility='visible';jl.selectedIndex=snum;currentSlide();number=0;}
function goTo(target){if(target>=smax||target==snum)return;go(target-snum);}
function subgo(step){if(step>0){removeClass(incrementals[snum][incpos-1],'current');removeClass(incrementals[snum][incpos],'incremental');addClass(incrementals[snum][incpos],'current');incpos++;}else{incpos--;removeClass(incrementals[snum][incpos],'current');addClass(incrementals[snum][incpos],'incremental');addClass(incrementals[snum][incpos-1],'current');}}
function toggle(){var slideColl=GetElementsWithClassName('*','slide');var slides=document.getElementById('slideProj');var outline=document.getElementById('outlineStyle');if(!slides.disabled){slides.disabled=true;outline.disabled=false;s5mode=false;fontSize('1em');for(var n=0;n<smax;n++){var slide=slideColl[n];slide.style.visibility='visible';}}else{slides.disabled=false;outline.disabled=true;s5mode=true;fontScale();for(var n=0;n<smax;n++){var slide=slideColl[n];slide.style.visibility='hidden';}
slideColl[snum].style.visibility='visible';}}
function showHide(action){var obj=GetElementsWithClassName('*','hideme')[0];switch(action){case's':obj.style.visibility='visible';break;case'h':obj.style.visibility='hidden';break;case'k':if(obj.style.visibility!='visible'){obj.style.visibility='visible';}else{obj.style.visibility='hidden';}
break;}}
function keys(key){if(!key){key=event;key.which=key.keyCode;}
if(key.which==84){toggle();return;}
if(s5mode){switch(key.which){case 10:case 13:if(window.event&&isParentOrSelf(window.event.srcElement,'controls'))return;if(key.target&&isParentOrSelf(key.target,'controls'))return;if(number!=undef){goTo(number);break;}
case 32:case 34:case 39:case 40:if(number!=undef){go(number);}else if(!incrementals[snum]||incpos>=incrementals[snum].length){go(1);}else{subgo(1);}
break;case 33:case 37:case 38:if(number!=undef){go(-1*number);}else if(!incrementals[snum]||incpos<=0){go(-1);}else{subgo(-1);}
break;case 36:goTo(0);break;case 35:goTo(smax-1);break;case 67:showHide('k');break;}
if(key.which<48||key.which>57){number=undef;}else{if(window.event&&isParentOrSelf(window.event.srcElement,'controls'))return;if(key.target&&isParentOrSelf(key.target,'controls'))return;number=(((number!=undef)?number:0)*10)+(key.which-48);}}
return false;}
function clicker(e){number=undef;var target;if(window.event){target=window.event.srcElement;e=window.event;}else target=e.target;if(target.getAttribute('href')!=null||hasValue(target.rel,'external')||isParentOrSelf(target,'controls')||isParentOrSelf(target,'embed')||isParentOrSelf(target,'object'))return true;if(!e.which||e.which==1){if(!incrementals[snum]||incpos>=incrementals[snum].length){go(1);}else{subgo(1);}}}
function findSlide(hash){var target=null;var slides=GetElementsWithClassName('*','slide');for(var i=0;i<slides.length;i++){var targetSlide=slides[i];if((targetSlide.name&&targetSlide.name==hash)||(targetSlide.id&&targetSlide.id==hash)){target=targetSlide;break;}}
while(target!=null&&target.nodeName!='BODY'){if(hasClass(target,'slide')){return parseInt(target.id.slice(5));}
target=target.parentNode;}
return null;}
function slideJump(){if(window.location.hash==null)return;var sregex=/^#slide(\d+)$/;var matches=sregex.exec(window.location.hash);var dest=null;if(matches!=null){dest=parseInt(matches[1]);}else{dest=findSlide(window.location.hash.slice(1));}
if(dest!=null)
go(dest-snum);}
function fixLinks(){var thisUri=window.location.href;thisUri=thisUri.slice(0,thisUri.length-window.location.hash.length);var aelements=document.getElementsByTagName('A');for(var i=0;i<aelements.length;i++){var a=aelements[i].href;var slideID=a.match('\#slide[0-9]{1,2}');if((slideID)&&(slideID[0].slice(0,1)=='#')){var dest=findSlide(slideID[0].slice(1));if(dest!=null){if(aelements[i].addEventListener){aelements[i].addEventListener("click",new Function("e","if (document.getElementById('slideProj').disabled) return;"+"go("+dest+" - snum); "+"if (e.preventDefault) e.preventDefault();"),true);}else if(aelements[i].attachEvent){aelements[i].attachEvent("onclick",new Function("","if (document.getElementById('slideProj').disabled) return;"+"go("+dest+" - snum); "+"event.returnValue = false;"));}}}}}
function externalLinks(){if(!document.getElementsByTagName)return;var anchors=document.getElementsByTagName('a');for(var i=0;i<anchors.length;i++){var anchor=anchors[i];if(anchor.getAttribute('href')&&hasValue(anchor.rel,'external')){anchor.target='_blank';addClass(anchor,'external');}}}
function createControls(){var controlsDiv=document.getElementById("controls");if(!controlsDiv)return;var hider=' onmouseover="showHide(\'s\');" onmouseout="showHide(\'h\');"';var hideDiv,hideList='';if(controlVis=='hidden'){hideDiv=hider;}else{hideList=hider;}
controlsDiv.innerHTML='<form action="#" id="controlForm"'+hideDiv+'>'+'<div id="navLinks">'+'<a accesskey="t" id="toggle" href="javascript:toggle();">Ø<\/a>'+'<a accesskey="z" id="prev" href="javascript:go(-1);">«<\/a>'+'<a accesskey="x" id="next" href="javascript:go(1);">»<\/a>'+'<div id="navList"'+hideList+'><select id="jumplist" onchange="go(\'j\');"><\/select><\/div>'+'<\/div><\/form>';if(controlVis=='hidden'){var hidden=document.getElementById('navLinks');}else{var hidden=document.getElementById('jumplist');}
addClass(hidden,'hideme');}
function fontScale(){if(!s5mode)return false;var vScale=22;var hScale=32;if(window.innerHeight){var vSize=window.innerHeight;var hSize=window.innerWidth;}else if(document.documentElement.clientHeight){var vSize=document.documentElement.clientHeight;var hSize=document.documentElement.clientWidth;}else if(document.body.clientHeight){var vSize=document.body.clientHeight;var hSize=document.body.clientWidth;}else{var vSize=700;var hSize=1024;}
var newSize=Math.min(Math.round(vSize/vScale),Math.round(hSize/hScale));fontSize(newSize+'px');if(isGe){var obj=document.getElementsByTagName('body')[0];obj.style.display='none';obj.style.display='block';}}
function fontSize(value){if(!(s5ss=document.getElementById('s5ss'))){if(!isIE){document.getElementsByTagName('head')[0].appendChild(s5ss=document.createElement('style'));s5ss.setAttribute('media','screen, projection');s5ss.setAttribute('id','s5ss');}else{document.createStyleSheet();document.s5ss=document.styleSheets[document.styleSheets.length-1];}}
if(!isIE){while(s5ss.lastChild)s5ss.removeChild(s5ss.lastChild);s5ss.appendChild(document.createTextNode('body {font-size: '+value+' !important;}'));}else{document.s5ss.addRule('body','font-size: '+value+' !important;');}}
function notOperaFix(){slideCSS=document.getElementById('slideProj').href;var slides=document.getElementById('slideProj');var outline=document.getElementById('outlineStyle');slides.setAttribute('media','screen');outline.disabled=true;if(isGe){slides.setAttribute('href','null');slides.setAttribute('href',slideCSS);}
if(isIE&&document.styleSheets&&document.styleSheets[0]){document.styleSheets[0].addRule('img','behavior: url(ui/default/iepngfix.htc)');document.styleSheets[0].addRule('div','behavior: url(ui/default/iepngfix.htc)');document.styleSheets[0].addRule('.slide','behavior: url(ui/default/iepngfix.htc)');}}
function getIncrementals(obj){var incrementals=new Array();if(!obj)
return incrementals;var children=obj.childNodes;for(var i=0;i<children.length;i++){var child=children[i];if(hasClass(child,'incremental')){if(child.nodeName=='OL'||child.nodeName=='UL'){removeClass(child,'incremental');for(var j=0;j<child.childNodes.length;j++){if(child.childNodes[j].nodeType==1){addClass(child.childNodes[j],'incremental');}}}else{incrementals[incrementals.length]=child;removeClass(child,'incremental');}}
if(hasClass(child,'show-first')){if(child.nodeName=='OL'||child.nodeName=='UL'){removeClass(child,'show-first');if(child.childNodes[isGe].nodeType==1){removeClass(child.childNodes[isGe],'incremental');}}else{incrementals[incrementals.length]=child;}}
incrementals=incrementals.concat(getIncrementals(child));}
return incrementals;}
function createIncrementals(){var incrementals=new Array();for(var i=0;i<smax;i++){incrementals[i]=getIncrementals(document.getElementById('slide'+i));}
return incrementals;}
function defaultCheck(){var allMetas=document.getElementsByTagName('meta');for(var i=0;i<allMetas.length;i++){if(allMetas[i].name=='defaultView'){defaultView=allMetas[i].content;}
if(allMetas[i].name=='controlVis'){controlVis=allMetas[i].content;}}}
function trap(e){if(!e){e=event;e.which=e.keyCode;}
try{modifierKey=e.ctrlKey||e.altKey||e.metaKey;}
catch(e){modifierKey=false;}
return modifierKey||e.which==0;}
function startup(){defaultCheck();if(!isOp)
createControls();slideLabel();fixLinks();externalLinks();fontScale();if(!isOp){notOperaFix();incrementals=createIncrementals();slideJump();if(defaultView=='outline'){toggle();}
document.onkeyup=keys;document.onkeypress=trap;document.onclick=clicker;}}
window.onload=startup;window.onresize=function(){setTimeout('fontScale()',50);}
</script>
</head
><body
><div class="layout">
<div id="controls"></div>
<div id="currentSlide"></div>
<div id="header"></div>
<div id="footer">
<h1 id="cefp-budapest-&-komárno-25-30-may-2009"
>CEFP, Budapest & Komárno, 25-30 May 2009</h1
><h2 id="implementing-pointer-algorithms-in-haskell---exercises"
>Implementing Pointer Algorithms in Haskell — Exercises</h2
></div>
</div>
<div class="presentation">
<div class="slide">
<h1 id="implementing-pointer-algorithms-in-haskell---exercises-1"
>Implementing Pointer Algorithms in Haskell — Exercises</h1
><h3 id="péter-diviánszky"
>Péter Diviánszky</h3
><h4 id="cefp-budapest-&-komárno-25-30-may-2009-1"
>CEFP, Budapest & Komárno, 25-30 May 2009</h4
></div>
<div class="slide">
<h1 id="legend"
>Legend</h1
><p
>E2: exercise<br
/>*E3: exercise, hard to solve<br
/>-E6: exercise, easy to solve</p
></div>
<div class="slide">
<h1 id="programming-environment"
>Programming Environment</h1
><p
>Newer <code
>GHC</code
> and <code
>cabal-install</code
> are needed (these are on computers in the lab; Linux is recommended).</p
><ol style="list-style-type: decimal;"
><li
>Run the following commands in a terminal:</li
></ol
><pre class="sourceCode bash"
><code
><span class="Normal NormalText"
>cabal update</span
><br
/><span class="Normal NormalText"
>cabal </span
><span class="Keyword Command"
>install</span
><span class="Normal NormalText"
> linear</span
><span class="Normal Option"
>-maps</span
><span class="Normal NormalText"
> </span
><span class="Normal Option"
>-fcheck</span
><br
/><span class="Normal NormalText"
>firefox </span
><span class="Keyword Backquote"
>`</span
><span class="Normal NormalText"
>linear</span
><span class="Normal Option"
>-maps-exercises</span
><span class="Keyword Backquote"
>`</span
><span class="Normal NormalText"
> </span
><span class="Keyword Control"
>&</span
><br
/></code
></pre
><ol start="2" style="list-style-type: decimal;"
><li
>Open an editor and save an empty file <code
>Maps.hs</code
> (do not quit).</li
><li
>Run the command “<code
>ghci Maps.hs</code
>” in a terminal — this is an interpreter.</li
></ol
></div>
<div class="slide">
<h1 id="first-steps"
>First Steps</h1
><ul
><li
>Enter <code
>3*23</code
> in the interpreter. The result should be <code
>69</code
>.</li
><li
>Write <code
>x = 3*3</code
> in the editor and save the file. Enter <code
>:r</code
> (reload) and enter <code
>x</code
> in the interpreter. The result should be <code
>9</code
>.</li
><li
>You can navigate between previous commands with up and down arrows.</li
><li
><p
><code
>:t x</code
> shows the type of <code
>x</code
>.</p
></li
><li
><p
>Get acquainted with Haskell (look at <a href="http://haskell.org"
>haskell.org</a
> if necessary).</p
></li
></ul
></div>
<div class="slide">
<h1 id="e1-depth-first-walk"
>E1: Depth-First Walk</h1
><p
>If we start from A then we get A, B, D, E, C, F, G, H.</p
><p
><img src="graph.png" alt="graph"
/></p
></div>
<div class="slide">
<h1 id="instructions"
>Instructions</h1
><p
>Define a function with the following type signature:</p
><pre class="sourceCode haskell"
><code
><span class="Keyword"
>import</span
><span class="Normal NormalText"
> </span
><span class="Normal ModuleName"
>Data.IdMap</span
><span class="Normal NormalText"
> </span
><span class="Comment"
>-- at the beginning of the file</span
><br
/><span class="Keyword"
>import</span
><span class="Normal NormalText"
> </span
><span class="Normal ModuleName"
>Data.Graph.IdMap.Tests</span
><br
/><br
/><span class="Keyword"
>type</span
><span class="Normal NormalText"
> ChildrenFun k = Id k -> [Id k]</span
><br
/><br
/><span class="Function FunctionDefinition"
>depthFirstWalk ::</span
><span class="Normal NormalText"
> </span
><br
/><span class="Normal NormalText"
> I i => </span
><span class="Comment"
>-- type level integer </span
><br
/><span class="Normal NormalText"
> ChildrenFun k -> </span
><span class="Comment"
>-- children function</span
><br
/><span class="Normal NormalText"
> Set i k -> </span
><span class="Comment"
>-- set of already visited nodes </span
><br
/><span class="Normal NormalText"
> [Id k] -> </span
><span class="Comment"
>-- nodes to be visited</span
><br
/><span class="Normal NormalText"
> [Id k] </span
><span class="Comment"
>-- visited nodes</span
><br
/></code
></pre
></div>
<div class="slide">
<h1 id="instructions-continued"
>Instructions (continued)</h1
><p
>Use the following primitives:</p
><pre class="sourceCode haskell"
><code
><span class="Function FunctionDefinition"
>member ::</span
><span class="Normal NormalText"
> I i => Id k -> Set i k -> </span
><span class="DataType TypeConstructor"
>Bool</span
><br
/><span class="Function FunctionDefinition"
>setInsert ::</span
><span class="Normal NormalText"
> I i => Id k -> Set i k -> Set i k</span
><br
/></code
></pre
><p
>Test your function in the interpreter:</p
><pre class="sourceCode haskell"
><code
><span class="Normal NormalText"
>*Main> testWalk depthFirstWalk </span
><span class="String"
>"A"</span
><br
/><span class="String"
>"ABDECFGH"</span
><br
/></code
></pre
></div>
<div class="slide">
<h1 id="help"
>Help</h1
><p
>Make pattern matching on the identifier list. If it is not empty, test whether the first identifier is in the set. If it is not in the set, return it and make a recursive call with a modified set and an extended task list (the children of the first identifier has to be visited).</p
><p
>You will probably need the functions <code
>(++)</code
> and <code
>(:)</code
>.</p
></div>
<div class="slide">
<h1 id="e2-postorder-walk"
>E2: Postorder Walk</h1
><p
>If we start from A then we get D, E, B, F, H, G, C, A.</p
><p
><img src="graph.png" alt="graph"
/></p
></div>
<div class="slide">
<h1 id="instructions-1"
>Instructions</h1
><p
>Define a postorder walk:</p
><pre class="sourceCode haskell"
><code
><span class="Function FunctionDefinition"
>postOrderWalk ::</span
><span class="Normal NormalText"
> I i => ChildrenFun k -> Set i k -> [Id k] -> [Id k]</span
><br
/></code
></pre
><p
>Use the following data structure inside in a “task list”:</p
><pre class="sourceCode haskell"
><code
><span class="Keyword"
>data</span
><span class="Normal NormalText"
> Task a = Return a | Visit a</span
><br
/></code
></pre
><p
>Use the same primitives as in <code
>depthFirstWalk</code
>. Test your function in the interpreter:</p
><pre class="sourceCode haskell"
><code
><span class="Normal NormalText"
>*Main> testWalk postOrderWalk </span
><span class="String"
>"A"</span
><br
/><span class="String"
>"DEBFHGCA"</span
><br
/></code
></pre
></div>
<div class="slide">
<h1 id="help-1"
>Help</h1
><p
>Define a local function which receives a set of already visited nodes and a list of tasks and returns the reachable nodes. Call the local function with the set and with <code
>Visit</code
> tasks.</p
><p
>The local function is a recursive function.<br
/>Make pattern matching on the identifier list. If it is not empty, and the first identifier is a <code
>Return</code
> task then return it and make a recursive call.<br
/>If the first identifier is a <code
>Visit</code
> task then test whether it is in the set.<br
/>If it is not in the set, make a recursive call with a modified set and an extended task list.<br
/>The extended task list should contain the children of the first identifier (as <code
>Visit</code
> tasks) and the first identifier as <code
>Return</code
> task, and the old tasks.</p
></div>
<div class="slide">
<h1 id="e2-postorder-walk-variant"
>E2’: Postorder Walk Variant</h1
><p
>Define the function:</p
><pre class="sourceCode haskell"
><code
><span class="Function FunctionDefinition"
>revPostOrderWalk ::</span
><br
/><span class="Normal NormalText"
> I i => </span
><br
/><span class="Normal NormalText"
> Children k -> </span
><br
/><span class="Normal NormalText"
> Set i k -> </span
><br
/><span class="Normal NormalText"
> [Id k] -> </span
><br
/><span class="Normal NormalText"
> ( Set i k </span
><span class="Comment"
>-- set of visited nodes</span
><br
/><span class="Normal NormalText"
> , [Id k]) </span
><span class="Comment"
>-- visited nodes in reversed postorder</span
><br
/></code
></pre
><p
>Help: Use accumulation (define a local function with an additional list parameter which accumulates the values).</p
></div>
<div class="slide">
<h1 id="e3-mapped-walk"
>*E3: Mapped Walk</h1
><p
>If we start from B, G, A then we get E, D, B; H, G; F, C, A.</p
><p
><img src="graph.png" alt="graph"
/></p
></div>
<div class="slide">
<h1 id="instructions-2"
>Instructions</h1
><p
>Define the function:</p
><pre class="sourceCode haskell"
><code
><span class="Function FunctionDefinition"
>mapWalk ::</span
><span class="Normal NormalText"
> I i => ChildrenFun k -> Set i k -> [Id k] -> [[Id k]]</span
><br
/></code
></pre
><p
><code
>mapWalk</code
> takes a list of nodes. It returns a list of lists with the same length. The first list contains the nodes reachable from the first node. The second contains the nodes reachable from the second node not touching nodes in the first list. …</p
><pre class="sourceCode haskell"
><code
><span class="Normal NormalText"
>*Main> testMapWalk mapWalk </span
><span class="String"
>"BGA"</span
><br
/><span class="Normal NormalText"
>[</span
><span class="String"
>"EDB"</span
><span class="Normal NormalText"
>,</span
><span class="String"
>"HG"</span
><span class="Normal NormalText"
>,</span
><span class="String"
>"FCA"</span
><span class="Normal NormalText"
>]</span
><br
/></code
></pre
></div>
<div class="slide">
<h1 id="e3-mapped-walk-variant"
>E3’: Mapped Walk Variant</h1
><p
>Define a function similar to <code
>mapWalk</code
> but</p
><ul
><li
>The result is reversed.</li
><li
>Collect the nodes which are present in the set.</li
></ul
><pre class="sourceCode haskell"
><code
><span class="Function FunctionDefinition"
>revMapWalk ::</span
><span class="Normal NormalText"
> I i => </span
><br
/><span class="Normal NormalText"
> ChildrenFun k -> Set i k -> [Id k] -> [[Id k]]</span
><br
/></code
></pre
><p
>Help: Use accumulation.</p
></div>
<div class="slide">
<h1 id="e4-strongly-connected-components"
>*E4: Strongly Connected Components</h1
><p
>If we start from A then we get D; E; B; I, H, G; C, F, A.<br
/>(If these are modules then this is the compilation order.)</p
><p
><img src="graph.png" alt="graph"
/></p
></div>
<div class="slide">
<h1 id="instructions-3"
>Instructions</h1
><p
>Define the function:</p
><pre class="sourceCode haskell"
><code
><span class="Function FunctionDefinition"
>scc ::</span
><span class="Normal NormalText"
> I i => </span
><br
/><span class="Normal NormalText"
> ChildrenFun k -> </span
><span class="Comment"
>-- children</span
><br
/><span class="Normal NormalText"
> ChildrenFun k -> </span
><span class="Comment"
>-- parents</span
><br
/><span class="Normal NormalText"
> Set i k -> </span
><span class="Comment"
>-- an empty set</span
><br
/><span class="Normal NormalText"
> [Id k] -> </span
><span class="Comment"
>-- initial nodes</span
><br
/><span class="Normal NormalText"
> ( Set i k </span
><span class="Comment"
>-- an empty set</span
><br
/><span class="Normal NormalText"
> , [[Id k]]) </span
><span class="Comment"
>-- the scc of the reachable nodes</span
><br
/></code
></pre
><p
>Test case:</p
><pre class="sourceCode haskell"
><code
><span class="Normal NormalText"
>*Main> testSCC scc </span
><span class="String"
>"A"</span
><br
/><span class="Normal NormalText"
>[</span
><span class="String"
>"D"</span
><span class="Normal NormalText"
>,</span
><span class="String"
>"E"</span
><span class="Normal NormalText"
>,</span
><span class="String"
>"B"</span
><span class="Normal NormalText"
>,</span
><span class="String"
>"HG"</span
><span class="Normal NormalText"
>,</span
><span class="String"
>"CFA"</span
><span class="Normal NormalText"
>]</span
><br
/></code
></pre
></div>
<div class="slide">
<h1 id="e5-replaceLast"
>-E5: <code
>replaceLast</code
></h1
><p
>Define a function which replaces the last element of a list.</p
><pre class="sourceCode haskell"
><code
><span class="Function FunctionDefinition"
>replaceLast ::</span
><span class="Normal NormalText"
> [a] -> a -> [a]</span
><br
/></code
></pre
><p
>Test cases:</p
><pre class="sourceCode haskell"
><code
><span class="Normal NormalText"
>replaceLast [</span
><span class="DecVal Decimal"
>1</span
><span class="Normal NormalText"
>,</span
><span class="DecVal Decimal"
>4</span
><span class="Normal NormalText"
>,</span
><span class="DecVal Decimal"
>6</span
><span class="Normal NormalText"
>] </span
><span class="DecVal Decimal"
>7</span
><span class="Normal NormalText"
> == [</span
><span class="DecVal Decimal"
>1</span
><span class="Normal NormalText"
>,</span
><span class="DecVal Decimal"
>4</span
><span class="Normal NormalText"
>,</span
><span class="DecVal Decimal"
>7</span
><span class="Normal NormalText"
>]</span
><br
/><span class="Normal NormalText"
>replaceLast </span
><span class="String"
>"take"</span
><span class="Normal NormalText"
> </span
><span class="Char"
>'x'</span
><span class="Normal NormalText"
> == </span
><span class="String"
>"takx"</span
><br
/></code
></pre
></div>
<div class="slide">
<h1 id="e6-replaceAndShiftOne"
>-E6: <code
>replaceAndShiftOne</code
></h1
><p
>Define a function which replaces a list’s nth element and shift the old element one position to the right.</p
><pre class="sourceCode haskell"
><code
><span class="Function FunctionDefinition"
>replaceAndShiftOne ::</span
><span class="Normal NormalText"
> </span
><span class="DataType TypeConstructor"
>Int</span
><span class="Normal NormalText"
> -> [a] -> a -> [a]</span
><br
/></code
></pre
><p
>Test cases:</p
><pre class="sourceCode haskell"
><code
><span class="Normal NormalText"
>replaceAndShiftOne </span
><span class="DecVal Decimal"
>0</span
><span class="Normal NormalText"
> </span
><span class="String"
>"abcd"</span
><span class="Normal NormalText"
> </span
><span class="Char"
>'e'</span
><span class="Normal NormalText"
> == </span
><span class="String"
>"eacd"</span
><br
/><span class="Normal NormalText"
>replaceAndShiftOne </span
><span class="DecVal Decimal"
>1</span
><span class="Normal NormalText"
> </span
><span class="String"
>"abcd"</span
><span class="Normal NormalText"
> </span
><span class="Char"
>'e'</span
><span class="Normal NormalText"
> == </span
><span class="String"
>"aebd"</span
><br
/><span class="Normal NormalText"
>replaceAndShiftOne </span
><span class="DecVal Decimal"
>2</span
><span class="Normal NormalText"
> </span
><span class="String"
>"abcd"</span
><span class="Normal NormalText"
> </span
><span class="Char"
>'e'</span
><span class="Normal NormalText"
> == </span
><span class="String"
>"abec"</span
><br
/></code
></pre
></div>
<div class="slide">
<h1 id="e7-pointer-reversal-walk"
>*E7: Pointer Reversal Walk</h1
><p
>Define the pointer reversal algorithm.</p
><pre class="sourceCode haskell"
><code
><span class="Function FunctionDefinition"
>prWalk ::</span
><span class="Normal NormalText"
> </span
><br
/><span class="Normal NormalText"
> (I i, I i') =></span
><br
/><span class="Normal NormalText"
> Map i k [Id k] -> </span
><span class="Comment"
>-- a graph</span
><br
/><span class="Normal NormalText"
> Map i' k </span
><span class="DataType TypeConstructor"
>Int</span
><span class="Normal NormalText"
> -> </span
><span class="Comment"
>-- an empty map</span
><br
/><span class="Normal NormalText"
> Id k -> </span
><span class="Comment"
>-- start node</span
><br
/><span class="Normal NormalText"
> [Id k] </span
><span class="Comment"
>-- reachable nodes in depth first order</span
><br
/></code
></pre
><p
><em
>next slide</em
></p
></div>
<div class="slide">
<h1 id="e7-pointer-reversal-walk-continued"
>*E7: Pointer Reversal Walk (continued)</h1
><p
>Use the helper functions:</p
><pre class="sourceCode haskell"
><code
><span class="Normal NormalText"
>follow, </span
><span class="Function FunctionDefinition"
>back ::</span
><span class="Normal NormalText"
> </span
><br
/><span class="Normal NormalText"
> (I i, I i') =></span
><br
/><span class="Normal NormalText"
> Map i k [Id k] -> </span
><span class="Comment"
>-- modified graph</span
><br
/><span class="Normal NormalText"
> Map i' k </span
><span class="DataType TypeConstructor"
>Int</span
><span class="Normal NormalText"
> -> </span
><span class="Comment"
>-- index map</span
><br
/><span class="Normal NormalText"
> Id k -> </span
><span class="Comment"
>-- previous node</span
><br
/><span class="Normal NormalText"
> Id k -> </span
><span class="Comment"
>-- this node</span
><br
/><span class="Normal NormalText"
> [Id k] </span
><span class="Comment"
>-- reachable nodes in depth first order</span
><br
/></code
></pre
><p
><code
>follow</code
> follows an edge, <code
>back</code
> goes back on an edge.<br
/>The index map contains already visited nodes. The index show how many children of the node was completely visited.<br
/>The graph is transformed in each step a little but at the end it will have its original shape.</p
></div>
<div class="slide">
<h1 id="e7-pointer-reversal-walk-continued-1"
>*E7: Pointer Reversal Walk (continued)</h1
><p
>Use the following library functions:</p
><pre class="sourceCode haskell"
><code
><span class="Function FunctionDefinition"
>lookUp ::</span
><span class="Normal NormalText"
> I i => Id k -> Map i k a -> </span
><span class="DataType TypeConstructor"
>Maybe</span
><span class="Normal NormalText"
> a</span
><br
/><br
/><span class="Function FunctionDefinition"
>insert ::</span
><span class="Normal NormalText"
> I i => Id k -> a -> Map i k a -> Map i k a</span
><br
/><br
/><span class="Normal NormalText"
>(!) :: I i => Map i k a -> Id k -> a</span
><br
/></code
></pre
><p
>Test Cases:</p
><pre class="sourceCode haskell"
><code
><span class="Normal NormalText"
>*Main> testPrWalk prWalk </span
><span class="String"
>"A"</span
><br
/><span class="String"
>"ABDECFGH"</span
><br
/></code
></pre
></div>
<div class="slide">
<h1 id="e8-linear-time-type-inference"
>*E8: Linear Time Type Inference</h1
><p
>Begin a new file with the rows:</p
><pre class="sourceCode haskell"
><code
><span class="Keyword"
>import</span
><span class="Normal NormalText"
> </span
><span class="Normal ModuleName"
>Data.LinkMap</span
><br
/><br
/><span class="Keyword"
>type</span
><span class="Normal NormalText"
> Link i k = LinkMap i k ()</span
><br
/></code
></pre
><p
><code
>Link</code
> is a disjoint set data structure.<br
/>We will use the following primitives:</p
><pre class="sourceCode haskell"
><code
><span class="Function FunctionDefinition"
>link ::</span
><span class="Normal NormalText"
> I i => Id k -> Id k -> Link i k -> Link i k</span
><br
/><span class="Normal NormalText"
> </span
><span class="Comment"
>-- make a link from the first id to the second id</span
><br
/><span class="Function FunctionDefinition"
>follow ::</span
><span class="Normal NormalText"
> I i => Link i k -> Id k -> Id k</span
><br
/><span class="Normal NormalText"
> </span
><span class="Comment"
>-- follow the links until no link is found</span
><br
/><span class="Function FunctionDefinition"
>same ::</span
><span class="Normal NormalText"
> I i => Link i k -> Id k -> Id k -> </span
><span class="DataType TypeConstructor"
>Bool</span
><br
/><span class="Normal NormalText"
> </span
><span class="Comment"
>-- True if follow id1 == follow id2</span
><br
/></code
></pre
></div>
<div class="slide">
<h1 id="e8--types"
>*E8 / Types</h1
><pre class="sourceCode haskell"
><code
><span class="Keyword"
>data</span
><span class="Normal NormalText"
> TypeNode k</span
><br
/><span class="Normal NormalText"
> = Var </span
><span class="Comment"
>-- type variable</span
><br
/><span class="Normal NormalText"
> | Con </span
><span class="DataType TypeConstructor"
>String</span
><span class="Normal NormalText"
> </span
><span class="Comment"
>-- type constructor</span
><br
/><span class="Normal NormalText"
> | App (Id k) (Id k) </span
><span class="Comment"
>-- application</span
><br
/><br
/><span class="Keyword"
>type</span
><span class="Normal NormalText"
> Types k = Id k -> TypeNode k</span
><br
/><span class="Normal NormalText"
> </span
><span class="Comment"
>-- many types in one graph</span
><br
/></code
></pre
><p
>For example, “<code
>[a]->a</code
>” is first transformed to “<code
>((->) ([] a)) a</code
>”.</p
></div>
<div class="slide">
<h1 id="e8--types-continued"
>*E8 / Types (continued)</h1
><p
>“<code
>[a]->a</code
>” has the graph:</p
><p
><img src="type.png" alt="type"
/></p
></div>
<div class="slide">
<h1 id="e8--type-equations"
>*E8 / Type Equations</h1
><pre class="sourceCode haskell"
><code
><span class="Keyword"
>type</span
><span class="Normal NormalText"
> TEq k = (Id k, Id k)</span
><br
/></code
></pre
></div>
<div class="slide">
<h1 id="e8--instruction"
>*E8 / Instruction</h1
><p
>Define a function</p
><pre class="sourceCode haskell"
><code
><span class="Function FunctionDefinition"
>solveEqs ::</span
><br
/><span class="Normal NormalText"
> I i => </span
><br
/><span class="Normal NormalText"
> Link i k -> </span
><span class="Comment"
>-- fully separated map </span
><br
/><span class="Normal NormalText"
> Types k -> </span
><span class="Comment"
>-- typing environment</span
><br
/><span class="Normal NormalText"
> [TEq k] -> </span
><span class="Comment"
>-- type equations</span
><br
/><span class="Normal NormalText"
> ( [TEq k] </span
><span class="Comment"
>-- failed equations</span
><br
/><span class="Normal NormalText"
> , Link i k) </span
><span class="Comment"
>-- unifications</span
><br
/></code
></pre
><p
>The definition is just 13 rows..</p
></div>
</div>
</body
></html
>