1940 年代的函数式编程：阶乘的简约实现
Functional Programming à la 1940s: Minimalistic Implementation of Factorial
我看了 John Hughes 的精彩演讲 Why Functional Programming Matters a couple of times and only recently decided to actually try implementing the "minimalist" version of booleans, integers, and of course factorial, as shown in the video。
我实施了 true、false、ifte、zero、one、two、iszero、decr 最后 fact here 如下：
-- boolean
true x y = x
false x y = y
ifte bool t e = bool t e
-- positive integers
three f x = f $ f $ f x
two f x = f $ f x
one f x = f x
zero f x = x
-- add and multiplication
add m n f x = m f $ n f x
mul m n f x = m (n f) x
-- is zero check
iszero n = n (\_ -> false) true
-- decrement
decr n =
n (\m f x -> f (m f zero))
zero
(\x->x)
zero
-- factorial
fact n =
ifte (iszero n)
one
(mul n (fact (decr n)))
问题
我测试了每个函数，除了 decr 和 fact 之外，它们都能完美地编译和运行。
尽管 John Hughes 在 6:37 承诺他的 decr 实现有效，但编译失败并出现以下错误：
error: Variable not in scope: incr
我不确定 incr 应该如何在 (\m f x -> f (m incr zero)) 中实现。
现在，如果我将它们定义为 incr = (+1) 并将 decr 的定义更改为以下内容，则 decr 可以编译并正常工作，但 fact 仍然会导致编译失败。
decr n =
n (\m f x -> f (m incr x))
zero
(\x->x)
zero'
在 decr 的定义中使用的 lambda (\m f x -> f (m incr zero)) 是否存在错误，或者 incr 是否应该有不同的定义？
更新
当我将 incr 定义为 incr n = (\f x -> f (n f x)) 时，decr n 工作正常，但 fact n 无法编译。这是错误消息的可读部分：
factorial.hs:30:1: error:
• Occurs check: cannot construct the infinite type:
...
| fact n =
| ^^^^^^^^...
...
factorial.hs:33:6: error:
• Occurs check: cannot construct the infinite type:
...
• In the third argument of ‘ifte’, namely ‘(mul n (fact (decr n)))’
In the expression: ifte (iszero n) one (mul n (fact (decr n)))
In an equation for ‘fact’:
fact n = ifte (iszero n) one (mul n (fact (decr n)))
...
| (mul n (fact (decr n)))
| ^^^^^^^^^^^^^^^^^^^^^
注意：完整的错误消息有几页那么长。
看起来你真的很接近
我可以向您展示如何在 JavaScript 中使用 Church's encodings，但在 Haskell 中不行，因为我不知道如何进行一些简单的组合器类型检查在 Haskell（下方 U）
因为JavaScript是严格求值的，谓词分支必须用lambda包起来
继续 运行 片段 – 我们计算 8!
const True = a => b =>
a ()
const False = a => b =>
b ()
const IsZero = n =>
n (x => False) (True)
const Succ = n =>
f => x => f (n (f) (x))
const Pred = n =>
f => x => n (g => h => h (g (f))) (u => x) (u => u)
const Mult = m => n =>
f => m (n (f))
const Add = m => n =>
m (Succ) (n)
const one = f => x =>
f (x)
const two =
Add (one) (one)
const four =
Add (two) (two)
const eight =
Add (four) (four)
const U = f => f (f)
const Fact = U (f => acc => n =>
IsZero (n)
(z => acc) // thunks used for predicate branches
(z => U (f) (Mult (acc) (n)) (Pred (n)))) (one)
const result =
Fact (eight)
// convert church numeral result to a JavaScript number
console.log ('8! =', result (x => x + 1) (0))
// 8! = 40320
如果你稍微作弊，你可以通过使用 JavaScript 的 ?: 三元运算符来实现假懒惰 – 我只是展示这个所以你可以看到 Fact更具可读性的形式；上面的实现使用 only lambdas
const IsZero = n =>
// cheat by returning JavaScript's true/false booleans
n (x => false) (true)
const Succ = n =>
f => x => f (n (f) (x))
const Pred = n =>
f => x => n (g => h => h (g (f))) (u => x) (u => u)
const Mult = m => n =>
f => m (n (f))
const Add = m => n =>
m (Succ) (n)
const one = f => x =>
f (x)
const two =
Add (one) (one)
const four =
Add (two) (two)
const eight =
Add (four) (four)
const U = f => f (f)
const Fact = U (f => acc => n =>
IsZero (n)
? acc // now we're sorta cheating using JavaScript's ternary here
: U (f) (Mult (acc) (n)) (Pred (n))) (one)
const result =
Fact (eight)
console.log ('8! =', result (x => x + 1) (0))
// 8! = 40320
首先，让我们尝试明确键入所有内容。天真地，所有这些东西都是在教会函数处理的某种类型上参数化的：
type Logical a = a -> a -> a
type Nat a = (a->a) -> a->a
-- boolean
true, false :: Logical a
true x y = x
false x y = y
ifte :: Logical a -> a -> a -> a
ifte = id
incr :: Nat a -> Nat a
incr n f = f . n f
-- integer “literals”
zero, one, two, three :: Nat a
three = incr two
two = incr one
one = incr zero
zero _ = id
-- addition and multiplication
add, mul :: Nat a -> Nat a -> Nat a
add m n f = m f . n f
mul m n f = m $ n f
-- zero check
isZero :: Nat a -> Logical a
isZero n = n (const false) true
...好的，这里我们 运行 进入第一个问题：
• Couldn't match expected type ‘Logical a’ with actual type ‘a’
‘a’ is a rigid type variable bound by
the type signature for:
isZero :: forall a. Nat a -> Logical a
at /tmp/wtmpf-file7834.hs:25:1-28
• In the expression: n (const false) true
问题是我们尝试使用 Nat-church-numbers 作为一个函数，而不是在结果 Logical 应该使用的基础 a 类型上，但在那些逻辑本身。 IE。实际上是
isZero :: Nat (Logical a) -> Logical a
decr 变得更糟 – 这不起作用：
decr :: Nat a -> Nat a
decr n = n (\m f x -> f (m incr x))
zero
id
zero
因为您正试图将数字用于 isZero 中的逻辑目的，这需要注入另一个 Nat 层，但也只是为了传递 on/incrementing。在传统的 Hindley-Milner 中，您需要决定其中之一，因此无法对其进行类型检查。
在现代 Haskell 中，您 可以 通过 使参数多态 :
来进行类型检查
{-# LANGUAGE RankNTypes, UnicodeSyntax #-}
decr :: (∀ α . Nat α) -> Nat a
为了避免携带量词，我们可以创建另一个同义词：
type ANat = ∀ α . Nat α
那就是
decr :: ANat -> Nat a
该技术也适用于阶乘：
fact :: ANat -> Nat a
fact n = ifte (isZero n)
one
(mul n $ fact (decr n))
我看了 John Hughes 的精彩演讲 Why Functional Programming Matters a couple of times and only recently decided to actually try implementing the "minimalist" version of booleans, integers, and of course factorial, as shown in the video。
我实施了 true、false、ifte、zero、one、two、iszero、decr 最后 fact here 如下：
-- boolean
true x y = x
false x y = y
ifte bool t e = bool t e
-- positive integers
three f x = f $ f $ f x
two f x = f $ f x
one f x = f x
zero f x = x
-- add and multiplication
add m n f x = m f $ n f x
mul m n f x = m (n f) x
-- is zero check
iszero n = n (\_ -> false) true
-- decrement
decr n =
n (\m f x -> f (m f zero))
zero
(\x->x)
zero
-- factorial
fact n =
ifte (iszero n)
one
(mul n (fact (decr n)))
问题
我测试了每个函数，除了 decr 和 fact 之外，它们都能完美地编译和运行。
尽管 John Hughes 在 6:37 承诺他的 decr 实现有效，但编译失败并出现以下错误：
error: Variable not in scope: incr
我不确定 incr 应该如何在 (\m f x -> f (m incr zero)) 中实现。
现在，如果我将它们定义为 incr = (+1) 并将 decr 的定义更改为以下内容，则 decr 可以编译并正常工作，但 fact 仍然会导致编译失败。
decr n =
n (\m f x -> f (m incr x))
zero
(\x->x)
zero'
在 decr 的定义中使用的 lambda (\m f x -> f (m incr zero)) 是否存在错误，或者 incr 是否应该有不同的定义？
更新
当我将 incr 定义为 incr n = (\f x -> f (n f x)) 时，decr n 工作正常，但 fact n 无法编译。这是错误消息的可读部分：
factorial.hs:30:1: error: • Occurs check: cannot construct the infinite type:
...
| fact n =
| ^^^^^^^^......
factorial.hs:33:6: error: • Occurs check: cannot construct the infinite type:
...
• In the third argument of ‘ifte’, namely ‘(mul n (fact (decr n)))’ In the expression: ifte (iszero n) one (mul n (fact (decr n))) In an equation for ‘fact’: fact n = ifte (iszero n) one (mul n (fact (decr n)))...
| (mul n (fact (decr n)))
| ^^^^^^^^^^^^^^^^^^^^^
注意：完整的错误消息有几页那么长。
看起来你真的很接近
我可以向您展示如何在 JavaScript 中使用 Church's encodings，但在 Haskell 中不行，因为我不知道如何进行一些简单的组合器类型检查在 Haskell（下方 U）
因为JavaScript是严格求值的，谓词分支必须用lambda包起来
继续 运行 片段 – 我们计算 8!
const True = a => b =>
a ()
const False = a => b =>
b ()
const IsZero = n =>
n (x => False) (True)
const Succ = n =>
f => x => f (n (f) (x))
const Pred = n =>
f => x => n (g => h => h (g (f))) (u => x) (u => u)
const Mult = m => n =>
f => m (n (f))
const Add = m => n =>
m (Succ) (n)
const one = f => x =>
f (x)
const two =
Add (one) (one)
const four =
Add (two) (two)
const eight =
Add (four) (four)
const U = f => f (f)
const Fact = U (f => acc => n =>
IsZero (n)
(z => acc) // thunks used for predicate branches
(z => U (f) (Mult (acc) (n)) (Pred (n)))) (one)
const result =
Fact (eight)
// convert church numeral result to a JavaScript number
console.log ('8! =', result (x => x + 1) (0))
// 8! = 40320
如果你稍微作弊，你可以通过使用 JavaScript 的 ?: 三元运算符来实现假懒惰 – 我只是展示这个所以你可以看到 Fact更具可读性的形式；上面的实现使用 only lambdas
const IsZero = n =>
// cheat by returning JavaScript's true/false booleans
n (x => false) (true)
const Succ = n =>
f => x => f (n (f) (x))
const Pred = n =>
f => x => n (g => h => h (g (f))) (u => x) (u => u)
const Mult = m => n =>
f => m (n (f))
const Add = m => n =>
m (Succ) (n)
const one = f => x =>
f (x)
const two =
Add (one) (one)
const four =
Add (two) (two)
const eight =
Add (four) (four)
const U = f => f (f)
const Fact = U (f => acc => n =>
IsZero (n)
? acc // now we're sorta cheating using JavaScript's ternary here
: U (f) (Mult (acc) (n)) (Pred (n))) (one)
const result =
Fact (eight)
console.log ('8! =', result (x => x + 1) (0))
// 8! = 40320
首先，让我们尝试明确键入所有内容。天真地，所有这些东西都是在教会函数处理的某种类型上参数化的：
type Logical a = a -> a -> a
type Nat a = (a->a) -> a->a
-- boolean
true, false :: Logical a
true x y = x
false x y = y
ifte :: Logical a -> a -> a -> a
ifte = id
incr :: Nat a -> Nat a
incr n f = f . n f
-- integer “literals”
zero, one, two, three :: Nat a
three = incr two
two = incr one
one = incr zero
zero _ = id
-- addition and multiplication
add, mul :: Nat a -> Nat a -> Nat a
add m n f = m f . n f
mul m n f = m $ n f
-- zero check
isZero :: Nat a -> Logical a
isZero n = n (const false) true
...好的，这里我们 运行 进入第一个问题：
• Couldn't match expected type ‘Logical a’ with actual type ‘a’
‘a’ is a rigid type variable bound by
the type signature for:
isZero :: forall a. Nat a -> Logical a
at /tmp/wtmpf-file7834.hs:25:1-28
• In the expression: n (const false) true
问题是我们尝试使用 Nat-church-numbers 作为一个函数，而不是在结果 Logical 应该使用的基础 a 类型上，但在那些逻辑本身。 IE。实际上是
isZero :: Nat (Logical a) -> Logical a
decr 变得更糟 – 这不起作用：
decr :: Nat a -> Nat a
decr n = n (\m f x -> f (m incr x))
zero
id
zero
因为您正试图将数字用于 isZero 中的逻辑目的，这需要注入另一个 Nat 层，但也只是为了传递 on/incrementing。在传统的 Hindley-Milner 中，您需要决定其中之一，因此无法对其进行类型检查。
在现代 Haskell 中，您 可以 通过 使参数多态 :
来进行类型检查{-# LANGUAGE RankNTypes, UnicodeSyntax #-}
decr :: (∀ α . Nat α) -> Nat a
为了避免携带量词，我们可以创建另一个同义词：
type ANat = ∀ α . Nat α
那就是
decr :: ANat -> Nat a
该技术也适用于阶乘：
fact :: ANat -> Nat a
fact n = ifte (isZero n)
one
(mul n $ fact (decr n))