最外部的评估策略如何评估功能的部分应用和咖喱函数的应用 [英] How does the outermost evaluation strategy evaluate partial application of a function and application of a curried function

问题描述

在Haskell编程

在计算表达式时，应以什么顺序执行归约?一种常见 称为最内在评估的策略是，始终选择最内在的Redex， 不含其他redex.如果最里面的redex不止一个，按照惯例，我们选择一个 从表达式最左侧的位置开始.

When evaluating an expression, in what order should the reductions be performed? One common strategy, known as innermost evaluation, is to always choose a redex that is innermost, in the sense that it contains no other redex. If there is more than one innermost redex, by convention we choose the one that begins at the leftmost position in the expression.

评估表达式的另一种常见策略是对最内层的评估，始终是 选择一个最外部的Redex，因为它不包含在其他Redex中.如果超过 然后像以前一样选择一个这样的redex，它从最左边的位置开始.不出所料， 这种评估策略称为最外部评估.

Another common strategy for evaluating an expression, dual to innermost evaluation, is to always choose a redex that is outermost, in the sense that it is contained in no other redex. If there is more than one such redex then as previously we choose that which begins at the leftmost position. Not surprisingly, this evaluation strategy is known as outermost evaluation.

在函数的部分应用中，例如mult(3)(4)，其中mult被定义为

In partial application of a function, for example, mult(3)(4), where mult is defined as

mult    ::  (Int,Int)   ->  Int
mult    (x,y)   =   x   *   y

最里面的评估将首先将mult(3)评估为\y->3*y，然后评估(\y->3*y)4. 最外面的评估如何评估mult(3)(4)?

innermost evaluation will first evaluate mult(3) as \y->3*y, and then evaluate (\y->3*y)4. How will outermost evaluation evaluate mult(3)(4)?

应用咖喱函数，例如mult'(3)(4)，其中

In application of a curried function, for example, mult'(3)(4), where

mult'   ::  Int ->  Int ->  Int
mult'   x   =   \y  ->  x   *   y

最里面的评估将首先将mult'(3)评估为\y->3*y，然后评估(\y->3*y)4. 最外面的评估如何评估mult'(3)(4)?

innermost evaluation will first evaluate mult'(3) as \y->3*y, and then evaluate (\y->3*y)4. How will outermost evaluation evaluate mult'(3)(4)?

推荐答案

唯一明智的解释方式:

mult :: (Int, Int) -> Int
mult (x,y) = x * y

在更大的问题中，

是作为一元函数，它接受一个元组类型为(Int, Int)的单个参数.因此，不能部分应用mult.特别地，mult(3)没有任何意义，因为3不是类型为(Int, Int)的元组.

in the context of your larger question is as an unary function that takes a single argument of tuple type (Int, Int). So, mult cannot be partially applied. In particular, mult(3) doesn't make any sense, because 3 is not a tuple of type (Int, Int).

因此，无论使用最外面的缩小还是最里面的缩小，在表达式中，mult (3,4)的缩小在Hutton的意义上都是相同的.这里只有一个redex/应用程序，mult到(3,4)的应用程序，并且最外面和最里面的减少都会给出减少:

As a result, the reduction of the expression mult (3,4) in the sense meant by Hutton is the same whether you use outermost or innermost reduction. There's only one redex/application here, the application of mult to (3,4), and both outermost and innermost reduction would give the reductions:

mult (3,4)
=>  3 * 4
=>  12

对于功能:

mult' :: Int -> Int -> Int
mult' x y = x * y

或等效地:

mult' = \x -> (\y -> x * y)

表达式mult' 3 4或等效地(mult' 3) 4的最内层归因为:

the expression mult' 3 4 or equivalently (mult' 3) 4 undergoes innermost reduction as:

(mult' 3) 4
= ((\x -> (\y -> x * y)) 3) 4
=> (\y -> 3 * y) 4
=> 3 * 4
=> 12

奇怪的是，最外面的减少以完全相同的方式进行:

Curiously, outermost reduction proceeds in exactly the same manner:

(mult' 3) 4
= ((\x -> (\y -> x * y)) 3) 4     -- (1)
=> (\y -> 3 * y) 4
=> 3 * 4
=> 12

这是因为第(1)行中的((\x -> \y -> x * y) 3)到4的应用程序虽然是最外层的应用程序，但它不是redex.它不能减少，因为要应用((\x -> \y -> x * y) 3)的东西不是lambda表达式. (这是将lambda表达式应用于参数的方法.)

That's because the application of ((\x -> \y -> x * y) 3) to 4 in line (1), while it's the outermost application, is not a redex. It can't be reduced, because the thing being applied ((\x -> \y -> x * y) 3) isn't a lambda expression. (It's an application of a lambda expression to an argument.)

因此，与首次出现相反，第(1)行中只有一个redex，并且最内部和最外部的还原策略选择相同的redex.

Therefore, contrary to first appearances, there's only one redex in line (1), and the innermost and outermost reduction strategies choose the same redex.

这篇关于最外部的评估策略如何评估功能的部分应用和咖喱函数的应用的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！