Lab 3

[BertLisser]

Exercise 1 Nice solution with uncurry.

Exercise 2

parserTest :: Int -> Int -> IO ()
parserTest testsExecuted totalTests = if testsExecuted == totalTests then putStrLn ("\x1b[32m" ++ show totalTests ++ " tests passed\x1b[0m")
                else generateActualForm >>= \x -> let resultingForm = parse (show x) in if length resultingForm == 1 && equiv x (head resultingForm) then
                    do putStrLn ("pass on: " ++ show x)
                       parserTest (testsExecuted+1) totalTests
                  else error ("failed test on: " ++ show x)

equiv is not sufficient. Required is: That the forms have the same shape. So

parserTest :: Int -> Int -> IO ()
parserTest testsExecuted totalTests = if testsExecuted == totalTests then putStrLn ("\x1b[32m" ++ show totalTests ++ " tests passed\x1b[0m")
                else generateActualForm >>= \x -> let resultingForm = parse (show x) in if length resultingForm == 1 &&  x == (head resultingForm) then
                    do putStrLn ("pass on: " ++ show x)
                       parserTest (testsExecuted+1) totalTests
                  else error ("failed test on: " ++ show x)

Exercise 3 The following rule is too complicated. I don't recognize the rule -- p ∨ (q ∧ r) == (p ∨ q) ∧ (p ∨ r) in the following fragment

applyDistributiveLaw (Dsj formList) = Dsj (foldr (\x acc -> let y = applyDistributiveLaw x in
           if not (null acc) && (isConjunction x || isConjunction (head acc)) then let cnjOne = head acc
                                                                                       cnjTwo = y
                                                                                       conj = Cnj (if isDisjunction cnjOne then map (\ x -> Dsj (x : getAsList cnjOne)) (getAsList cnjTwo)
                                                                                                    else if isDisjunction cnjTwo then map (\ x -> Dsj (x : getAsList cnjTwo)) (getAsList cnjOne)
                                                                                                    else [Dsj [x,y] | x <- getAsList cnjOne, y <- getAsList cnjTwo]) in conj: tail acc
           else if isDisjunction y then getAsList y++acc
           else y:acc) [] formList)

Simpler solution:

cnf :: Form -> Form
cnf x = cnf' $ nnf $ arrowfree x

-- preconditions: input is arrowfree and in nnf
cnf' :: Form -> Form
cnf' (Prop x) = Prop x
cnf' (Neg (Prop x)) = Neg (Prop x)
cnf' (Cnj fs) = Cnj (map cnf' fs)
cnf' (Dsj []) = Dsj []
cnf' (Dsj [f]) = cnf' f
cnf' (Dsj (f1:f2:fs)) = dist (cnf' f1) (cnf' (Dsj(f2:fs)))

dist :: Form -> Form -> Form
dist (Cnj []) f = Cnj[] {-- f --}
dist (Cnj [f1]) f2 = dist f1 f2
dist (Cnj (f1:fs)) f2 = Cnj [dist f1 f2, dist (Cnj fs) f2]
dist f (Cnj []) = Cnj[] {-- f --}
dist f1 (Cnj [f2]) = dist f1 f2
dist f1 (Cnj (f2:fs)) = Cnj [dist f1 f2, dist f1 (Cnj fs)]
dist f1 f2 = Dsj [f1,f2]

Exercise 4

-- This method generates an infinite list of random floating-point numbers between 0 and 1. These numbers are generated in advance, so I can unwrap the monad
-- they're in and don't have to further bother any IO monads till the algorithm is over. The `curRand` field of the `TreeState` datatype holds the current
-- index that will be fetched from this list.
randomNumberStream :: IO [Float]
randomNumberStream = do
    g <- newStdGen
    return $ randomRs (0.00,1.00) g

Why not

randomNumberStream ::Int-> IO [Int]
randomNumberStream n = do
    g <- newStdGen
    return $ randomRs (0,n) g

? Floats occur nowhere.

[SimonBaars]

The line p ∨ (q ∧ r) == (p ∨ q) ∧ (p ∨ r) just describes how the distributive mathemathical law works. We distribute p over q and r and thus get (p ∨ q) ∧ (p ∨ r).

[SimonBaars]

The == means that p ∨ (q ∧ r) is equivalent to (p ∨ q) ∧ (p ∨ r).

[BertLisser]

I mean: I don't recognise that rule in the mentioned code fragment. I have no problems with ==.

[SimonBaars]

Why not

randomNumberStream ::Int-> IO [Int]
randomNumberStream n = do
    g <- newStdGen
    return $ randomRs (0,n) g

? Floats occur nowhere.

I actually have a very good reason for this. The thing is: performance. First, I wrote the random generator like this:

data TreeState = TreeState {amountOfProperties :: Int, form :: Form}

chooseTreeOption :: Int -> Int
chooseTreeOption maximumNumber = unsafePerformIO (getStdRandom(randomR (0,maximumNumber-1)))

maxTreeChance = 10 -- This number decides the size of the resulting form.

generateActualForm :: Form
generateActualForm = form (generateForm (maxTreeChance-1) (TreeState 1 p)) -- This number decides the maximum amount of subforms in the resulting form.

generateForm :: Int -> TreeState -> TreeState
generateForm leftTreeChance state = if chooseTreeOption maxTreeChance < leftTreeChance then chooseRandomSplitForm (leftTreeChance - 1) state else chooseRandomProperty state

chooseRandomSplitForm :: Int -> TreeState -> TreeState
chooseRandomSplitForm leftTreeChance state = case chooseTreeOption 2 of 0 -> let x = generateFormList leftTreeChance state maxTreeChance []
                                                                             in if chooseTreeOption 2 == 0 then treeStateListToTreeState Cnj x
                                                                                                           else treeStateListToTreeState Dsj x
                                                                        1 -> let x = generateForm leftTreeChance state
                                                                                 y = generateForm leftTreeChance x
                                                                             in if chooseTreeOption 2 == 0 then TreeState (amountOfProperties y) (Impl (form x) (form y))
                                                                                                           else TreeState (amountOfProperties y) (Equiv (form x) (form y))

treeStateListToTreeState :: ([Form] -> Form) -> [TreeState] -> TreeState
treeStateListToTreeState f states = TreeState (amountOfProperties (last states)) (f (map form states))

generateFormList :: Int -> TreeState -> Int -> [TreeState] -> [TreeState]
generateFormList leftTreeChance state maxListSize currentFormList = case chooseTreeOption 2 of 0 -> generatedState:currentFormList
                                                                                               1 -> generatedState:generateFormList leftTreeChance generatedState (maxListSize-1) currentFormList
                                                                                               _ -> error "Something impossible just happened!"
                                                            where generatedState = generateForm leftTreeChance state

chooseRandomProperty :: TreeState -> TreeState
chooseRandomProperty state = TreeState (if chosenProperty == props then props + 1 else props) (Prop chosenProperty)
  where props = amountOfProperties state
        chosenProperty = chooseTreeOption (props + 1)

However, the usage of unsafe gave issues (of course). So I changed it all to IO datatypes to fix those unsafe related issues:

data TreeState = TreeState {amountOfProperties :: Int, form :: Form}

chooseTreeOption :: Int -> IO Int
chooseTreeOption maximumNumber = getStdRandom(randomR (0,maximumNumber-1))

maxTreeChance = 5 -- This number decides the size of the resulting form.

generateActualForm :: IO Form
generateActualForm =  generateForm (maxTreeChance-1) (return(TreeState 1 p)) >>= \x -> return (form x);

generateForm :: Int -> IO TreeState -> IO TreeState
generateForm leftTreeChance state = chooseTreeOption maxTreeChance >>= \x -> if x < leftTreeChance then chooseRandomSplitForm (leftTreeChance - 1) state else chooseRandomProperty state

chooseRandomSplitForm :: Int -> IO TreeState -> IO TreeState
chooseRandomSplitForm leftTreeChance state = chooseTreeOption 2 >>= \treeOption -> case treeOption of 0 -> generateFormList leftTreeChance state maxTreeChance [] >>= \x ->
                                                                                                           chooseTreeOption 2 >>= \leftOption -> if leftOption == 0 then treeStateListToTreeState Cnj x
                                                                                                                                                                       else treeStateListToTreeState Dsj x
                                                                                                      _ -> let genForm = generateForm leftTreeChance state in genForm >>= \x ->
                                                                                                           generateForm leftTreeChance genForm >>= \y ->
                                                                                                           chooseTreeOption 2 >>= \rightOption -> return (if rightOption == 0 then TreeState (amountOfProperties y) (Impl (form x) (form y))
                                                                                                                                                                              else TreeState (amountOfProperties y) (Equiv (form x) (form y)))

treeStateListToTreeState :: ([Form] -> Form) -> [IO TreeState] -> IO TreeState
treeStateListToTreeState f states = sequence states >>= \currentStates -> return(TreeState (amountOfProperties (last currentStates)) (f (map form currentStates)))

generateFormList :: Int -> IO TreeState -> Int -> [IO TreeState] -> IO [IO TreeState]
generateFormList leftTreeChance state maxListSize currentFormList = chooseTreeOption 2 >>= \chosenOption -> case chosenOption of 0 -> return (generatedState:currentFormList)
                                                                                                                                 _ -> generateFormList leftTreeChance generatedState (maxListSize-1) currentFormList >>= \genList -> return(generatedState:genList)
                                                            where generatedState = generateForm leftTreeChance state

chooseRandomProperty :: IO TreeState -> IO TreeState
chooseRandomProperty state = state >>= \currentState -> let props = amountOfProperties currentState in chooseTreeOption (props + 1) >>= \chosenProperty -> return (TreeState (if chosenProperty == props then props + 1 else props) (Prop chosenProperty))

This worked, only the performance was very very bad (which I could never have known). Large problems completely crashed. So I came up with a solution of not using too much IO (because of the performance issues) by generating all random numbers in advance to the calculcation. However, as I don't know yet between what numbers I want them at that point (could be anything), I create random floats between 0 and 1 which I can later translate to any random number bound I want by using the following functions:

-- Retrieves the random number at the given index from the infinite random number list. Multiplies the random number so it is in between 0 and a given maximum,
-- then converts it to an integer by using the `floor` function.
getCurRandNum :: Int -> [Float] -> Int -> Int
getCurRandNum x randList maxNum = floor ((randList !! x) * fromIntegral maxNum)

-- Gives the current random number for a given treestate.
getCurRand :: TreeState -> [Float] -> Int -> Int
getCurRand TreeState{curRand = x} = getCurRandNum x

I tried to explain this process using the following comment:

-- This method generates an infinite list of random floating-point numbers between 0 and 1. These numbers are generated in advance, so I can unwrap the monad
-- they're in and don't have to further bother any IO monads till the algorithm is over. The `curRand` field of the `TreeState` datatype holds the current
-- index that will be fetched from this list.

However, as it's quite an extensive process (as you see) concerning several revisions I understand that this might not have been completely clear just based on that comment.

[BertLisser]

I understand your point. But the following remark about the performance surprises me. This worked, only the performance was very very bad (which I could never have known). Large problems completely crashed.

[SimonBaars]

Yes, it also surprised me. It is probably because the nested extraction of monads is not very optimized way in haskell.