BEng,BSc,MEngandMMathDegreeExaminations
代写Haskell – 这是利用Haskell进行训练的代写, 对Haskell的流程进行训练解析, 包括了Haskell等方面
ModuleCode
COM00025I
BEng,BSc,MEngandMMathDegreeExaminations2020-
Department ComputerScience
Title Software
Issued: 09:00amonWednesday19thMay2021.
Submissiondue: 09:00onThursday20thMay2021.
Feedback&Marksdue: Thursday17thJune2021.
TimeAllowed 24Hours(NOTE:paperslatebyupto30minuteswillbesubjecttoa5mark penalty;paperslaterthan30minuteswillreceive0marks).
Notificationoferrorsinthepapermaybemadeupto onehour afterthestarttime.Ifyou wishtoraiseapossibleerroritmustbedonethroughcs-exams@york.ac.ukwith enoughtimeforaresponsetobeconsideredandmadewithinthefirsthour.
TimeRecommended THREEhours
WordLimit Not Applicable.
AllocationofMarks:
Thispaperhastwoquestions,eachworth45marks.Inaddition,thereare 10marks allocated tostyle,clarity,andqualityofcode.
Instructions:
Candidatesshouldanswer all questionsusingHaskell.Failingtodosowillresultinamarkof 0%.Foreveryquestion,atemplatehasbeenprovided ( Q
YoumayuseanyvaluesdefinedinthestandardPrelude,butyoumaynotimportanyother moduleunlessexplicitlypermitted.YoumayuseNeilMitchellsHoogetodiscoveruseful functionsinthe Prelude.
WheretestsaccompanytheEnglishdescriptionoftheproblem,itisnotnecesarilyenoughfor
Page1of12 Turnover.
yourimplementationtopasstheteststobecorrect.Partiallyfunctionalsolutionswith undefined ,maybeconsideredforpartofthefullmarks.
Download thepaperandtherequiredsourcefilesfromtheVLE,inthe"Assessment"section. Oncedownloaded,unzipthefile.You must saveallyourcodeintheClosedExamination folderandtherelated Q
SubmityouranswerstotheDepartmentsTeachingPortalasasingle .zip filecontainingthe ClosedExaminationfolderanditsfiles.FailingtoincludetheClosedExamination folderwillresultinamarkof0%.Otherarchivalformatsuchas.rarand.tarfileswillnotbe accepted.
Ifaquestionisunclear,answerthequestionasbestasyoucan,andnotetheassumptionsyou havemadetoallowyoutoproceed.Pleaseinformcs-exams@york.ac.ukaboutany suspectederrorsonthepaperimmediatelyafteryousubmit.
Page2of
ModuleCode
COM00025I
ANoteonAcademicIntegrity
Wearetreatingthisonlineexaminationasatime-limitedopenassessment,andyouare thereforepermittedtorefertowrittenandonlinematerialstoaidyouinyouranswers.
However,youmustensurethattheworkyousubmitisentirelyyourown,andforthewhole timetheassessmentisliveyoumustnot:
- communicatewithdepartmentalstaffonthetopicoftheassessment
- communicatewithotherstudentsonthetopicofthisassessment
- seekassistancewiththeassignmentfromtheacademicand/ordisabilitysupport services,suchastheWritingandLanguageSkillsCentre,MathsSkillsCentreand/or DisabilityServices.(Theonlyexceptiontothiswillbeforthosestudentswhohavebeen recommendedanexamsupportworkerinaStudentSupportPlan.Ifthisappliestoyou, youareadvisedtocontactDisabilityServicesassoonaspossibletodiscussthe necessaryarrangements.)
- seekadviceorcontributionfromanythirdparty,includingproofreaders,onlinefora, friends,orfamilymembers.
Weexpect,andtrust,thatallourstudentswillseektomaintaintheintegrityoftheassessment, andoftheiraward,throughensuringthattheseinstructionsarestrictlyfollowed.Failureto adheretotheserequirementswillbeconsideredabreachoftheAcademicMisconduct regulations,wheretheoffencesofplagiarism,breach/cheating,collusionandcommissioning arerelevant:seeAM1.2.1 (NotethissupercedesSection7.3oftheGuidetoAssessment).
Page3of12 Turnover.
1 (45marks) Shortquestions
(i) [1mark] WriteafunctionisHaskellthattakesastringandreturnsTrueifthestringis "Haskell"andFalseotherwise.
Yoursolutionshouldsatisfy:
test Haskell :: Bool
testHaskell =
(isHaskell "Haskell" == True) &&
(isHaskell "Software" == False) &&
(isHaskell "" == False) &&
(isHaskell "haskell" == False)
(ii) [1mark] WriteafunctionlowerVowelthattakesastringandreturnsTrueifthestring hasonlylowercasevowels(a,e,i,o,u)andFalseotherwise.
Yoursolutionshouldsatisfy:
testlv:: Bool
testlv = (lowerVowel "ue" == True) &&
(lowerVowel "ueA" == False) &&
(lowerVowel "uea" == True)
(iii) [2marks] WriteafunctionprodCubethatcomputestheproductofthecubeofnumbers inalistthataredivisibleby2butnotdivisibleby4.Yoursolutionshouldsatisfy:
Yoursolutionshouldsatisfy:
testprodCube :: Bool
testprodCube = (prodCube [] == 1)
&& (prodCube [4, 8] == 1)
&& (prodCube [4, 6, 8] == 216)
&& (prodCube [4, 6, 8, 12] == 216)
&& (prodCube [2..11] == 1728000)
(iv) [2marks] WriteafunctionconsDiffthatcomputesthedifferencebetweenthenumber ofconsonants"bcdfghjklmnpqrstvwxyzBCDFGHJKLMNPQRSTVWXYZ"andthenumberofdigit charactersinastring.Yoursolutionshouldsatisfy:
testconsDiff :: Bool
testconsDiff =
(consDiff "" == 0)
&& (consDiff "SOf3in2021" == -2)
&& (consDiff "Software123andTheory123" == 5)
&& (consDiff "HASkellprogramming2021" == 9)
(v) [4marks] TheInternationalAirTransportAssociations(IATA)LocationIdentifierisaunique
Page4of
ModuleCode
COM00025I
andalluppercase3-lettercodeusedinaviationtoidentifyanairport,forexampleLHR,JFKand
BHX.Forthepurposesofthisquestion,IATAlocationidentifiershouldconsistofonly
consonants"BCDFGHJKLMNPQRSTVWXYZ".
(a) [2marks] WriteafunctionisIATAthattestswhetherornotastringisanIATA
locationidentifier.
Yoursolutionshouldsatisfy:
testisIATA :: Bool
testisIATA =
(isIATA "" == False) &&
(isIATA "MAN" == False) &&
(isIATA "LHR" == True) &&
(isIATA "LHRT" == False) &&
(isIATA "lhr" == False) &&
(isIATA "JFK" == True) &&
(isIATA "BHX" == True)
(b) [2marks] WriteafunctioncountIATAthatcountsthenumberofIATAlocation
identifiersinalistofstrings.
Yoursolutionshouldsatisfy:
testcountIATA :: Bool
testcountIATA =
(countIATA ["LHR"] == 1) &&
(countIATA ["LHR", "Lhr", "MAN", "JFK", "", "jfk"] == 2) &&
(countIATA ["LHR", "BHX", "MAN", "JFK", "ACC", "LRHT"] == 3)
(vi) [5marks]
ConsiderthetypeofstudentsrecordStudents:
type Students = [(Name, Age, College)]
type Name = String
type Age = Int
type College = String
Abuswillnormallycarrystudentsbetweencampusesandrecordsofallthestudentstravelling
onaparticularbusaremaintained.Ifastudentboardsthebus,his/herrecordisaddedtothe
busdatabaseandtherecordisremovedwhenthestudentgetsoffthebus.Belowisthe
currentstateof bus66 inaformofadatabasewithstudentsrecords onBus.
onBus66 :: Students
onBus66 =
Page5of12 Continued.
[("Zain", 18, "Halifax"), ("Julia", 20, "Constantine"),
("Mandy", 22, "Goodricke"), ("Jack", 24, "Constantine"),
("Emma", 21, "Langwith"), ("Zack", 19, "Halifax"),
("Alice", 21, "Halifax"), ("Bob", 19, "Alcuin"),
("Lui", 22, "Goodricke")]
(a) [1mark] Writeafunctioncollegesthattakesanageandreturnsalistofall
collegeswithstudentscurrentlyonboardbus66withthatage.
(b) [2marks] WriteafunctionjoinBusthataddstherecordofastudenttothe
databaseoncethestudentgetsonboardthebus.
(c) [2marks] WriteafunctionoffBusthatremovestherecordofastudentfromthe
databaseoncehe/shegetsoffthebus.Thereshouldntbeanychangetothedatabaseif
therecorddoesnotexist.
(vii) [5marks] Considerthetype
type BoolD a = (Bool, a)
Avalue(True, x)istobeinterpretedasxisavalidresultand(False, x)asxisinvalid
andshouldnotbeused.AbetterwayofrepresentingsuchvaluesistouseaMaybetype.
(a) [1mark] Writeafunctionbd2mthatconvertsBoolD atoMaybe a.
(b)[3marks] WriteafunctionbDSumthatreturnsaBoolD Int;thesumofalldigitsin
alistofcharacters.Assumethesumiszeroforalistwithoutdigits.
(c)[1mark] WriteafunctionmBSumwhichusesthefunctionbd2mandbDSumtoreturn
aMaybetypefromthesumofalldigitsinalistofcharactersasdescribedinquestion
(b).
(viii) [9marks] Consider
data TreeP a = Leaf Int | Node (TreeP a) a (TreeP a) deriving (Eq, Show)
Ina regulartree thevalueinaleafisthelengthofthepathfromtheroottotheleaf.Hencewe
define:
emptyTreeP :: TreeP a
emptyTreeP = Leaf 0
Inan ordered tree,allthevaluesintheleft-handsubtreearestrictlysmallerthanthevalueat
theroot,allthevaluesintheright-handsubtreearestrictlygreaterthanthevalueattheroot,
andbothsubtreesareordered.
(a) [6marks] Writeafunctionitptoinsertavalueintoaregular,orderedtree.
Page6of
ModuleCode
COM00025I
(b) [3marks] WriteafunctiontreeListthatreturnsalistwiththevaluesofaregular,
orderedtreeinascendingorder.
(ix) [8marks] Consider
data DBTree = DBLeaf | DBNode DBTree (Int, String) DBTree deriving (Eq, Show)
Ina binarysearchtree if k isthekeyinanode,thenallkeysintheleftsubtreemustbeless
than k ,andallthekeysintherightsubtreemustbegreaterthan k .Consideradatabasetable
(like smallDB )withstudent-idandnamepair,representedasabinarysearchtree.
smallDB :: DBTree
smallDB = DBNode (DBNode DBLeaf (2,"James") DBLeaf) (3,"Maxwell")
(DBNode DBLeaf (6,"Helen") DBLeaf)
WriteafunctionstdUpdatewhichtakesastudent-id,anewnameandadatabaseorganised
asabinarysearchtree,andreturnsanewtreewiththestudentsnewname.However,youare
expectedtoreturnanerrormessageifavalidrecordwiththeprovidedstudent-iddoesnot
existinthedatabase.YouwillneedtodefineanappropriatetypeforError,aspartof
yoursolution.
Yoursolutionshouldsatisfy:
testUpdate :: Bool
testUpdate =
(stdUpdate 6 "Abi" smallDB == Right (DBNode (DBNode DBLeaf (2,"James")
DBLeaf) (3,"Maxwell") (DBNode DBLeaf (6,"Abi") DBLeaf))) &&
(stdUpdate 8 "Mandy" smallDB == Left "There is no such student with ID: 8")
(x) [8marks]
RecallthedefinitionoftheProofLayouttypeconstructor:
infixr 0 :=: -- the fixity and priority of the operator
data ProofLayout a = QED | a :=: ProofLayout a deriving Show
Considerthedefinitionsofthe Prelude functions:
head :: [a] -> a
head (x:_) = x -- head.
foldr :: (a->b->b) -> b -> [a] -> b
foldr _ z [] = z -- foldr.
foldr f z (x:xs) = f x (foldr f z xs) -- foldr.
const :: a -> b -> a
const x y = x -- const.
Page7of12 Continued.
Define:
caput :: [a] -> a caput = foldr const undefined — caput.
Giveavalueoftype ProofLayouta thatcapturestheproofof
x::a, xs :: [a], caput (x:xs) == head (x:xs)
Forfullmarks,eachstepmustbeannotatedwiththerulethatjustifiesthestep.
caputHead :: a -> [a] -> ProofLayout a
caputHead = undefined
Page8of
ModuleCode
COM00025I
2 (45marks) Extendedexample
Itisnotnecessarytoknowanythingaboutthecardgame ContractBridge (orjust Bridge )for
thisquestion.Anythingneededwillbeexplained.Whereyoumaybefamiliarwithdifferent
rulestothosedescribedintheaccompanyingfiles, therulesandtestsintheaccompanying
filestakeprecedence.
(i) [2marks] Definea pack ofcardsasalistof Card ,containingeachcardexactlyonce.The suitsmustbearrangedintheorder: Clubs , Diamonds , Hearts , Spades ;withineachsuitthe cardsmustbearrangedintheorder Two , Three ,…, Ten , Jack , Queen , King , Ace.
Types Card , Suit and Value aredefinedintheimportedmodule Pack ,whichyouare
recommendedtoread(butmust not modify)aswellasutilityfunctionsforprintingstructures
containingcards.
Yoursolutionshouldsatisfy:
packTest :: Bool
packTest =
pack!!3 == Card Clubs Five
&& pack!!4 == Card Clubs Six
&& pack!!16 == Card Diamonds Five
&& pack!!31 == Card Hearts Seven
&& pack!!48 == Card Spades Jack
Togainfullmarksyoursolutionshouldtakeadvantageofthefactthatthetypesusedto
describe Card areinstancesof Enum.
Inthenextgroupofquestionsyouwillbuildafunctionthatmimicsthewaythatpeople
preparethegame,by shuffling thepackandthen dealing thepack.
(ii) [3marks] Astreamofpseudorandomnaturalnumberscanbegeneratedbythe linear congruentialmethod .Givenanyelementofthestream, n ,thenextelementis:
a*n+c mod m
forsuitablevaluesof a , c ,and m .Pickingthesevaluescanbedifficult,butonereasonable
assignmentis a== 7^5 , c== 0 ,and m== 2^31 1 .
Define psrn tocomputethenextelementofthestreambythelinearcongruentialmethod,
usingthesevalues.
Yoursolutionshouldsatisfy:
psrnTest :: Bool
psrnTest = psrn 1234567890 == 395529916 && psrn 2468013579 == 1257580448
(iii) [5marks] Implementafunction, insertMod ,toinsertanelementintoalistatagiven
Page9of12 Continued.
position.Ifthegivenpositionislargerthanthelengthofthelisttheninsertionshouldbeatthe
positionfoundbytakingtheinputmodulothenumberofinsertionpositions.
Yoursolutionshouldsatify:
insertModTest :: Bool
insertModTest = insertMod 0 "hello" x == "xhello"
&& insertMod 5 "hello" x == "hellox"
&& insertMod 3 [0..4] 9 == [0, 1, 2, 9, 3, 4]
&& insertMod 24 "hello" x == "xhello"
&& insertMod 131 "hello" x == "hellox"
&& insertMod 1011 [0..4] 9 == [0, 1 ,2, 9, 3 ,4]
(iv) [6marks] Implementafunction, shuffleStep thatcalculatesasinglestepofashuffle(the nextquestionasksforthewholeshuffle).Thefunction shuffleStep takesafunctionover numbers,anumberlistpair,andanelement.Theresultisalsoanumber-listpair.Thenumber intheoutputpairisgivenbyapplyingthefirstargumenttotheinputnumber.Thelistinthe outputpairisobtainedbyinsertingthepotentialelementintothelistatthepositiongivenby thenumberintheinputpair,followingthesamerulesthat insertMod follows.
Yoursolutionshouldsatisfy:
shuffleStepTest :: Bool
shuffleStepTest =
shuffleStep id ( 3, "hello") x == ( 3, "helxlo")
&& shuffleStep psrn (1234567890, [0 .. 4]) 9 == ( 395529916, [9,0,1,2,3,4])
&& shuffleStep psrn (2468013579, [0 .. 4]) 9 == (1257580448, [0,1,2,9,3,4])
(v) [10marks] Wecangettheeffectofrandomising,or shuffling ,ofalist,byrepeatedlytaking anelementofalistandinsertingitintoasecond,initiallyempty,listatarandomposition.To obtainthestreamofrandomnumbers,a seed ,orstartingpoint,anda nextnumber function areparametersofthefunction.Implementthe shuffle function.
Yoursolutionshouldsatisfy:
shuffleTest :: Bool
shuffleTest =
shuffle psrn 1234567890 [0 .. 9] == [9,4,1,0,3,7,6,5,8,2]
&& shuffle psrn 2468013579 [0 .. 9] == [2,4,1,3,5,8,9,6,0,7]
&& shuffle id 0 [0 .. 9] == [9,8,7,6,5,4,3,2,1,0]
&& shuffle (+1) 0 [0 .. 9] == [0,1,2,3,4,5,6,7,8,9]
(vi) [7marks] Implementafunction, deal ,todistributealistasevenlyaspossibleintofour orderedsublists.
Yourfunctionshouldsatisfy:
dealTest :: Bool
Page10of
ModuleCode
COM00025I
dealTest =
deal [0..9] == ([0,4,8],[1,5,9],[2,6],[3,7])
&& deal "hello world!" == ("hor"," el","dlw","!lo")
Youmayusethefunction insertOrd inyoursolutions:
insertOrd :: Ord a => a -> [a] -> [a]
insertOrd w = foldr f [w]
where
f x ys@(z:zs) | x > w = z:x:zs
| otherwise = x:ys
deal :: Ord a => [a] -> ([a], [a], [a], [a])
deal = undefined
Usingyourfunction deal ,implementafunction, shuffleDeal that,givenaseed,andanext
numberfunction,shufflesanddealsafullpackofcardsforagameofbridge.
Whenprettyprintedusingthefunction pp definedinmodule Pack availablein Pack.hs ,your
functionshouldprintasshownin Q2vi.hs. Note: theprettyprint pp outputonWindowsOS
mayusedifferentfonts.
(vii) [12marks] Agameofbridgeisplayedeitherwith
* onesuitbeingdesignatedthe trump suit,or
* nosuitbeingdesignatedthetrumpsuit.
Giveasuitabledatatypetorepresentthecurrenttrumpsuit,orthatthereisnotrumpsuit.
Definethespecialvalue noTrumpSuit::Trumps whichrepresentstherebeingnotrumpsuit,
andthefunction theTrumpSuit::Suit->Trumps ,sothat theTrumpSuits isavaluethat
represents s beingthetrumpsuit.
noTrumpSuit :: Trumps
theTrumpSuit :: Suit -> Trumps
type Trumps = ()
-- TREAT AS UNDEFINED TYPE;
you may replace type by newtype or data
noTrumpSuit = undefined
theTrumpSuit = undefined
Ineachroundoneplayerleads,andthentheotherplayersfollowthelead,inrotation.The
followingrulesareusedtodecidethewinneroftheround,or trick :
* ifthereisnotrumpsuit,orthereisatrumpsuitbutnocardsofthatsuithavebeen
exposed,thenthehighestcardofthesamesuitastheledcard(thefirstcardexposed)
Page11of12 Continued.
wins.
* ifthereisatrumpsuit,andcardsofthatsuithavebeenexposed,thenthehighestcard
ofthetrumpsuitwins.
* Thetype Card isdeclaredasderiving Ord ,inawaysuchthatthemaximumcardina
listmatchestheBridgenotionofhighestcardinatrick.
Implementafunction, trickWinner ,thattakes:
* atrumpsuit,ornotrumps,
* aledcard,and
* alistofthreefollowingcards,
anddeterminesthewinningcardofthefour.
Yoursolutionshouldsatisfy
trickWinnerTest :: Bool trickWinnerTest = twh noTrumpSuit == Card Spades Ace && twh (theTrumpSuit Diamonds) == Card Spades Ace && twh (theTrumpSuit Hearts) == Card Hearts Four where twh t = trickWinner t (Card Spades Two) [Card Hearts Four, Card Spades Ace, Card Spades King]
Endofexaminationpaper
Page12of