haskell - 让 Haskell 势在必行

Question

注意:这是一个练习，我试图了解事情是如何运作的。

我正在努力使在 Haskell 中做这样的事情成为可能:

f :: Integer -> Integer
f n = def $ do
  i      <- var n
  while i (>0) $ do
    i      -= lit 1
  return i
-- for now, my program returns n 

下面是我的程序。在这一点上，我不明白为什么它不起作用，但出于某种原因，变量没有改变。

import Control.Monad.State


data Lit a = Lit a
type Variable a = State Integer a


def :: Variable (Lit a) -> a
def (State f) = fromLit . fst . f $ 0 

fromLit :: Lit a -> a
fromLit (Lit a) = a

lit :: a -> Lit a
lit l = Lit l

var :: a -> Variable (Lit a)
var v = State $ \x -> (lit v, x)

while :: Lit a -> (a -> Bool) -> Variable () -> Variable ()
while (Lit r) cond act = do
                 if cond r then do
                          _ <- act
                          while (Lit r) cond act
                    -- or act >> while (Lit r) cond act
                 else return ()


op :: (Integer -> Integer -> Integer) -> Lit Integer -> Lit Integer -> Variable ()
op f (Lit a) (Lit b) = State $ \n -> ((), if n == a then f a b else n)
-- that is, if the state is (a) change it to (f a b), else don't change it

(+=) = op (+)
(-=) = op (-)
(*=) = op (*)

请帮助我了解这里有什么问题以及如何改进代码。谢谢。

Answer 1

不用说，这在 Haskell 中是一件愚蠢的事情；但我完全赞成尝试一些愚蠢的事情，只要它能帮助你学到一些东西。

我认为在尝试像这样复杂的问题之前，您可能应该退回到一个更简单的问题并多尝试使用 State monad；根据您发布的代码片段，我怀疑您的直觉有点偏差。

你当然可以做这种事情，但是在 State monad 中处理“任意”类型的变量是很棘手的(它必须有一个固定的状态类型)。您可以使用 Dynamic 和 Proxy 以相对类型安全的方式完成此操作；但我认为这可能仍然有点遥不可及。

我们将从存储 Int 类型的变量开始。我不确定您使用的是哪个 State monad，但我会改用 mtl 中的那个。

import Control.Monad.State
import qualified Data.Map as M
import Data.Maybe

data Var = Var Int
  deriving (Show, Eq, Ord)

data Env = Env {freshVar :: Int, vars :: M.Map Var Int}
  deriving Show

type Imperative a = State Env a

我已经定义了 Env 类型，它跟踪我们“创建”的所有变量，以及一个“新名称”生成器，它只是一个不断向上计数的 Int正如我们定义变量一样。

lit :: Int -> Imperative Var
lit n = do
    varID <- gets freshVar
    let newVar = Var varID
    modify (\s -> s{freshVar=n+1, vars=(M.insert newVar n (vars s))})
    return newVar

这段代码从文字数字创建一个新的“变量”，它通过从环境中获取一个新的变量名，将其包装在构造函数中，然后将其与提供的值一起存储在环境中来实现。请注意，我们增加了 freshVar 编号，因此我们将为下一个文字获得不同的变量 ID。

getVar :: Var -> Imperative Int
getVar v = gets (fromJust . M.lookup v . vars)

setVar :: Var -> Int -> Imperative ()
setVar v n = modify (\s -> s{vars=M.insert v n (vars s)})

这些是一些帮助程序，它们在我们的变量映射中查找变量或设置变量。 getVar 使用 fromJust 通常是不安全的；但是如果你只用“lit”定义新变量那么它工作正常。

op :: (Int -> Int -> Int) -> Var -> Var -> Imperative ()
op f aVar bVar = do
    a <- getVar aVar
    b <- getVar bVar
    setVar aVar (f a b)

(+=) = op (+)
(-=) = op (-)
(*=) = op (*)

为了执行您版本的变异操作，我们采用两个变量，查找它们的当前值，执行操作，然后将结果存储到左侧的变量中。

现在我们可以定义while

while :: Imperative Bool -> Imperative () -> Imperative ()
while cond act = do
    continue <- cond
    if continue then act >> while cond act
                else return ()

我们可以接受任何返回 bool 值的命令式语句作为条件；如果需要，用户可以在语句中查找变量的状态。我们简单地运行语句，如果我们想继续我们act然后递归，否则我们返回。

f :: Int -> Int
f n = run $ do
  i <- lit n
  while ((>0) <$> getVar i) $ do
    one <- lit 1
    i -= one
  getVar i

它有点冗长(我们可以简化它，但它会使组合器更复杂)。我们将 i 定义为一个值为 n 的新变量，然后在条件中检查它是否大于 0。在循环体中，我们定义了一个值为 1 的变量，然后从变量 i 中减去它。

循环结束后我们检查i

的值

run :: Imperative a -> a
run m = evalState m (Env 0 M.empty)

这是我们上面使用的 run 函数，它只是运行没有定义变量的状态。

如果您尝试一下，您会发现它成功地归零；你可以添加一个跟踪语句来查看它命中了哪些值:

import Debug.Trace
f :: Int -> Int
f n = run $ do
  i <- lit n
  while ((>0) <$> getVar i) $ do
    getVar i >>= traceShowM
    one <- lit 1
    i -= one
  getVar i

>>> f 10
10
9
8
7
6
5
4
3
2
1
0