Using Just and Nothing Haskell

Question

我正在实现一个lambda演算解释器，我必须编写的函数之一如下所示。我已经编写了所有其他函数，但这一个函数真的给我带来了麻烦，因为它需要返回Just Expr或Nothing，我不知道如何通过递归来实现这一点：

---

一个步骤。现在编写一个函数来完成一个简化步骤：

appNF_OneStep:：Expr->也许Expr

其中内置的Maybe类型定义如下：

数据也许=没有什么|只是

appNF_OneStep采用表达式e。如果e中有可用的redex，它会选择正确的应用程序顺序redex和减少e。(注意，在应用顺序中，我们追求的是最左边、最里面的策略如下所示。选取最左边的redex R；如果在R内有嵌套(内部(的redex，等等，直到我们达到一个没有嵌套的redex。(如果进行了减少，导致new表达式expr'，appNF_OneStep返回Just-expr'，否则返回Nothing。

例如输入/输出：
输入：应用程序/>输入：Lambda"；y"；(Lambda"x"(Var"x"(
正确输出：无

可以看出，只执行了一次还原的整个表达式被包裹在Just中。

Answer 1

我将提供一些提示。

您需要执行递归调用，并检查它们的结果是Nothing还是Just something。你的代码的这一部分看起来还可以：

appNF_OneStep (App e1 e2) =
let f = appNF_OneStep e1
a = appNF_OneStep e2
in

让我们从那里继续。有四种可能的情况：

appNF_OneStep (App e1 e2) =
let f = appNF_OneStep e1
a = appNF_OneStep e2
in case (f, a) of
(Nothing, Nothing) -> ??? -- case 1
(Nothing, Just a') -> ??? -- case 2
(Just f', Nothing) -> ??? -- case 3
(Just f', Just a') -> ??? -- case 4

在情况1中，e1和e2都不能被减少。我们能减少他们的申请吗？怎样

在情况2中，e1不能被减少，但是e2可以(到a'(。我们能减少他们的申请吗？怎样

等等。如果你发现其中一些情况相似并且可以分组，你可能不需要考虑所有四种情况。尽管如此，我还是建议你从检查所有四个案例开始，了解发生了什么

代码的其余部分有一些问题：

appNF_OneStep::Expr -> Maybe Expr
appNF_OneStep (Var x) = (Var x)

这里的结果(Var x)是Expr，而不是Maybe Expr，因此它具有错误的类型。我们可以将其修复为Just (Var x)。这真的是正确的结果吗？我们真的知道一个变量可以进行一个归约步骤，从而产生它自己吗？

类似地，

appNF_OneStep (Lambda x ex) = (Lambda x (appNFOneStep ex))

返回错误的类型Expr而不是Maybe Expr。最重要的是，Lambda期望Expr作为第二个参数，但递归调用是Maybe Expr，所以这不行

appNF_OneStep (Lambda x ex) = case appNFOneStep ex of
Nothing -> ???
Just a  -> ???

一旦你熟练地使用Haskell，你就可以用fmap这样的助手来替换一些无聊的代码，但不必着急。首先，试着学习模式匹配和代数类型的基础知识。