Haskell Utilities

HaskellUtilitiesBrianAllietNovember25,2006Contents1MathFunctions51.1MatrixFunctions.......................................51.2NumberTheoryFunctions..................................71.3MiscMathFunctions.....................................151.4BoolNumInstance......................................162DataStructures172.1BalancedTree.........................................172.2Trie...............................................252.3Tree...............................................272.4MemoryBuffer........................................293DataStructureUtilities323.1ArrayFunctions........................................323.2ListFunctions.........................................323.3MaybeFunctions.......................................384Monads394.1FailureMonad.........................................394.2MiscMonadFunctions....................................405Streams415.1InputStreams.........................................415.2OutputStreams........................................445.3Consumers...........................................465.4Producers...........................................466TextProcessingandParsers476.1CSVLibrary..........................................476.2ParsecFunctions.......................................496.3HTMLParser.........................................506.4HtmlUtilities.........................................536.5FormFunctions........................................567NetworkLibraries597.1CURLBindings........................................5927.2HTTPProtocolUtilities....................................637.3URIFunctions.........................................647.4WebBrowser..........................................677.5MiscIOFunctions.......................................687.6ForeignFunctionInterfaceUtilities.............................698TypeLevelMagic708.1TypeLevelNaturals.....................................708.2StronglyTypedHeterogeneousLists............................729Type-SafeWords749.1Introduction..........................................749.2WordTypes..........................................749.3Operations...........................................759.4StandardTypeclassInstances................................769.5AdvancedOperations....................................799.6TypeAliases..........................................8110Miscellaneous8210.1DebugingFunction......................................8210.2MiscHelperFunctions....................................8210.3Operators...........................................843IntroductionThisisasmall(althoughgrowing)libraryofusefulHaskellmodules.4Chapter1MathFunctions1.1MatrixFunctionsTheHillciphermakeheavyuseofmatrices.Matrixmultiplicationandinversionarekeypartsofthecipher.WhatfollowsisasmalllibraryofmatrixfunctionsforusewiththeHillciper(andpossiblyotherciphersinthefuture).matrixMap::(a→b)→[[a]]→[[b]]matrixMap=map.mapmatrixMapsimplyappliesagivenfunctiontoeveryelementoftheamatrixandreturnstheresultantmatrix.matrixAdd::Numa⇒[[a]]→[[a]]→[[a]]matrixAdd=zipWith(zipWith(+))matrixAddaddsthecorrespondingelementsoftwomatricestogether.matrixMul::Numa⇒[[a]]→[[a]]→[[a]]matrixMulab=[[r‘dotProd‘c|c←transposeb]|r←a]matrixMulMod::Integrala⇒a→[[a]]→[[a]]→[[a]]matrixMulModmab=matrixMap(flipmodm)$matrixMulabmatrixMulmultipliestwomatrices.Foreachrowofathedotproductisfoundfortheentirerowandeachofthecolumnsofb.matrixMinor::Numa⇒Int→Int→[[a]]→amatrixMinorij=matrixDet.skipi.map(skipj)matrixMinorfindstheminorforagivenpositioninamatrix.Theminoriscalculatedbyfindingthedeterminant(seematrixDet)ofthematrixthatresultsfromremovingtheallelementsinthesameroworcolumnasthegivenelement.5matrixDet::Numa⇒[[a]]→amatrixDet[]=1matrixDetm@(f:_)=f‘dotProd‘(head$matrixCofactorm)matrixDetfindsthedeterminantofasquarematrix.Thedeterminantiscalculatedbymultiply-ingeachelementofthefirstrowbyitscofactor.matrixCofactor::Numa⇒[[a]]→[[a]]matrixCofactorm=zipWith(map.(∗))signs$map(zipWith(∗)signs)$[[matrixMinorrcm|c←indices]|r←indices]whereindices=[0..lengthm−1]signs=cycle[1,−1]matrixCofactorfindsthecofactormatrixforagivenmatrix.Thecofactormatrixiscalculatedbycalculatingtheminorateachpositioninthematrix,invertingthesignofeveryotherelementineachrow,thenfinallyinvertingthesignofeveryelementineveryotherrow.matrixAdjoint::Numa⇒[[a]]→[[a]]matrixAdjoint=transpose.matrixCofactormatrixAdjointfindstheadjointofagivenmatrix.Theadjointiscalculatedbysimplytrans-posingthecofactormatrix.matrixInv::Fractionala⇒[[a]]→[[a]]matrixInvm=matrixMap(/matrixDetm)$matrixAdjointmmatrixInvfindstheinverseofamatrix.Theinverseiscalculatedbymultiplyingeveryelementoftheadjointofthematrixby1det(m).matrixInvMod::Integrala⇒a→[[a]]→[[a]]matrixInvModxm=matrixMap(mulModx$multInvModxd)awhered=matrixDetma=matrixAdjointmmatrixInvModfindstheinverseofamatrix(modm).Theinverseiscalculatedbymultiplying(modm)everyelementoftheadjointmatrixbythemultiplicitiveinverseofthedeterminant.matrixInvertable::Numa⇒[[a]]→BoolmatrixInvertablem=matrixDetm6=0matrixInvertableMod::Integrala⇒a→[[a]]→BoolmatrixInvertableModxm=gcd(matrixDetm)x=