12/08/2020 Code (Week 3 Wednesday)
Code (Week 3 Wednesday) List Properties
module ListProps where
import Test.QuickCheck
— Lists
— Proof of associativity of list semigroup
prop_semigroup :: [Int] -> [Int] -> [Int] -> Bool
prop_semigroup xs ys zs = ((xs ++ ys) ++ zs) == (xs ++ (ys ++ zs))
— Proof of identity of list monoid
— Left identity
prop_leftIdentity :: [Int] -> Bool prop_leftIdentity xs = xs == [] ++ xs
— Right itdentity prop_rightIdentity :: [Int] -> Bool
prop_rightIdentity xs = xs == xs ++ [] — List reverse
prop_involution :: [Int] -> Bool
prop_involution xs = xs == reverse (reverse xs)
Mersenne Primes
module Mersenne where
import Test.QuickCheck
nats :: [Int]
nats = 0 : map (+1) nats
— Seive of Eratosthenes primes :: [Int]
primes = 2 : rest
www.cse.unsw.edu.au/~cs3141/20T2/Week 03/Wednesday/Code.html
1/3
12/08/2020 Code (Week 3 Wednesday)
Ransom Note
where
rest = filter isPrime $ drop 3 nats
isPrime :: Int -> Bool
isPrime n = all (\p -> n `mod` p /= 0) smallerPrimes
where
smallerPrimes :: [Int]
smallerPrimes = takeWhile (\p -> p * p <= n) primes
prop_mersenne :: Positive Int -> Property
prop_mersenne (Positive n) = isPrime n ==> isPrime $ (2 ^ n) – 1
module Ransom where
import Test.QuickCheck
import Data.Char
import Data.List
import qualified Data.Set as S
import qualified Data.Map as M
type Magazine = String
type Message = String
— 1. Specify the ransom note check
rnoteSpec :: Magazine -> Message -> Bool
rnoteSpec magazine message = all enoughChars message
where
enoughChars :: Char -> Bool
enoughChars c = countChars c magazine >= countChars c message
countChars :: Char -> String -> Int
countChars c = length . filter (==c)
newtype Counts = Counts (M.Map Char Int) deriving (Eq, Show)
instance Ord Counts where
(Counts sub) <= (Counts super) = hasChars && hasSufficient
where
subChars = M.keysSet sub
superChars = M.keysSet super
hasChars = subChars `S.isSubsetOf` superChars
hasSufficient = and $ M.intersectionWith (<=) sub super
emptyCounts = Counts M.empty
increment :: Char -> Counts -> Counts
www.cse.unsw.edu.au/~cs3141/20T2/Week 03/Wednesday/Code.html
2/3
12/08/2020 Code (Week 3 Wednesday)
increment char (Counts counts) = Counts $ M.alter inc char counts
where
inc :: Maybe Int -> Maybe Int
inc Nothing = Just 1
inc (Just n) = Just $ n + 1
countChars :: String -> Counts
countChars = foldr increment emptyCounts
— 2. How can you implement a more efficient checking mechanism? rnote :: Magazine -> Message -> Bool
rnote magazine message = messageCounts <= magazineCounts
where
magazineCounts = countChars magazine
messageCounts = countChars message
-- 3. Show that it is equivalent using properties prop_rnote message magazine =
rnoteSpec message magazine == rnote message magazine
www.cse.unsw.edu.au/~cs3141/20T2/Week 03/Wednesday/Code.html
3/3