腾讯云

开发者社区

文档建议反馈控制台

首页

文章/答案/技术大牛

发布

社区首页 >问答首页 >编译时Peano算法

问编译时Peano算法
EN

Code Golf用户

提问于 2021-01-27 12:45:08

回答 3查看 760关注 0票数 9

Peano数将非负整数表示为0或其他Peano数的继承者。例如，1表示为Succ(Zero)，3表示为Succ(Succ(Succ(Zero)))。

任务

在编译时对Peano数字执行以下操作：

加法
减法-你永远不会被要求从一个较小的数字减去一个更大的数字。
乘法
除法-如果结果不是整数，则永远不需要除以两个数字。

Input/Output

输入和输出格式不必相同，但它们应该是其中之一：

类* -> *的类型构造函数用于表示S，类型*的类型表示Z，例如在Java或int[][]中表示2 (int为0，[]为S)。
中间有一个Z的字符串，它周围有0或更多的S(s和)s，例如"S(S(Z))"表示2。
与Peano数字类似的任何其他格式，其中底部有一个表示零的值，另一个包装器可以包含其他值。

规则

只要在编译时可以获得结果，您就可以使用类型成员、隐式构造函数、类型构造函数(任何您想要的)。
为了解决这个问题，运行时之前的任何执行阶段都算作编译时间。
因为答案必须在编译时起作用，所以答案必须用编译过的语言。这包括Python这样的语言，前提是您可以在运行代码之前显示字节码包含计算结果。
这是密码-高尔夫，所以以字节为单位的最短代码将获胜！

示例，仅在Scala

中添加

sealed trait Num {
  //This is like having a method `abstract Num plus(Num n);`
  type Plus[N <: Num] <: Num
}
object Zero extends Num {
  //When we add any n to zero, it's just that n again
  type Plus[N <: Num] = N
}
final class Succ[N <: Num](n: N) extends Num {
  //In Java: `Num plus(Num x) { return new Succ(n.plus(x)) }
  type Plus[X <: Num] = Succ[N#Plus[X]]
}

使用(斯卡斯蒂)：

//This is just for sugar
type +[A <: Num, B <: Num] = A#Plus[B]

type Zero = Zero.type
type Two = Succ[Succ[Zero]]
type Three = Succ[Two]
type Five = Succ[Succ[Three]]
val five: Five = null
val threePlusTwo: Three + Two = five
val notFivePlusTwo: Five + Two = five //should fail
val zeroPlusFive: Zero + Five = five

测试用例

S是接班人，Z是零。

S(S(S(Z))) + Z = S(S(S(Z)))                 | 3 + 0 = 3
S(S(Z)) + S(S(S(Z))) = S(S(S(S(S(Z)))))     | 2 + 3 = 5
S(S(S(Z))) - S(S(S(Z))) = Z                 | 3 - 3 = 0
S(S(Z)) * S(S(S(Z))) = S(S(S(S(S(S(Z))))))  | 2 * 3 = 6
S(S(S(S(Z)))) / S(S(Z)) = S(S(Z))           | 4 / 2 = 2
Z / S(S(Z)) = Z                             | 0 / 2 = 0

一些帮助您入门的链接，

Scala中的类型级编程 (一堆文章，包括关于Peano算法的文章)(针对Scala)
编译时乘法 (用于Scala)
C++型系统中的Peano算法 (用于C++)
类型算法 (为Haskell)

compile-time

code-golf

在线客服搭建方案

搭建集AI机器人、在线客服、智能外呼等多功能服务的客服系统，支持快速接入及自搭建客服系统，从而让顾客快速得到解答

回答 3

Code Golf用户

发布于 2021-01-27 14:25:33

C++，328个字节

#define T templatestruct
#define W T A,class B>struct
#define U using t=
U int;O S;W a;W a,B>:a>{};O a{U N;};W s{U A;};W s,S>:s{};W m{U int;};O m>{U N;};W m>:a::t,A>{};T A,class B,class V=t>struct d:d::t,B,S>{};W d{U B;};

在网上试试！

0 (Z)由int类型表示。Succ(N)由S类型表示。

A+B是a::t，A-B是s::t，A*B是m::t，A/B是d::t。

C++，285个字节

#define U template<
#define Q U class N>struct
#define X(n,o)U class A,class B>struct n:T::v o i::v>{};
Q S;Q i{static const int v=0;};Q i>{static const int v=1+i::v;};U int i>struct T{using t=S::t>;};U>struct T<0>{using t=int;};X(a,+)X(s,-)X(m,*)X(d,/)

这个“便宜”版本(如果允许的话)更短。它简单地将类型转换为int、->、do操作、->转换回类型。

在网上试试！

C++或C，29个字节

#define Z 0
#define S(N)(N+1)

在网上试试！

这甚至更不可靠，它依赖于C具有整数常量表达式和C++具有可以在编译时运行的常量计算。

票数 6

Code Golf用户

发布于 2021-01-30 02:32:15

锈蚀，547字节

struct Z;struct S(Vec);trait A{type R;}implAfor Z{type R=B;}impl>Afor S{type R=S<>::R>;}trait M{type R;}implMfor Z{type R=Z;}implMfor S{type R=S;}impl>M>for S{type R=>::R;}trait T{type R;}implTfor Z{type R=Z;}impl>Tfor Swhere>::R:A{type R=<>::R as A>::R;}trait D{type R;}implD>for Z{type R=Z;}impl>D>for Swhere>::R:D>{type R=S<< as M>>::R as D>>::R>;}在网上试试这基本上等同于Scala版本。它定义了两个结构，Z和S，以及实现这些操作的四个特征(在黄金代码中称为A、M、T和D )。可读的版本：struct Z;
struct S(Vec);

trait Add{type R;}
impl Addfor Z{type R=B;}
impl> Addfor S{type R=S<>::R>;}

trait Sub{type R;}
implSubfor Z{type R=Z;}
impl Subfor S{type R=S;}
impl> Sub>for S{type R=>::R;}

trait Times{type R;}
impl Timesfor Z{type R=Z;}
impl> Timesfor S where >::R: Add{type R=<>::R as Add>::R;}

trait Divide{type R;}
implDivide>for Z{type R=Z;}
impl>Divide>for Swhere>::R:Divide>{type R=S<< as Sub>>::R as Divide>>::R>;}

票数 4

Code Golf用户

发布于 2021-01-31 14:38:48

C++ (gcc)，307字节

#define _ struct
#define n typename
#define t template_ S U=T;};

t,n B>_ s U=S::X>;};
t>_ sU=T;};

t,n B>_ b U=n b::X;};
t>_ bU=T;};

t,n B>_ m U=n s::X>::X;};
t>_ mU=Z;};

t,n B>_ d U=S::X,B>::X>;};
t>_ dU=Z;};