Simulating non-deterministic choice through the List Monad

Question

I'm trying to write an evaluation function for a language that I am working on in which non-determinism can be permitted within an if-block, called a selection block. What I'm trying to achieve is the ability to pick an if/selection statement from the block whose guard is true and evaluate it but it doesn't matter which one I pick.

From searching, I found an example that performs in a similar way to what I would like to achieve through modelling coinflips. Below is my adapation of it but I'm having issue in applying this logic to my problem.

import Control.Monad

data BranchType = Valid | Invalid deriving (Show)
data Branch = If (Bool, Integer) deriving (Show, Eq)

f Valid   = [If (True, 1)]
f Invalid = [If (False, 0)]

pick = [Invalid, Invalid, Valid, Invalid, Valid]

experiment = do
        b <- pick
        r <- f b
        guard $ fstB r
        return r

s = take 1 experiment

fstB :: Branch -> Bool
fstB (If (cond, int)) = cond

main :: IO ()
main = putStrLn $ show $ s -- shows first branch which could be taken.

Below is my ADT and what I have been trying to make work:

data HStatement
  = Eval    HVal
  | Print   HVal
  | Skip    String
  | Do      HVal [HStatement]
  | If      (HVal, [HStatement])
  | IfBlock [HStatement] -- made up of many If
  | Select  [HStatement] -- made up of many If
  deriving (Eq, Read)


fstIf :: HStatement -> Bool
fstIf (If (cond, body)) = if hval2bool cond == True
                              then True
                              else False

h :: Env -> HStatement -> IOThrowsError ()
h env sb = do
         x <- g env sb
         guard $ fstIf x -- Couldn't match expected type ‘HStatement’ with actual type ‘[HStatement]’
         -- after guard, take 1 x then evaluate 

         

g :: Env -> HStatement -> IOThrowsError [HStatement]
g env (Select sb) = mapM (\x -> f env x) sb

f :: Env -> HStatement -> IOThrowsError HStatement
f env (If (cond, body)) = evalHVal env cond >>= \x -> case x of
                                                         Bool True  -> return $ If (Bool True,  body)
                                                         Bool False -> return $ If (Bool False, body)

The error I receive is the following : Couldn't match expected type ‘HStatement’ with actual type ‘[HStatement]’ at the guard line. I believe the reason as to why the first section of code was successful was because the values were being drawn from List but in the second case although they're being drawn from a list, they're being drawn from a [HStatement], not something that just represents a list...if that makes any sort of sense, I feel like I'm missing the vocabulary.

In essence then what should occur is given a selection block of n statement, a subset of these are produced whose guards are true and only one statement is taken from it.

Put some types on your functions. This will help GHC give you better error messages, and also help readers of this question (and probably you!) understand what you meant to do. — amalloy, Aug 14 '21 at 18:16

score 3 · Accepted Answer · answered Aug 14 '21 at 19:53

3

The error message is pretty clear now that you have some types written down. g returns IOThrowsError [HStatement], so when you bind its result to x in h, you have an [HStatement]. You then call fstIf, which expects a single HStatement, not a list. You need to decide how to handle the multiple results from g.

answered Aug 14 '21 at 19:53

amalloy

89,153
8
140
205

Is it not a problem with `guard`? Handling multiple instances from `g` is already what I'm trying to do (I think). I'm trying to emulate the first block of code in which I drawing from pick, applying `f` to it then using `guard` but in that particular instance of `guard`, it looks as if it's applying the boolean check across the entirty of the array. – Mr.Bloom Aug 14 '21 at 21:51
1

In your `experiment`, `f b :: [Branch]`, and then when you bind to it in the List monad you get `r :: Branch`, which is the right type to call `fstB` on. In `h`, you do nothing to extract single elements from the list. – amalloy Aug 14 '21 at 22:57
I understand you completely now! Back to the drawing board! – Mr.Bloom Aug 14 '21 at 23:28

Simulating non-deterministic choice through the List Monad

1 Answers1