2

我正在为大学课程学习 Haskell，我有一个关于可简化表达式（redexes）的问题。我理解这个概念，但我仍然有一些我自己似乎无法弄清楚的问题。

假设您希望找到表达式中的所有可约表达式，如下所示：

head (map (+1) (3:repeat 3))

在这个表达式中，一个明显的 redex 将是map (+1) (3:repeat 3))因为它与 的定义匹配map，所以 Haskell 将“减少”表达式并map增加3and 4:map (+1) (repeat 3)。接下来会减少。

我的问题是：

已经是head (map (+1) (3:repeat 3))一个redex，之前map被评估过吗？

因为“输入”的“输入”head与列表的构造函数不匹配（这是head正在寻找的），所以我对它是否仍然是 redex 感到困惑，因为从逻辑上讲它还不能减少，但网上的定义似乎是说会的。

4

1 回答 1

3

Haskell 的评估是懒惰的：它通过最左边的redex 策略进行（至少在概念上）：它减少最左边的 redex 中的最左边。

大概head定义为

head xs = case xs of (x:_) -> x

那么它对任何表达式的应用确实是一个redex——一个需要归约的表达式。根据 的定义进行head，

head (map (+1) (3:repeat 3))
=
case (map (+1) (3:repeat 3)) of (x:_) -> x
=

（或者我们可以说它head本身是最左上角的 redex，它首先简化为它的定义；如果我们写上面的内容，((\xs -> case xs of (x:_) -> x) (map (+1) (3:repeat 3)))我们会得到相同的结果，只是有点乏味）。

一个主要的强制原语是case. 现在它需要执行模式匹配，因此它必须找出其检查表达式的值（仅在模式匹配成为可能的范围内）。要做到这一点，它现在必须根据其定义工作map，大概是

map f xs = case xs of { (x:ys) -> f x : map f ys
                      ; [] -> [] }

所以它变成

case (map (+1) (3:repeat 3)) of (x:_) -> x
=
case (case (3:repeat 3) of 
         { (x:ys      ) -> (+1) x : map (+1) ys
                   ; [] -> [] } )
                             of (x:_) -> x
=

此时可以减少内心的case表达，

case (let { x=3 ; ys=repeat 3} in 
        (+1) x : map (+1) ys )
  of (x        : _                  ) -> x
=

现在outer case的模式匹配成为可能，

case (let { x=3 } in 
        (+1) x               )
  of (x                             ) -> x
=
      let { x=3 } in 
        (+1) x 
=
        (+1) 3 
=
        4
于 2022-02-21T15:17:17.957 回答