haskell 归约规则

dw1jzc5e  于 2023-10-19  发布在  其他
关注(0)|答案(2)|浏览(117)

如何在Haskell中将lengthGT4 $ produce id 1简化为True

lengthGT4 :: List a -> Bool
lengthGT4 (_ :. _ :. _ :. _ :. _ :. _) = True
lengthGT4 (_ :. _) = False    -- deliberately doing this

produce :: (a -> a) -> a -> List a
produce f i = i :. produce f (f i)

lengthGT4 $ produce id 1

$将右语句作为左首参数。
1.在减少,当$采取右手向左匹配?为什么右边的product不会无限扩展,也不会阻止$的取和匹配?
1.为什么下面的not jump不匹配lengthGT4 (_ :. _) = False,结果是False?而here jump out匹配lengthGT4 (_ :. _ :. _ :. _ :. _ :. _) = True,结果是True

lengthGT4 $ 1 :. (produce id 1)  -- not jump
lengthGT4 $ 1 :. 1:. (produce id 1)
lengthGT4 $ 1 :. 1:. 1:. (produce id 1)
lengthGT4 $ 1 :. 1:. 1:. 1:. (produce id 1)  -- here jump out

来自fp-course https://github.com/Nero5023/fp-course-solution/blob/f95a1a8c1b95dbe63015168f4fe4388854cd4a32/src/Course/List.hs#L280

fcipmucu

fcipmucu1#

1.在减少,当$采取右手向左匹配?为什么右边的product不会无限扩展,也不会阻止$的取和匹配?
你可以假设表达式e1 $ e2中的$在减少之前不计算表达式e1e2。实际上,e1 $ e2简化为函数应用程序e1 e2,然后将计算函数e1并将其应用于 * 未计算的 * 表达式e2
请注意,函数e1决定了e2的计算量。懒惰就是这样的。例如,take 3 (1:2:3:4:error "urk")不计算error,因此程序不会崩溃,并计算为[1,2,3]。相比之下,take 7 (1:2:3:4:error "urk")确实会崩溃。
在您的示例中,produce id 1不会被$计算。相反,它是根据lengthGT4进行评估的,并且只需要匹配或反驳模式。因此,它永远不会被完全计算为无限列表(这将使程序永远运行)。
1.为什么下面的not jump不匹配lengthGT4 (_ :. _) = False,结果是False?而here jump out匹配lengthGT4 (_ :. _ :. _ :. _ :. _ :. _) = True,结果是True
模式是按顺序从上到下尝试的。实际上,一个像

f pat1 = exp1
f pat2 = exp2
...

用伪代码表示:

Take the input argument of f.
Evaluate the input as much as needed to match or refute pat1.
if it's a match then
   Bind variables of pat1 to the corresponding values.
   Evaluate exp1 and return the result.
else
   Evaluate the input as much as needed to match or refute pat2.
   if it's a match then
      Bind variables of pat2 to the corresponding values.
      Evaluate exp2 and return the result.
   else
      ...

在您的特定情况下,lengthGT4 (_ :. _) = False中的模式不会被考虑,直到lengthGT4 (_ :. _ :. _ :. _ :. _ :. _) = True中的模式被驳回。但是对于输入produce id 1,这并没有被反驳,因为它可以计算出一个至少有5个元素的列表。

rkue9o1l

rkue9o1l2#

由于列表的工作方式,produce id 1创建的无限列表1 : 1 : 1 : 1 : 1 : ...等效于四项cons 1 : 1 : 1 : [1 : 1 : 1 : ...] AND两项cons 1 : [1 : 1 : 1 : ...]
由于这两种情况是等效的,所以第一个匹配的情况是代码采用的分支。如果你颠倒顺序:

lengthGT4' :: [a] -> Bool
lengthGT4' (_ : _) = False
lengthGT4' (_ : _ : _ : _ : _ : _) = True

你会得到警告的

Pattern match is redundant
    In an equation for ‘lengthGT4'’:
        lengthGT4' (_ : _ : _ : _ : _ : _) = ...

但该表达式的计算结果为False。
也许更简单的方式来思考它是简单的:produce id 1将始终生成一个无限列表,并且无限列表的长度大于4。

相关问题