# Code (Week 1)

## Table of Contents

## 1 Basic Haskell Programming

factorial :: Int -> Int factorial 0 = 1 factorial n | n > 0 = n * factorial (n - 1) | otherwise = error "urgh!" -- this is already defined in the standard prelude as -- (.) comp :: (b -> c) -> (a -> b) -> a -> c comp f g x = f (g x) type Point = (Int, Int) type Length = Int type Angle = Int data Colour = Red | Blue | Fuchsia | Cyan | Turquoise data Shape = Square Length | Triangle Angle Length Length | Rect Length Length deriving (Show) -- so that I can print it. area :: Shape -> Int area (Square s) = s * s area (Rect w h) = w * h area (Triangle theta s1 s2) = error "High school maths?!" -- Haskell's built-in lists are as follows: -- List a is written [a] -- Empty is written [] -- NonEmpty is written as : -- e.g NonEmpty 3 (NonEmpty 4 Empty) :: List Int -- is equivalent to 3:4:[] :: [Int] data List a = Empty | NonEmpty a (List a) deriving (Show) -- Just like "length", but for our lists length' :: List a -> Int length' Empty = 0 length' (NonEmpty x xs) = 1 + length' xs -- Just like (++), but for our lists append :: List a -> List a -> List a append Empty ys = ys append (NonEmpty x xs) ys = NonEmpty x (append xs ys) -- Already defined in prelude as (++) append' :: [a] -> [a] -> [a] append' [] ys = ys append' (x:xs) ys = x:(append' xs ys) -- Already defined in prelude as filter filter' :: (a -> Bool) -> [a] -> [a] filter' p [] = [] filter' p (x:xs) | p x = x : filter' p xs | otherwise = filter' p xs

## 2 Lexer

import Data.Char(isSpace, isDigit, isAlpha) import Data.List(partition) data Token = Kwd Keyword | Ident String | Times | Minus | Equals | Gt | Lt | LParen | RParen | LBrace | RBrace | Semi | Number Int deriving (Show) data Keyword = If | Else | Return | While deriving (Show) lexer :: String -> [Token] lexer [] = [] lexer (' ':cs) = lexer cs lexer ('\n':cs) = lexer cs lexer (c:cs) | isSpace c = lexer cs lexer ('*':cs) = Times : lexer cs lexer ('-':c:cs) = Minus : lexer (c:cs) lexer ('=':cs) = Equals : lexer cs lexer ('>':cs) = Gt : lexer cs lexer ('<':cs) = Lt : lexer cs lexer ('(':cs) = LParen : lexer cs lexer (')':cs) = RParen : lexer cs lexer ('{':cs) = LBrace : lexer cs lexer ('}':cs) = RBrace : lexer cs lexer (';':cs) = Semi : lexer cs lexer (c:cs) | isAlpha c = let (word,rest) = span isAlpha (c:cs) in checkKeyword word : lexer rest where checkKeyword :: String -> Token checkKeyword "if" = Kwd If checkKeyword "while" = Kwd While checkKeyword "else" = Kwd Else checkKeyword "return" = Kwd Return checkKeyword other = Ident other lexer ('/':'/':cs) = lexer (dropWhile (/= '\n') cs) lexer (c:cs) | isDigit c = let (numString, rest) = span isDigit (c:cs) in Number (read numString) : lexer rest lexer _ = []

We used the following C program as input:

int factorial(int n) { // comment if (n < 0) { return -1; } else { int ret = 1; while (n > 0) { ret = ret * n; n = n-1; } return ret; } }

To run our lexer on this file, use the following GHCi commands:

> :l Lexer.hs > file <- readFile "input.c" > lexer file

## 3 Mole Problem (Extension)

module Mole where import Data.List(nub) data State = G1 | G2 | G3 | G4 | G5 | Found | Initial deriving (Show, Eq) data Act = Start | D1 | D2 | D3 | D4 | D5 deriving (Show) initialState = Initial finalState = Found -- concatMap :: (a -> [b]) -> [a] -> [b] deltaSubset :: Act -> [State] -> [State] deltaSubset a ss = nub (concatMap (delta a) ss) isSolution :: [Act] -> [State] -> Bool isSolution [] ss = ss == [Found] isSolution (a:as) ss = isSolution as (deltaSubset a ss) allSequencesOfLength :: Int -> [[Act]] allSequencesOfLength 0 = [[]] allSequencesOfLength n = [ (a:as) | a <- [D1,D2,D3,D4,D5] , as <- allSequencesOfLength (n-1) ] candidates = map (\l -> Start:l) (allSequencesOfLength 0 ++ allSequencesOfLength 1 ++ allSequencesOfLength 2 ++ allSequencesOfLength 3 ++ allSequencesOfLength 4 ++ allSequencesOfLength 5) -- Returns false, indicating that no sequence of digs of length <= 5 is -- a solution. check = any (\acts -> isSolution acts [Initial]) candidates delta :: Act -> State -> [State] delta Start Initial = [G1,G2,G3,G4,G5] delta D1 G1 = [Found] delta _ G1 = [G2] delta D2 G2 = [Found] delta _ G2 = [G1,G3] delta D3 G3 = [Found] delta _ G3 = [G2,G4] delta D4 G4 = [Found] delta _ G4 = [G3,G5] delta D5 G5 = [Found] delta _ G5 = [G4] delta _ g = [g]