如何返回带有防护和双重递归的 lambda？

Question

我用Python编写了这个函数：

def calc(a): return lambda op: {
    '+': lambda b: calc(a+b),
    '-': lambda b: calc(a-b),
    '=': a}[op]

所以你可以这样计算：

calc(1)("+")(1)("+")(10)("-")(7)("=")

结果将是5。

我想在 Haskell 中制作相同的函数来了解 lambda，但我遇到了解析错误。

我的代码如下所示：

calc :: Int -> (String -> Int)
calc a = \ op 
    | op == "+" = \ b calc a+b
    | op == "-" = \ b calc a+b
    | op == "=" = a

main = calc 1 "+" 1 "+" 10 "-" 7 "="

Answer 1

您发布的代码存在许多语法问题。不过，我不会在这里讨论它们：在完成基本的 Haskell 教程后，您会自己发现它们。相反，我将重点关注该项目的一个更基本的问题，即这些类型并不真正有效。然后我将展示一种不同的方法，让您获得相同的结果，向您展示一旦您了解了更多信息，在 Haskell 中这是可能的。

虽然在 Python 中有时返回 int 函数有时返回 int 是可以的，但在 Haskell 中这是不允许的。GHC 必须在编译时知道将返回什么类型；您无法在运行时根据字符串是否存在来做出决定"="。因此，“keep ing”参数需要calc与“给我答案”参数不同的类型。

这在 Haskell 中是可能的，事实上这是一种有很多应用程序的技术，但它可能不是初学者的最佳起点。你正在发明延续。您想要calc 1 plus 1 plus 10 minus 7 equals生成 5，用于其中使用的名称的某些定义。实现这一点需要 Haskell 语言的一些高级功能和一些有趣的类型¹，这就是为什么我说它不适合初学者。但是，下面是实现此目标的实现。我不会详细解释，因为有太多东西需要你先学习。希望在学习了 Haskell 基础知识之后，您可以回到这个有趣的问题并理解我的解决方案。

calc :: a -> (a -> r) -> r
calc x k = k x

equals :: a -> a
equals = id

lift2 :: (a -> a -> a) -> a -> a -> (a -> r) -> r
lift2 f x y = calc (f x y)

plus :: Num a => a -> a -> (a -> r) -> r
plus = lift2 (+)

minus :: Num a => a -> a -> (a -> r) -> r
minus = lift2 (-)

ghci> calc 1 plus 1 plus 10 minus 7 equals
5

¹当然calc 1 plus 1 plus 10 minus 7 equals看起来很像1 + 1 + 10 - 7，这非常简单。这里重要的区别是这些是中缀运算符，因此被解析为(((1 + 1) + 10) - 7)，而您尝试在 Python 中实现的版本以及我的 Haskell 解决方案被解析为((((((((calc 1) plus) 1) plus) 10) minus) 7) equals)- 没有偷偷摸摸的中缀运算符，并且calc可以控制所有组合。

Answer 2

我想说，这是一个简单的解决方案，它比其他答案中的高级解决方案更符合您的 Python 代码。这不是一种惯用的解决方案，因为就像 Python 一样，它将使用运行时失败而不是编译器中的类型。

\n

所以，Python 的本质是：返回一个函数或一个 int。在 Haskell 中，不可能根据运行时值返回不同的类型，但是可以返回包含不同数据（包括函数）的类型。

\n

data CalcResult = ContinCalc (Int -> String -> CalcResult)\n                | FinalResult Int\n\ncalc :: Int -> String -> CalcResult\ncalc a "+" = ContinCalc $ \\b -> calc (a+b)\ncalc a "-" = ContinCalc $ \\b -> calc (a-b)\ncalc a "=" = FinalResult a\n

\n

出于最终会变得清楚的原因，我实际上会提出以下变体，与典型的 Haskell 不同，它不是柯里化的：

\n

calc :: (Int, String) -> CalcResult\ncalc (a,"+") = ContinCalc $ \\b op -> calc (a+b,op)\ncalc (a,"-") = ContinCalc $ \\b op -> calc (a-b,op)\ncalc (a,"=") = FinalResult a\n

\n

现在，你不能只是在上面堆积函数应用程序，因为结果永远不仅仅是一个函数 \xe2\x80\x93 它只能是一个包装函数。因为应用的参数多于处理它们的函数似乎是失败的情况，所以结果应该在 monad 中Maybe。

\n

contin :: CalcResult -> (Int, String) -> Maybe CalcResult\ncontin (ContinCalc f) (i,op) = Just $ f i op\ncontin (FinalResult _) _ = Nothing\n

\n

为了打印最终结果，让我们定义

\n

printCalcRes :: Maybe CalcResult -> IO ()\nprintCalcRes (Just (FinalResult r)) = print r\nprintCalcRes (Just _) = fail "Calculation incomplete"\nprintCalcRes Nothing = fail "Applied too many arguments"\n

\n

现在我们可以做

\n

ghci> printCalcRes $ contin (calc (1,"+")) (2,"=")\n3\n

\n

好的，但是对于较长的计算来说这会变得非常尴尬。请注意，我们在两次操作 a 之后，Maybe CalcResult所以我们不能contin再次使用。另外，需要向外匹配的括号也很痛苦。

\n

幸运的是，Haskell 不是 Lisp，并且支持中缀运算符。而且因为我们无论如何都会得到Maybe结果，所以不妨将失败案例包含在数据类型中。

\n

那么，完整的解决方案是这样的：

\n

data CalcResult = ContinCalc ((Int,String) -> CalcResult)\n                | FinalResult Int\n                | TooManyArguments\n\ncalc :: (Int, String) -> CalcResult\ncalc (a,"+") = ContinCalc $ \\(b,op) -> calc (a+b,op)\ncalc (a,"-") = ContinCalc $ \\(b,op) -> calc (a-b,op)\ncalc (a,"=") = FinalResult a\n\ninfixl 9 #\n(#) :: CalcResult -> (Int, String) -> CalcResult\nContinCalc f # args = f args\n_ # _ = TooManyArguments\n\nprintCalcRes :: CalcResult -> IO ()\nprintCalcRes (FinalResult r) = print r\nprintCalcRes (ContinCalc _) = fail "Calculation incomplete"\nprintCalcRes TooManyArguments = fail "Applied too many arguments"\n

\n

这允许你写

\n

ghci> printCalcRes $ calc (1,"+") # (2,"+") # (3,"-") # (4,"=")\n2\n

\n

Answer 3

chi的回答说你可以用“复杂类型的机械”来做到这一点，就像printf做的那样。您可以这样做：

{-# LANGUAGE ExtendedDefaultRules #-}

class CalcType r where
    calc :: Integer -> String -> r

instance CalcType r => CalcType (Integer -> String -> r) where
    calc a op
        | op == "+" = \ b -> calc (a+b)
        | op == "-" = \ b -> calc (a-b)

instance CalcType Integer where
    calc a op
        | op == "=" = a

result :: Integer
result = calc 1 "+" 1 "+" 10 "-" 7 "="

main :: IO ()
main = print result

Maybe如果你想让它更安全，你可以用or消除偏向Either，如下所示：

{-# LANGUAGE ExtendedDefaultRules #-}

class CalcType r where
    calcImpl :: Either String Integer -> String -> r

instance CalcType r => CalcType (Integer -> String -> r) where
    calcImpl a op
        | op == "+" = \ b -> calcImpl (fmap (+ b) a)
        | op == "-" = \ b -> calcImpl (fmap (subtract b) a)
        | otherwise = \ b -> calcImpl (Left ("Invalid intermediate operator " ++ op))

instance CalcType (Either String Integer) where
    calcImpl a op
        | op == "=" = a
        | otherwise = Left ("Invalid final operator " ++ op)

calc :: CalcType r => Integer -> String -> r
calc = calcImpl . Right

result :: Either String Integer
result = calc 1 "+" 1 "+" 10 "-" 7 "="

main :: IO ()
main = print result

这是相当脆弱的，非常不建议用于生产用途，但无论如何它只是作为（最终？）学习的东西。