Semester 2, 2018

# Code (Week 1)

```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
> 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]
```

2018-11-16 Fri 19:37