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必须是a Num a => 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)

请注意,我在这里删除了一些不必要的parens.最后,我们可以弄清楚它的类型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),但这些定义是等价的)