Haskell - 程序的结果

Question

我不久前开始学习 Haskell，在考试期间，我被要求回答如果调用成本函数会返回什么，但我不明白会发生哪些步骤。我再次参加考试，但我无法理解我应该如何解决此类程序。

如有任何帮助，我们将不胜感激!

cost = n(twice, inc, 3)
n(h,s,x) = if (x<1) then (h s x) else n(h, (h s), x-1)
inc x = x+1
twice n a = n (n a)

Answer 1

类型签名在这里确实有很大帮助。让我们从最简单的开始，inc :

inc :: Num a => a -> a
inc x = x + 1

这很容易推导，因为 + 1类型为Num a => a -> a ，您可以在 GHCi 中使用 :type (+1) 检查这一点。接下来我们看一下函数twice 。很明显 n传入的必须是一个函数，因为它适用于 a和n a 。因为它应用于n a和a ，这两个表达式必须具有相同的类型，并且 n必须只有一个参数，因此我们可以说 twice有类型

twice :: (a -> a) -> a -> a
twice n a = n (n a)

现在我们可以算出n 。它需要一个元组 (h, s, x)作为参数并被递归调用。 h必须是两个参数的函数，因为它应用于 s和x ，和s如果没有更多上下文，是未知的。 x必须同时是Num a => a和一个Ord a => a由于它与< 1一起使用和-1 ，所以我们可以将签名写为

n :: (Num a, Ord a) => (b -> a -> c, b, a) -> c
n (h, s, x) = if x < 1 then h s x else n (h, h s, x - 1)

请注意，我在这里删除了一些不必要的括号。最后我们可以算出cost的类型，这就是n的返回类型:

cost :: (Num a, Ord a) => a
cost = n (twice, inc, 3)

但是这会返回什么呢？对于初学者来说，它被重写为 n的定义，但带有 twice , inc ，和3替换为:

if 3 < 1
    then twice inc 3
    else n (twice, twice inc, 3 - 1)

显然3 < 1是假的，所以让我们减少 n (twice, twice inc, 3 - 1) :

if 2 < 1
    then twice (twice inc) 2
    else n (twice, twice (twice inc), 2 - 1)

同样的故事，2 < 1是假的，所以我们继续减少:

if 1 < 1
    then twice (twice (twice inc)) 1
    else n (twice, twice (twice (twice inc)), 1 - 1)

这一步没什么新意，再试一次:

if 0 < 1
    then twice (twice (twice (twice inc))) 0
    else n (twice, twice (twice (twice (twice inc))), 0 - 1)

这里有0 < 1 ，所以我们选择 twice (twice (twice (twice inc))) 2 的分支。要解决这个问题，只需插入 inc和0进入 twice 的定义:

twice (twice (twice (twice inc))) 0
           = twice (twice (twice (inc . inc))) 0
           = twice (twice (inc . inc . inc . inc)) 0
           = twice (inc . inc . inc . inc . inc . inc . inc . inc) 0
           = (inc.inc.inc.inc.inc.inc.inc.inc.inc.inc.inc.inc.inc.inc.inc.inc) 0
           = 16

现在我们不能再简化这个表达式了!所以整个减少链是

cost = n (twice, inc, 3)
     = if 3 < 1
           then twice inc 3
           else n (twice, twice inc, 3 - 1)
     = n (twice, twice inc, 2)
     = if 2 < 1
           then twice (twice inc) 2
           else n (twice, twice (twice inc), 2 - 1)
     = n (twice, twice (twice inc), 1)
     = if 1 < 1
           then twice (twice (twice inc)) 1
           else n (twice, twice (twice (twice inc)), 1 - 1)
     = n (twice, twice (twice (twice inc)), 0)
     = if 0 < 1
           then twice (twice (twice (twice inc))) 0
           else n (twice, twice (twice (twice (twice inc))), 0 - 1)
     = twice (twice (twice (twice inc))) 0
     = inc (inc 0)
     = inc (0 + 1)
     = (inc.inc.inc.inc.inc.inc.inc.inc.inc.inc.inc.inc.inc.inc.inc.inc) 0
     = 16

(为了保持可读性，我使用 twice f = f . f 而不是 twice f x = f (f x) ，但这些定义是等效的)