Creating list comprehension from scratch in haskell using monads

Question

I am trying to create an interpreter as an exercise that I have come across, and the interpreter should also be able to make a list comprehension that should work similar to the original Haskell-list comprehension. In the version in the exercise however the list comprehension shall be evaluated as part of an eval-function with below signature:

eval :: Expr -> Comp Value

Where

data Expr =
    Const Value
  | Var VName    
  | Call FuncName [Expr]
  | List [Expr]
  | Compr Expr [ExprClause]
  deriving (Eq, Show, Read)

data ExprClause =
    ForCl VName Expr
  | IfCl Expr
  deriving (Eq, Show, Read)

Furthermore where Comp refers to a monad with newtype Comp a = Comp {runComp :: Env -> (Either RunErr a, [String]) }´as constructor.

And where

data Value =     
  | IntVal Int
  | StringVal String
  | ListVal [Value]
  deriving (Eq, Show, Read)

data VName = String

When the eval-function is given Compr eBody [ForCl VName Expr], each occurrance for ForCl will correspond to a for-loop for the variable named by VName, such that e.g. eval (Compr (2*x) [ForCl (Var "x") (Call "range" (Const (IntVal 10)))] will be equivalent to the python list comrpehension [2*x for x in range 10]

I am able to create a function that looks like the following:

eval (Compr eBody [(ForCl vname e)]) = 
  let body = [(eval eBody) | eBody <- [e]]  
  in 
  do   
  values <- sequence $ body  
  return (ListVal values)

While it does compile it doesn't take vname into account such that the input given in VName points to the same variable as the one (possibly) contained in the eBody. This might require more Monadic computations and involvement than what I imply in my solution. This is however something I am unsure of.

Can you give me some ideas how to make before mentioned 'co-reference', such that that I might also be able to deal with several variables contained in eBody and with each their ForCl.

Answer 1

[(eval e0) | e0 <- [e]] is equivalent to [eval e], which is not what you intended. You aren’t using the original e0 at all here, but another local variable with the same name.

Since you haven’t shown the definition of Env I’ll assume type Env = [(VName, Value)] for now. Where you wrote data VName = String, I believe you meant type VName = String. And where you wrote CCFor, I’ll assume you meant ForCl.

If you haven’t done so already, to implement local variable binding, you can include a case for eval (Var vname) (using e.g. lookup), and add a way to update the local environment, such as this:

withVar :: VName -> Value -> Comp a -> Comp a
withVar name value comp =
  Comp $ \ env -> runComp ((name, value) : env) comp

Now, your goal is to implement a transformation that simplifies the list comprehension one clause at a time. For example, [e | x <- xs, y <- ys] is equivalent to the concatenation of [e | y <- ys] evaluated for each value x from in xs. And a comprehension with no clauses remaining is simply a list.

Since eval produces a Value, but here we are always working with lists, I will introduce two helper functions. The first will just check for a list value.

needList :: Value -> Comp [Value]
needList (ListVal xs) = pure xs
needList _ = {- Raise an error. -}

The other, local to eval, will evaluate a list comprehension. It can iterate over the clauses recursively, using withVar to bind each variable.

When reaching the end, it should evaluate the comprehension’s main expression.

eval (Compr e0 clauses0) = ListVal <$> evalCompr clauses0
  where

    evalCompr :: [ExprClause] -> Comp [Value]

    evalCompr (ForCl vname e : clauses) = do

      list <- needList =<< eval e

      results <- for list $ \value -> do
        withVar vname value (evalCompr clauses)

      {- Collect results. (Hint: ‘>>=’.) -}

    evalCompr (IfCl e : clauses) =
      {- Filter results. (Hint: ‘guard’.) -}

    evalCompr [] = do
      value <- eval e0
      {- Produce one result. (Hint: ‘pure’.) -}

I’ll leave the rest for you to fill in on your own.