Haskell 表达式修复函数的流派

Question

所以我正在阅读 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

使用fix重写remainder，使其成为非递归的。

Answer 1

首先，修复的主要类型实际上是 (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.

Answer 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

Haskell 表达式修复函数的流派

Haskell school of expression fix function

haskell

recursion

types

infinite

fixpoint-combinators