4 个版本 (2 个破坏性更改)
| 0.3.0 | 2020 年 2 月 24 日 |
|---|---|
| 0.2.0 | 2020 年 2 月 23 日 |
| 0.1.1 | 2019 年 8 月 19 日 |
| 0.1.0 | 2019 年 8 月 19 日 |
#1 in #higher
用于 2 crates
23KB
158 行
高阶核心
此包包含用于使用高阶数据结构的核心结构和特征。
高阶数据结构简介
高阶数据结构是普通数据结构的一般化。
在普通数据结构中，编程的默认方式是
- 使用数据结构存储数据
- 使用方法/函数对数据进行操作
在高阶数据结构中，数据和函数成为同一件事。
高阶数据结构的核心思想是属性可以是相同类型的函数。
例如，一个 Point 有一个 x、y 和 z 属性。在普通编程中，x、y 和 z 可能是类型 f64。
如果 x、y 和 z 是从 T -> f64 的函数，那么点类型是 Point<T>。
可以像函数一样调用高阶 Point<T>。当作为函数调用时，Point<T> 返回 Point。
然而，与函数不同，您仍然可以访问 Point<T> 的属性。您还可以为 Point<T> 定义方法和重载运算符。这意味着在高阶数据结构中，数据和函数成为同一件事。
使用高阶数据结构编程的动机
高阶数据结构的主要应用是几何学。
典型的用法是例如为游戏创建程序生成的内容。
高阶数据结构是关于在各种通用算法中寻找隐藏实现细节和暴露它们之间的平衡。
例如，一个圆可以被视为具有类型 Point<f64>。参数可以是一个弧度角，或者单位区间 [0, 1] 中的值。
另一个例子，一条线可以被视为具有类型 Point<f64>。参数是单位区间 [0, 1] 中的值。当调用 0 时，你得到线的起点。当调用 1 时，你得到线的终点。
与其声明一个 Circle 类型、一个 Line 类型等等，不如使用 Point<f64> 来表示它们。
高阶数据结构使得编写几何通用算法变得更加容易。尽管一开始看起来很抽象，但它也在一些意想不到的情况下非常有用。
例如，一个动画点可以被视为具有类型 Point<(&[Frame], f64)>。第一个参数包含动画数据，第二个参数是秒数。动画点的属性 x、y 和 z 决定了动画点的计算方式。可以使用动画点实现的细节可以隐藏在使用动画点的算法中。
有时你需要处理复杂的几何。在这些情况下，使用高阶数据结构更容易。
例如，一个行星可能有一个中心、赤道、两极、表面等。一个行星围绕一个恒星运行，而恒星又围绕星系中心运行。这意味着从不同的参考系来看，行星的属性是确定参考系的参数的函数。你可以创建一个“高阶行星”来讨论在不同参考系下行星的属性。
设计
以下是如何声明一个新的高阶数据结构的示例
use higher_order_core::{Ho, Call, Arg, Fun, Func};
use std::sync::Arc;
/// Higher order 3D point.
#[derive(Clone)]
pub struct Point<T = ()> where f64: Ho<T> {
/// Function for x-coordinates.
pub x: Fun<T, f64>,
/// Function for y-coordinates.
pub y: Fun<T, f64>,
/// Function for z-coordinates.
pub z: Fun<T, f64>,
}
// It is common to declare a type alias for functions, e.g:
pub type PointFunc<T> = Point<Arg<T>>;
// Implement `Ho<Arg<T>>` to allow higher order data structures
// using properties `Fun<T, Point>` (`<Point as Ho<T>>::Fun`).
impl<T: Clone> Ho<Arg<T>> for Point {
type Fun = PointFunc<T>;
}
// Implement `Call<T>` to allow higher order calls.
impl<T: Copy> Call<T> for Point
where f64: Ho<Arg<T>> + Call<T>
{
fn call(f: &Self::Fun, val: T) -> Point {
Point::<()> {
x: <f64 as Call<T>>::call(&f.x, val),
y: <f64 as Call<T>>::call(&f.y, val),
z: <f64 as Call<T>>::call(&f.z, val),
}
}
}
impl<T> PointFunc<T> {
/// Helper method for calling value.
pub fn call(&self, val: T) -> Point where T: Copy {
<Point as Call<T>>::call(self, val)
}
}
// Operations are usually defined as simple traits.
// They look exactly the same as for normal generic programming.
/// Dot operator.
pub trait Dot<Rhs = Self> {
/// The output type.
type Output;
/// Returns the dot product.
fn dot(self, other: Rhs) -> Self::Output;
}
// Implement operator once for the ordinary case.
impl Dot for Point {
type Output = f64;
fn dot(self, other: Self) -> f64 {
self.x * other.x +
self.y * other.y +
self.z * other.z
}
}
// Implement operator once for the higher order case.
impl<T: 'static + Copy> Dot for PointFunc<T> {
type Output = Func<T, f64>;
fn dot(self, other: Self) -> Func<T, f64> {
let ax = self.x;
let ay = self.y;
let az = self.z;
let bx = other.x;
let by = other.y;
let bz = other.z;
Arc::new(move |a| ax(a) * bx(a) + ay(a) * by(a) + az(a) * bz(a))
}
}
为了区分例如 Point<()> 的实现和 Point<T>，使用参数类型 Arg<T> 用于点函数： Point<Arg<T>>。
对于每个高阶类型 U 和参数类型 T，都有一个关联的函数类型 T -> U。
对于原始类型，例如 f64，函数类型是 Func<T, f64>。
对于高阶结构体，例如 X<()>，函数类型是 X<Arg<T>>。
对高阶数据结构上的运算符的代码必须写两次
- 一次用于普通情况
X<()> - 一次用于高阶情况
X<Arg<T>>
高阶映射
有时构建任意类型的数据很有用
- 原始类型的向量
- 向量的向量等。
例如，如果高阶点从角度映射到圆，则可以使用角度在圆上定义复几何原始数据
- 边，例如
[a, b] - 三角形，例如
[a, b, c] - 正方形，例如
[[a, b], [c, d]]
可以使用 HMap::hmap 方法来处理此类结构。
例如，如果 p 是类型为 Point<Arg<f64>> 的高阶点，则以下代码同时映射两个点
let q: [Point; 2] = [0.0, 1.0].hmap(&p);
对于类型为 f : (T, T) -> U 的二进制高阶映射，可以在使用 HMap::hmap 之前使用 HPair::hpair 方法。
例如
let in_between: Func<f64, f64> = Arc::new(move |(a, b)| {
if b < a {b += 1.0};
(a + (b - a) * 0.5) % 1.0
});
// Pair up.
let args: [(f64, f64); 2] = ([0.7, 0.9], [0.9, 0.1]).hpair();
// `[0.8, 0.0]`
let q: [f64; 2] = args.hmap(&in_between);