《编程原本 》一2.1 变换

简介: 本节书摘来自华章出版社《编程原本 》一书中的第2章,第2.1节,作者(美)斯特潘诺夫(Stepanov, A.),(美)麦克琼斯(McJones, P.),更多章节内容可以访问云栖社区“华章计算机”公众号查看

2.1 变换

虽然从任意一组类型到任意类型的函数都存在,但是有些具有特殊签名的函数类更为常用.本书中经常用的是两类函数:同源谓词和同源运算.同源谓词在形式上都是Tו••× T → bool;同源运算都是形如Tו••× T → T的函数.一般而言存在着任意的n元谓词和n元运算,但实际中遇到最多的还是一元和二元的同源谓词,一元和二元的同源运算.
谓词是返回真值的函数:

Predicate(P).FunctionalProcedure(P)∧Codomain(P)=bool

同源谓词也是同源函数:

HomogeneousPredicate(P).
Predicate(P)∧HomogeneousFunction(P)

一元谓词只有一个参数:

UnaryPredicate(P).Predicate(P)∧UnaryFunction(P)

运算是同源函数,其值域与作用域相同:

Operation(Op).HomogeneousFunction(Op)∧Codomain(Op)=Domain(Op)

下面是几个同源运算的实例:

int abs(int x) { 
if (x < 0) return -x; else return x; 
} //一元运算
double euclidean norm(double x, double y) { 
return sqrt(x * x + y * y); 
} //二元运算
double euclidean norm(double x, double y, double z) { 
return sqrt(x * x + y * y + z * z); 
} //三元运算

引理2.1euclidean_norm(x,y,z)=euclidean_norm(euclidean_norm(x,y),z)
这一引理说明上面的三元运算可以从相应的二元版本得到.但是,由于效率,表达方便,或者准确性等原因,这样的三元运算也可以纳入处理三维空间的程序的计算基.

如果一个过程的定义空间是其输入类型的直积的子集,就称该过程为部分的(partial);如果其定义空间等于其输入类型的直积,则说它是全的.按标准的

数学习惯,我们也认为部分过程包括全过程,并称那些不是全的部分过程为非全的(nontotal).由于计算机表示的有穷性,有些全函数在计算机里的实现却是非全的.例如,有符号的32位整数加法就是非全的.

一个非全过程需要有一个描述其定义空间的前条件.要验证对这个过程的一个调用是正确的,必须确定所给的实参满足这一前条件.有时我们会把部分过程作为参数传给一个算法,因此需要在运行时确定这种过程参数的定义空间问题.为了处理这类情况,我们将定义一个定义空间谓词(de.nitionspacepredicate),它与这一过程参数的输入相同,当且仅当实际输入在这个过程的定义空间里时,让这个谓词返回真.在调用一个非全过程之前,或者其前条件必须满足,或者该调用是用这个过程的定义空间谓词保护的.

练习2.1请为32位有符号整数的加法实现一个定义空间谓词.
本章研究一元运算,我们称其为变换(transformation):

Transformation(F).
Operation(F)
∧UnaryFunction(F)
∧DistanceType:TransformationInteger
→

这里的DistanceType将在下一节讨论.
变换可以自组合(selfcomposable),例如可以写f(x),f(f(x)),f(f(f(x))),等等.f(f(x))的定义空间是f的定义空间和结果空间的交.这种自组合能力和检查相等能力的结合,使我们可以定义许多有趣的算法.
设f是一个变换,它的幂(power)定义如下:

.
.x if n = 0, fn(x)=. 
.fn.1(f(x))ifn>0
.

要实现计算fn(x)的算法,就要描述对一个整数类型的需求.第5章将研究描述与整数有关的一些概念,现在我们暂时依靠对整数的一些直观理解.有符号和无符号的整数类型都是整数的模型,还有任意精度的整数等,它们都包含下面的运算和文字量:
18 第2 章变换及其轨道
image

其中的I是一个整数类型.
这样就可以写出下面算法:

template requires(Transformation(F) && Integer(N)) Domain(F) power unary(Domain(F) x, N n, F f)
{
// 前条件: n . 0 ∧ (.i ∈ N) 0 while (n != N(0)) {n = n -N(1);x = f(x);
}
return x;
}

相关文章
|
6天前
|
存储 安全 编译器
C++学习过程中的一些值得注意的小点(1)
C++学习过程中的一些值得注意的小点(1)
|
6天前
|
Python
三点映射变换
【5月更文挑战第15天】三点映射变换。
6 1
|
6天前
|
算法
几何原本
几何原本
19 8
如何做一个俄罗斯方块3:形状控制
今天,我们来继续学习和实现下一个模块:玩家控制形状。在俄罗斯方块游戏中,玩家可以对下落的形状进行控制,控制分为两种,一种是控制形状的移动(左,右,下),一种是控制形状的旋转(顺时针旋转 90 度)。
104 0
|
程序员
程序员数学(22)–二次函数的图象与性质
本文目录 1. 定义 2. y=ax^2图象与性质 3. y=a(x-h)^2+k图象和性质 3.1 k值对图象的影响 3.2 h值对图象的影响 3.3 a值对图象的影响 4. y=ax^2+bx+c图象与性质 5. 二次函数与一元二次方程
245 0
程序员数学(22)–二次函数的图象与性质
|
Android开发
第二十一章:变换(十四)
3D-ish旋转 即使计算机屏幕是平面和二维的,也可以在这些屏幕上绘制视觉对象,使其具有第三维的外观。 在本章的前面,您看到了一些文本效果,它们提供了第三个维度的提示,而Xamarin.Forms支持两个额外的旋转,名为RotationX和RotationY,它们似乎也突破了屏幕固有的二维平面度。
1350 0
|
JavaScript Android开发 索引
第二十一章:变换(十二)
这两个问题都在非最小的BoxViewClock中得到解决。 XAML文件与MinimalBoxViewClock非常相似,但代码隐藏文件更为广泛。 它以名为HandParams的小结构开始,该结构定义每只手相对于半径的大小,但也包括偏移值。
1063 0
|
JavaScript Android开发
第二十一章:变换(十一)
模拟时钟用于图形用户界面的经典示例程序之一是模拟时钟。 BoxView再一次为时钟之手进行救援。 必须根据当前时间的小时,分钟和秒旋转这些BoxView元素。让我们首先使用名为AnalogClockViewModel的类来处理旋转数学,该类包含在Xamarin.
1071 0
|
Android开发 索引
第二十一章:变换(十)
样式通过将AnchorX值设置为0来结束,该值将旋转中心设置为每个Label的左边缘的垂直中心。 然后每个Label都会获得一个独特的旋转设置:显然,选择“ROTATE”字符串之前的空格,以便R的垂直条组合形成一个看起来几乎像圆的16边多边形。
1020 0
|
JavaScript Android开发 索引
第二十一章:变换(九)
旋转的文字效果轮换很有趣。 旋转动画时更有趣(正如您将在下一章中看到的那样),但即使使用静态图像也很有趣。本章和下一章中的几个旋转示例涉及将视觉元素排列在一个圆圈中,所以让我们首先尝试显示一个简单的圆圈。
846 0