1

所以我正在阅读 Paul Hudak 的书“The Haskell School of Expression”，并在那里进行了一项练习。

来了

假设函数 fix 定义为 

fix f = f (fix f)

主要类型是fix什么？我认识的那个是b -> b -> b

但是我不明白定义的方式fix，它不会进入无限递归吗？

另外，让remainder函数定义为 

remainder :: Integer -> Integer -> Integer
remainder a b = if a < b then a 
                else remainder (a - b) b

重写remainderusingfix使其不递归。

4

2 回答 2

3

首先，修复的主要类型实际上是(b -> b) -> b（请记住，仅b -> (b -> b)与 相同b -> b -> b）。

在严格的语言中，这样的定义会进入无限递归，但因为 Haskell 是惰性的，函数的参数只有在需要时才会被评估。例如，您可以定义factorial.

-- with recursion
factorial :: Int -> Int
factorial n = if n == 0 then 1 else n * factorial (n-1)

-- with `fix`
factorial' :: Int -> Int
factorial' = fix (\f n -> if n == 0 then 1 else n * f (n - 1))

按照相同的模式，您应该能够定义remainder.

于 2016-11-19T17:04:34.047 回答
2

玩它一点给我们

fix f         = f (fix f)                                            -- definition
fix f     a   = f (fix f) a                                          -- eta expansion
fix f     a b = f (fix f) a b                                        -- eta expansion
remainder a b = if a < b then a else remainder (a - b) b             -- definition
-- we want  remainder = fix f:                                       -- equation
fix f     a b = if a < b then a else (fix f)   (a - b) b             -- substitution
       = (\g -> if a < b then a else g         (a - b) b) (fix f)    -- abstraction
   = fix (\g -> \a b -> if a < b then a else g (a - b) b) a b        -- abstraction

因此

remainder = 
     fix (\g     a b -> if a < b then a else g (a - b) b)            -- eta reduction
于 2016-11-19T19:28:09.907 回答