如何在 haskell 中计算带有柯里化参数的函数？

Question

我正在编写一个定义如下的表达式求值器：

eval :: LState -> Env -> Lexp -> (LState, Value)

其中LState是内存。 Env：Variable 和 Value.Lexp 的映射定义如下：

data Lexp = Lid Var | Lfuncall Lexp [Lexp]

（Lexp 还有更多内容，但其余的对解决我的问题没有用。

值定义如下：

data Value = Vnum Int
           | Vbool Bool
           | Vref Int
           | Vfun ((LState, Value) -> (LState, Value))

使用模式匹配，我编写了函数的第一部分：

eval s env (Lfuncall func (arg:args)) =

现在，我尝试使用foldl和lambda函数，但没有任何效果。

eval s env (Lfuncall func (arg:args)) =   let arg' = eval s env arg
        args' = map (eval s env) args
    in
        case eval s env func of
            (_, Vfun func') -> foldl func' arg' args'
            _ -> error "error"

但这不起作用，因为 func' 需要是

(LState, Value) -> (LState, Value) -> (LState, Value)

但它只是

(LState, Value) -> (LState, Value)

。 Lambdas 没有帮助我解决这个问题。

关于我应该尝试探索什么有什么提示或想法吗？

Answer 1

你走在正确的轨道上，但有左折叠。让我们仔细考虑一下我们要折叠什么功能。它需要一个

Value

，它应该（但不保证）是一个函数，以及一个将被评估的

Lexp

参数，并且应该返回一个

Value

（它将扮演下一个函数的角色，如果还有更多的争论）。所以，乍一看，类型就是：

folder :: Value -> Lexp -> Value

如果我们将

foldl

应用于此：

foldl folder :: Value -> [Lexp] -> Value

它采用初始函数和参数列表。

但这不处理状态部分。我们需要当前状态作为累加器的一部分，而不仅仅是当前函数，并且需要返回最终状态。这些争论并不来自于他们自己的状态。所以我们的类型是：

folder :: (LState, Value) -> Lexp -> (LState, Value)

折叠将是：

foldl folder :: (LState, Value) -> [Lexp] -> (LState, Value)

获取初始状态、初始函数、参数列表，并给出最终状态和最终结果。这加起来。所以现在我们需要做的就是用该签名编写文件夹，我将把它作为练习。

一些需要记住的事情。永远不要丢弃一个状态或使用它两次——这称为“线性”，它对于“状态计算”的想法非常重要。状态计算通常具有这种模式

 let (s1, x) = something s0
     (s2, y) = something s1
     (s3, z) = something s2
 in  (s3, something)

因此，我们将上一步的结果状态传递给下一步，返回最终的状态。

为了呼叫

eval

，

folder

必须有权访问

env

。您可以通过在

folder

子句中定义

where

来实现此目的：

eval s env (Lfuncall func args) = ...
    where
    folder :: (LState, Value) -> Lexp -> (LState, Value)
    folder (s0, Vfun f) argExp = -- use env freely here

我希望这有帮助。我故意对一些细节说得有点含糊，因为你真的需要用头撞它才能得到模式，如果有什么你需要进一步澄清的，请告诉我。