1

I have this struct template

template<typename N>
struct Succ{};

and this function template

template<typename N> N dec(Succ<N> s_n){
    N n;
    return n;
}

and this does exactly what I want, if I decrement once too often, I get a compiler error.

Now, I would like to use this style of code in my projects for catching errors, however it is very tedious to create initial "values", I mean, 2 is already Succ<Succ<SomeType>>.

How can I accomplish this with C++ templates? Something like

Nat<2,SomeType> two;

which is the same as

Succ<Succ<SomeType>> two;

And can some people give me links or other resources to this kind of template programming please? Like, how to implement Peano Arithmetic with C++ templates and how to create Type Numbers more easily.

Manatee Pink
  • 160
  • 7
  • Welcome to stackoverflow.com. Please take some time to read [the help pages](http://stackoverflow.com/help), especially the sections named ["What topics can I ask about here?"](http://stackoverflow.com/help/on-topic) and ["What types of questions should I avoid asking?"](http://stackoverflow.com/help/dont-ask). Also please take the [tour] and read about [ask] good questions. Lastly please read [this question checklist](https://codeblog.jonskeet.uk/2012/11/24/stack-overflow-question-checklist/). – Some programmer dude Jul 24 '22 at 08:39
  • I see no reason why you implement it using type? `Nat<2>` is already different type than `Nat<1>`. – apple apple Jul 24 '22 at 09:22
  • @appleapple, do you mean, why is there an additional type parameter in my question? No particular reason, I just happened to get started that way, I don't care about the unique Natural Numbers in that sense, just the structure. – Manatee Pink Jul 24 '22 at 09:33
  • @ManateePink well I'd probably define `Succ` as alias to `Nat` so 3 is `Nat<3>` it just appears to be the same as `succ>>` (actually I'm not sure why `succ` is not a function while `dec` is) – apple apple Jul 24 '22 at 09:48
  • or, it look like your are trying to implement natural number by... using natural number? – apple apple Jul 24 '22 at 09:58

3 Answers3

5

Something like this

template<typename N>
struct Succ{};

template<int N, typename T>
struct NatImpl
{
    using type = Succ<typename NatImpl<N-1, T>::type>;
};

template<typename T>
struct NatImpl<0, T>
{
    using type = T;
};

template<int N, typename T>
using Nat = typename NatImpl<N, T>::type;

Templated using is a thing, but you can't specialise them, so that is done in the NatImpl class.

And the proof

int main()
{
    Nat<3,int> x = Succ<Succ<int>>();
}

error C2440: 'initializing': cannot convert from 'Succ<Succ<int>>' to 'Succ<Succ<Succ<int>>>'

john
  • 85,011
  • 4
  • 57
  • 81
  • Wow, thanks, great! Why is there `typename` in the 7th line though, in the `NatImpl` definition right after `Succ<`? – Manatee Pink Jul 24 '22 at 08:56
  • 1
    @ManateePink Because `NatImpl::type` is a *dependent type* and that requires the `typename` keyword. See [Where and why do I have to put the "template" and "typename" keywords?](https://stackoverflow.com/questions/610245/where-and-why-do-i-have-to-put-the-template-and-typename-keywords) – Some programmer dude Jul 24 '22 at 09:14
  • @Someprogrammerdude, thank you very much. I am curious, would you happen to know some resources with regards to this kind of "Compile-Time Constraints Programming" in C++? (I think Rust would also be a fine substitute) – Manatee Pink Jul 24 '22 at 09:34
2

You can create a alias template taking the number, a template and the type as template parameters and implement it via a helper template:

template<size_t N, template<class> class T, class U>
struct NatHelper
{
    using Type = T<typename NatHelper<N - 1, T, U>::Type>;
};

template<template<class> class T, class U>
struct NatHelper<0, T, U>
{
    using Type = U;
};

template<size_t N, template<class> class T, class U>
using Nat = typename NatHelper<N, T, U>::Type;

struct SomeType
{};

template<typename N>
struct Succ {};

using N0 = Nat<0, Succ, SomeType>;
static_assert(std::is_same_v<N0, SomeType>);

using N2 = Nat<2, Succ, SomeType>;
static_assert(std::is_same_v<N2, Succ<Succ<SomeType>>>);

using N10 = Nat<10, Succ, SomeType>;
static_assert(std::is_same_v<N10, Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<Succ<SomeType>>>>>>>>>>>);
fabian
  • 80,457
  • 12
  • 86
  • 114
  • Cool, thanks! I take it, this is a generalized version where you can wrap with something other then `Succ`? – Manatee Pink Jul 24 '22 at 08:57
  • 1
    @ManateePink Indeed this works with any template taking a single type as parameter. – fabian Jul 24 '22 at 09:16
  • Really cool. I am curious, would you happen to know some resources with regards to this kind of "Compile-Time Constraints Programming" in C++? (I think Rust would also be a fine substitute) – Manatee Pink Jul 24 '22 at 09:34
2

A C++17 version using constexpr if could look like this:

template <size_t N, class SomeType>
auto NatHelper() {
    if constexpr (N > 1) return Succ<decltype(NatHelper<N - 1, SomeType>())>{};
    else return Succ<SomeType>{};
}

template<size_t N, class SomeType>
using Nat = decltype(NatHelper<N, SomeType>());

Demo

Ted Lyngmo
  • 93,841
  • 5
  • 60
  • 108
  • Aaah, very cool, so this uses a function template instead of a struct template. Could I just use the function directly instead of the alias? Like `auto ten = NatHelper<10,Whatever>();` – Manatee Pink Jul 24 '22 at 09:02
  • 1
    @ManateePink Yes, exactly so. – Ted Lyngmo Jul 24 '22 at 09:02
  • Awesome, I think, I prefer this function template version to the struct ones. I am curious, would you happen to know some resources with regards to this kind of "Compile-Time Constraints Programming" in C++? (I think Rust would also be a fine substitute) – Manatee Pink Jul 24 '22 at 09:06
  • @ManateePink I bought one of the template books on [The Definitive C++ Book Guide and List](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) but to be honest, I've picked up most of what I know about templates from searching for things here at SO. – Ted Lyngmo Jul 24 '22 at 09:08