Переписать код с продолжениями

Question

У меня есть код, который оценивает примитивные программы. Программа представляет собой список операторов (выражение, блок, оператор возврата). Результатом оценки является последнее оцененное выражение. Также оценщик должен правильно относиться return утверждение (т.е. прекратить оценку после первого появления return).

Для реализации этой логики я передаю специальную функцию обратного вызова (NextStep), которые делают следующий шаг оценки после текущего утверждения. Я не вызываю следующий шаг при обработке оператора return:

data Statement = 
      Expr Int
    | Block [Statement]
    | Return Int
    deriving (Show, Eq)

data Value = 
      Undefined
    | Value Int
    deriving (Show, Eq)

type NextStep = Value -> Value

evalStmt :: Statement -> NextStep -> Value
evalStmt (Expr val) next = 
    let res = Value val
    in next res
evalStmt (Block stmts) next = evalBlock stmts next
evalStmt (Return val) next = Value val

evalBlock :: [Statement] -> NextStep -> Value
evalBlock [] next = next Undefined
evalBlock [st] next = evalStmt st next
evalBlock (st:rest) next = evalStmt st $ \ _ -> evalBlock rest next

evalProgram stmts = evalBlock stmts id

prog1 = [Expr 1, Block [Return 3, Expr 2], Expr 4] 
evalProg1 = evalProgram prog1 -- result will be Value 3

Вопрос в том, как мне переписать этот код с монадой продолжения? Я хочу избавиться от явно переданного NextStep обратный звонок в evalStmt а также evalBlock функции. Является ли это возможным?

Answer 1

Перевод довольно механический.

Имейте в виду, что в продолжении монады, return подает значение в продолжение.

evalStmt :: Statement -> Cont Value Value
evalStmt (Expr val) = 
    let res = Value val
    in return res
evalStmt (Block stmts) = evalBlock stmts
evalStmt (Return val) = cont $ \_ -> Value val

evalBlock :: [Statement] -> Cont Value Value
evalBlock [] = return Undefined
evalBlock [st] = evalStmt st
evalBlock (st:rest) = evalStmt st >> evalBlock rest

evalProgram :: [Statement] -> Value
evalProgram stmts = runCont (evalBlock stmts) id

И чтобы симулировать ранние возвращения, мы просто игнорируем продолжение, данное Return val и просто вернуть значение, которое мы имеем.