了解 Julia 中没有基本情况的递归
Understanding recursion without base case in Julia
此代码段来自 Julia 中 Rational Numbers 的实现:
# Rational.jl
# ...
Rational{T<:Integer}(n::T, d::T) = Rational{T}(n,d)
Rational(n::Integer, d::Integer) = Rational(promote(n,d)...)
Rational(n::Integer) = Rational(n,one(n))
//(x::Rational, y::Integer) = x.num // (x.den*y) <--- HERE!
# ...
看看//
函数是如何实现的,然后用中缀表示法使用?这实际上如何 return 一个值?
当我看到这段代码时,我是这样解释的:
//
函数使用 Rational 和 Integer 调用。
- 但随后它进行了没有其他参数的递归调用。
#2 是让我很困惑的那个。数据结构中的递归在哪里结束?如果 //
return 值一直不求值,它如何计算值?
请帮助我理解这一点。
这是因为 Julia 最基本的功能之一:多重分派。在 Julia 中,函数可以有许多适用于参数类型的各种组合的方法,当你调用一个函数时,Julia 会调用与你调用它的所有参数类型匹配的最具体的方法。您发布的方法定义中的 //
调用定义了 rational-integer //
integer-integer //
- 所以它实际上不是递归的,因为该方法不会调用自身,它调用属于同一 "generic function".
的不同方法
要了解多重分派在这种情况下的工作原理,让我们考虑表达式 (3//4)//6
的求值。我们将使用 @which
宏来查看每个函数调用调用的方法。
julia> @which (3//4)//6
//(x::Rational{T<:Integer}, y::Integer) at rational.jl:25
因为 3//4
是一个 Rational{Int} <: Rational
而 6
是一个 Int <: Integer
,并且没有其他更具体的方法适用,所以这个方法被称为:
//(x::Rational, y::Integer) = x.num // (x.den*y)
该方法的 current version 实际上比您发布的方法稍微复杂一些,因为它已被修改以检查整数溢出 – 但它本质上是相同的,并且更容易理解旧版本,更简单的版本,所以我会用它。让我们将 x
和 y
分配给参数并查看定义调用的方法:
julia> x, y = (3//4), 6
(3//4,6)
julia> x.num
3
julia> x.den*y
24
julia> x.num // (x.den*y)
1//8
julia> @which x.num // (x.den*y)
//(n::Integer, d::Integer) at rational.jl:22
如您所见,这个表达式没有调用相同的方法,它调用了 different method:
//(n::Integer, d::Integer) = Rational(n,d)
此方法简单地调用 Rational
构造函数,它将 n
和 d
的比率放入最低项并创建一个 Rational
数字对象。
在 Julia 中,根据同一函数的另一种方法定义函数的一种方法是很常见的。例如,这就是参数默认值的工作方式。考虑这个定义:
julia> f(x, y=1) = 2x^y
f (generic function with 2 methods)
julia> methods(f)
# 2 methods for generic function "f":
f(x) at none:1
f(x, y) at none:1
julia> f(1)
2
julia> f(2)
4
julia> f(2,2)
8
默认参数语法仅生成第二个只有一个参数的方法,该方法使用默认值调用双参数形式。所以 f(x, y=1) = 2x^y
完全等同于定义两个方法,其中一元方法只是调用二元方法,为第二个参数提供默认值:
julia> f(x, y) = 2x^y
f (generic function with 1 method)
julia> f(x) = f(x, 1)
f (generic function with 2 methods)
此代码段来自 Julia 中 Rational Numbers 的实现:
# Rational.jl
# ...
Rational{T<:Integer}(n::T, d::T) = Rational{T}(n,d)
Rational(n::Integer, d::Integer) = Rational(promote(n,d)...)
Rational(n::Integer) = Rational(n,one(n))
//(x::Rational, y::Integer) = x.num // (x.den*y) <--- HERE!
# ...
看看//
函数是如何实现的,然后用中缀表示法使用?这实际上如何 return 一个值?
当我看到这段代码时,我是这样解释的:
//
函数使用 Rational 和 Integer 调用。- 但随后它进行了没有其他参数的递归调用。
#2 是让我很困惑的那个。数据结构中的递归在哪里结束?如果 //
return 值一直不求值,它如何计算值?
请帮助我理解这一点。
这是因为 Julia 最基本的功能之一:多重分派。在 Julia 中,函数可以有许多适用于参数类型的各种组合的方法,当你调用一个函数时,Julia 会调用与你调用它的所有参数类型匹配的最具体的方法。您发布的方法定义中的 //
调用定义了 rational-integer //
integer-integer //
- 所以它实际上不是递归的,因为该方法不会调用自身,它调用属于同一 "generic function".
要了解多重分派在这种情况下的工作原理,让我们考虑表达式 (3//4)//6
的求值。我们将使用 @which
宏来查看每个函数调用调用的方法。
julia> @which (3//4)//6
//(x::Rational{T<:Integer}, y::Integer) at rational.jl:25
因为 3//4
是一个 Rational{Int} <: Rational
而 6
是一个 Int <: Integer
,并且没有其他更具体的方法适用,所以这个方法被称为:
//(x::Rational, y::Integer) = x.num // (x.den*y)
该方法的 current version 实际上比您发布的方法稍微复杂一些,因为它已被修改以检查整数溢出 – 但它本质上是相同的,并且更容易理解旧版本,更简单的版本,所以我会用它。让我们将 x
和 y
分配给参数并查看定义调用的方法:
julia> x, y = (3//4), 6
(3//4,6)
julia> x.num
3
julia> x.den*y
24
julia> x.num // (x.den*y)
1//8
julia> @which x.num // (x.den*y)
//(n::Integer, d::Integer) at rational.jl:22
如您所见,这个表达式没有调用相同的方法,它调用了 different method:
//(n::Integer, d::Integer) = Rational(n,d)
此方法简单地调用 Rational
构造函数,它将 n
和 d
的比率放入最低项并创建一个 Rational
数字对象。
在 Julia 中,根据同一函数的另一种方法定义函数的一种方法是很常见的。例如,这就是参数默认值的工作方式。考虑这个定义:
julia> f(x, y=1) = 2x^y
f (generic function with 2 methods)
julia> methods(f)
# 2 methods for generic function "f":
f(x) at none:1
f(x, y) at none:1
julia> f(1)
2
julia> f(2)
4
julia> f(2,2)
8
默认参数语法仅生成第二个只有一个参数的方法,该方法使用默认值调用双参数形式。所以 f(x, y=1) = 2x^y
完全等同于定义两个方法,其中一元方法只是调用二元方法,为第二个参数提供默认值:
julia> f(x, y) = 2x^y
f (generic function with 1 method)
julia> f(x) = f(x, 1)
f (generic function with 2 methods)