Skip to content

Instantly share code, notes, and snippets.

@yoh2
Last active February 8, 2018 13:50
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save yoh2/097b9b377fa57151df974c4ca3ac3ca7 to your computer and use it in GitHub Desktop.
Save yoh2/097b9b377fa57151df974c4ca3ac3ca7 to your computer and use it in GitHub Desktop.
型レベル FizzBuzz という字面のみから連想したもの。FizzBuzz 判定部では四則演算を用いずに型だけで何とかしてみた。
#include <iostream>
#include <sstream>
// リスト
template<typename... TS> struct L
{
template<typename T>
using cons = L<T, TS...>;
template<template<typename> typename F>
using map = L<F<TS>...>;
};
// 最終的な表示用
template<unsigned N>
struct Number
{
static constexpr unsigned value = N;
};
template<unsigned N>
constexpr unsigned Number<N>::value;
template<char... S> struct Str
{
static constexpr char value[] = { S..., '\0' };
};
template<char... S>
constexpr char Str<S...>::value[];
using FizzBuzzS = Str<'F', 'i', 'z', 'z', 'B', 'u', 'z', 'z'>;
using FizzS = Str<'F', 'i', 'z', 'z'>;
using BuzzS = Str<'B', 'u', 'z', 'z'>;
// 結果表示
template<typename RESULTS>
struct print_result;
template<typename... TS>
struct print_result<L<TS...>>
{
print_result()
{
(std::cout << ... << to_line(TS::value));
}
template<typename T>
std::string to_line(const T &x) const
{
std::stringstream ss;
ss << x << '\n';
return ss.str();
}
};
// おなじみペアノ数
struct Z;
template<typename N> struct S;
template<typename N>
struct ToNumberImpl;
// ペアノ数 -> Number
template<typename N>
using ToNumber = typename ToNumberImpl<N>::type;
template<>
struct ToNumberImpl<Z>
{
using type = Number<0>;
};
template<typename N>
struct ToNumberImpl<S<N>>
{
using type = Number<ToNumber<N>::value + 1>;
};
// Z = 0 と対応付けた上で [1, N] のペアノ数リストを作成。
template<unsigned N>
struct NatListImpl
{
using type = typename NatListImpl<N - 1>::type::template map<S>::template cons<S<Z>>;
};
template<unsigned N>
using NatList = typename NatListImpl<N>::type;
template<>
struct NatListImpl<0>
{
using type = L<>;
};
// いわゆる Maybe
template<typename T> struct Just
{
template<typename>
using or_else = T;
};
struct Nothing
{
template<typename T>
using or_else = T;
};
template<typename X, template<typename> typename DEFAULT_F, template<typename> typename... FS>
struct FindFirstOrDefaultImpl;
template<typename X, template<typename> typename DEFAULT_F, template<typename> typename... FS>
using FindFirstOrDefault = typename FindFirstOrDefaultImpl<X, DEFAULT_F, FS...>::type;
template<typename X, template<typename> typename DEFAULT_F>
struct FindFirstOrDefaultImpl<X, DEFAULT_F>
{
using type = DEFAULT_F<X>;
};
template<typename X, template<typename> typename DEFAULT_F, template<typename> typename F, template<typename> typename... FS>
struct FindFirstOrDefaultImpl<X, DEFAULT_F, F, FS...>
{
using type = typename F<X>::template or_else<FindFirstOrDefault<X, DEFAULT_F, FS...>>;
};
// FizzBuzz か?
template<typename N>
struct FizzBuzzSOrNothingImpl
{
using type = Nothing;
};
template<typename N>
using FizzBuzzSOrNothing = typename FizzBuzzSOrNothingImpl<N>::type;
template<>
struct FizzBuzzSOrNothingImpl<Z>
{
using type = Just<FizzBuzzS>;
};
template<typename N>
struct FizzBuzzSOrNothingImpl<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<N>>>>>>>>>>>>>>>>
{
using type = FizzBuzzSOrNothing<N>;
};
// Fizz か?
template<typename N>
struct FizzSOrNothingImpl
{
using type = Nothing;
};
template<typename N>
using FizzSOrNothing = typename FizzSOrNothingImpl<N>::type;
template<>
struct FizzSOrNothingImpl<Z>
{
using type = Just<FizzS>;
};
template<typename N>
struct FizzSOrNothingImpl<S<S<S<N>>>>
{
using type = FizzSOrNothing<N>;
};
// Buzz か?
template<typename N>
struct BuzzSOrNothingImpl
{
using type = Nothing;
};
template<typename N>
using BuzzSOrNothing = typename BuzzSOrNothingImpl<N>::type;
template<>
struct BuzzSOrNothingImpl<Z>
{
using type = Just<BuzzS>;
};
template<typename N>
struct BuzzSOrNothingImpl<S<S<S<S<S<N>>>>>>
{
using type = BuzzSOrNothing<N>;
};
// FizzBuzz ひとつ分
template<typename N>
using FizzBuzz1 = FindFirstOrDefault<N, ToNumber, FizzBuzzSOrNothing, FizzSOrNothing, BuzzSOrNothing>;
int main()
{
print_result<NatList<100>::map<FizzBuzz1>>();
}
import std.stdio;
// リスト
struct L(TS...)
{
alias cons(T) = L!(T, TS);
template map(alias F)
{
static if(TS.length == 0)
{
alias map = L!();
}
else
{
alias map = L!(TS[1..$]).map!(F).cons!(F!(TS[0]));
}
}
}
// 最終的な表示用
struct Str(string S)
{
static immutable string str = S;
}
struct Number(uint N)
{
static immutable string str = N.stringof[0..$-1]; // 末尾の 'u' が余計なので取っ払っている
}
template Concat(TS...)
{
static if(TS.length == 0)
{
static immutable string Concat = "";
}
else
{
static immutable string Concat = TS[0].str ~ '\n' ~ Concat!(TS[1..$]);
}
}
// おなじみペアノ数
struct Z;
struct S(T)
{
// 折角なので T に変なものが入らないようガード。
static assert(is(T == Z) || is(T == S!U, U));
}
// ペアノ数 -> Number
template ToNumber(N)
{
static if(is(N == Z))
{
alias ToNumber = Number!0;
}
else static if(is(N == S!M, M) && is(ToNumber!(M) == Number!(X), uint X))
{
alias ToNumber = Number!(1 + X);
}
else
{
static assert(false);
}
}
// Z = 0 と対応付けた上で [1, N] のペアノ数リストを作成。
template NatList(uint N)
{
static if(N == 0)
{
alias NatList = L!();
}
else
{
alias NatList = NatList!(N - 1).map!(S).cons!(S!Z);
}
}
// いわゆる Maybe
struct Just(T)
{
alias or(U) = T;
}
struct Nothing
{
alias or(U) = U;
}
// C++ で言うところのテンプレートテンプレートパラメータの可変長リストが取れないので
// C++ 版とはちょっと違う実装
template FindfirstOrDefault(DEFAULT, TS...)
{
static if(TS.length == 0)
{
alias FindfirstOrDefault = DEFAULT;
}
else
{
alias FindfirstOrDefault = TS[0].or!(FindfirstOrDefault!(DEFAULT, TS[1..$]));
}
}
// FizzBuzz か?
template FizzBuzzOrNothing(N)
{
static if(is(N == Z))
{
alias FizzBuzzOrNothing = Just!(Str!"FizzBuzz");
}
else static if(is(N == S!(S!(S!(S!(S!(S!(S!(S!(S!(S!(S!(S!(S!(S!(S!(M))))))))))))))), M))
{
alias FizzBuzzOrNothing = FizzBuzzOrNothing!M;
}
else
{
alias FizzBuzzOrNothing = Nothing;
}
}
// Fizz か?
template FizzOrNothing(N)
{
static if(is(N == Z))
{
alias FizzOrNothing = Just!(Str!"Fizz");
}
else static if(is(N == S!(S!(S!(M))), M))
{
alias FizzOrNothing = FizzOrNothing!M;
}
else
{
alias FizzOrNothing = Nothing;
}
}
// Buzz か?
template BuzzOrNothing(N)
{
static if(is(N == Z))
{
alias BuzzOrNothing = Just!(Str!"Buzz");
}
else static if(is(N == S!(S!(S!(S!(S!(M))))), M))
{
alias BuzzOrNothing = BuzzOrNothing!M;
}
else
{
alias BuzzOrNothing = Nothing;
}
}
// FizzBuzz ひとつ分
alias FizzBuzz1(N) = FindfirstOrDefault!(ToNumber!N, FizzBuzzOrNothing!N, FizzOrNothing!N, BuzzOrNothing!N);
void main()
{
if (is(NatList!(100).map!(FizzBuzz1) == L!(TS), TS...))
{
write(Concat!(TS));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment