'where' statement part II
bearophile
bearophileHUGS at lycos.com
Sat Mar 19 09:01:48 PDT 2011
These are mostly weekend musings.
I've found another possible usage for the 'where' statement. But first let me introduce the topic better.
This page contains a little problem:
http://csokavar.hu/blog/2010/04/20/problem-of-the-week-9-digit-problem/
The problem:
Find a number consisting of 9 digits in which each of the digits from 1 to 9 appears only once. This number must also satisfy these divisibility requirements:
1. The number should be divisible by 9.
2. If the rightmost digit is removed, the remaining number should be divisible by 8.
3. If the rightmost digit of the new number is removed, the remaining number should be divisible by 7.
4. And so on, until there’s only one digit (which will necessarily be divisible by 1).
A solution using just C++0x templates (not found by me, modified):
-------------
// g++ -ftemplate-depth-2000 -std=c++0x nine_digits.cpp
#include "stdio.h"
template<int... digits>
struct Value;
template<>
struct Value<> {
static const int v = 0;
};
template<int first, int... rest>
struct Value<first, rest...> {
static int const v = 10 * Value<rest...>::v + first;
};
template<int elem, int... set>
struct Contains;
template<int elem>
struct Contains<elem> {
static const bool v = false;
};
template<int elem, int first, int... rest>
struct Contains<elem, first, rest...> {
static const bool v = elem == first || Contains<elem, rest...>::v;
};
template<int... digits>
struct DivisorTest;
template<>
struct DivisorTest<> {
static const bool v = true;
};
template<int first, int... rest>
struct DivisorTest<first, rest...> {
static const int num = Value<first, rest...>::v;
static const int div = sizeof...(rest) + 1;
static const int mod = num % div;
static const bool v = mod == 0;
};
template<int first, int... rest>
struct TestCandidate {
static const bool v = (DivisorTest<first, rest...>::v && !Contains<first, rest...>::v);
};
template<int length, int... digits>
struct Search;
template<int length, bool good, bool final, int digit, int... rest>
struct SearchI {
static const int v = Search<length, digit + 1, rest...>::v;
};
template<int length, int digit, int... rest>
struct SearchI<length, true, true, digit, rest...> {
static const int v = Value<digit, rest...>::v;
};
template<int length, int digit, int... rest>
struct SearchI<length, true, false, digit, rest...> {
static const int v = Search<length, 1, digit, rest...>::v;
};
template<int length, int digit, int... rest>
struct Search<length, digit, rest...> {
static const bool good = TestCandidate<digit, rest...>::v;
static const bool final = good && 1 + sizeof...(rest) == length;
static const int v = SearchI<length, good, final, digit, rest...>::v;
};
template<int length>
struct Search<length, 10> {
static const int v = -1;
};
template<int length, int next, int... rest>
struct Search<length, 10, next, rest...> {
static const int v = Search<length, next + 1, rest...>::v;
};
template<int length>
struct Search<length> {
static const int v = Search<length, 1>::v;
};
int main() {
printf("%d\n", Search<7>::v);
return 0;
}
-------------
A translation of the C++0x to Haskell, from here, modified:
http://gergo.erdi.hu/cs/ninedigits/lorentey-c%2B%2B-tmp/lorentey-c%2B%2B-tmp.hs
value :: [Int] -> Int
value [] = 0
value (first:rest) = 10 * (value rest) + first
contains :: Int -> [Int] -> Bool
contains elem [] = False
contains elem (first:rest) = elem == first || (contains elem rest)
divisor_test :: [Int] -> Bool
divisor_test (first:rest) = mod' == 0
where num = value (first:rest)
div = (length rest) + 1
mod' = num `mod` div
test_candidate :: [Int] -> Bool
test_candidate (first:rest) = divisor_test (first:rest) && (not (contains first rest))
search_i :: Int -> Bool -> Bool -> [Int] -> Int
search_i len True True (digit:rest) = value (digit:rest)
search_i len True False (digit:rest) = search len (1:digit:rest)
search_i len good final (digit:rest) = search len (digit+1:rest)
search :: Int -> [Int] -> Int
search len [] = search len [1]
search len [10] = -1
search len (10:next:rest) = search len ((next+1):rest)
search len (digit:rest) = search_i len good final (digit:rest)
where good = test_candidate (digit:rest)
final = good && 1 + (length rest) == len
main = print $ search 9 []
-------------
A translation of the Haskell code to D2 templates:
import core.stdc.stdio: printf;
import std.typetuple: allSatisfy;
template IsInteger(alias x) {
enum bool IsInteger = is(typeof(x) == int);
}
template AreAllIntegers(args...) {
enum bool AreAllIntegers = allSatisfy!(IsInteger, args);
}
template value(args...) if (AreAllIntegers!args) {
static if (args.length == 0)
enum int value = 0;
else
enum int value = 10 * value!(args[1..$]) + args[0];
}
template contains(int elem, args...) if (AreAllIntegers!args) {
static if (args.length == 0)
enum bool contains = false;
else
enum bool contains = elem == args[0] || contains!(elem, args[1..$]);
}
template divisor_test(args...) if (AreAllIntegers!args) {
enum bool divisor_test = (value!args % args.length) == 0;
}
template test_candidate(args...) if (AreAllIntegers!args) {
enum bool test_candidate = divisor_test!args && !(contains!args);
}
template search_i(int length, bool good, bool isFinal, digits...) if (AreAllIntegers!digits) {
static if (good && isFinal)
enum int search_i = value!digits;
else static if (good && !isFinal)
enum int search_i = search!(length, 1, digits);
else
enum int search_i = search!(length, digits[0]+1, digits[1..$]);
}
template search(int length, digits...) if (AreAllIntegers!digits) {
static if (digits.length == 0)
enum int search = search!(length, 1);
else static if (digits.length == 1 && digits[0] == 10)
enum int search = -1;
else static if (digits.length > 1 && digits[0] == 10)
enum int search = search!(length, digits[1]+1, digits[2..$]);
else
enum int search = search_i!(length,
test_candidate!digits,
test_candidate!digits && digits.length == length,
digits);
}
pragma(msg, search!9);
void main() {}
-------------
You see very well that C++/C++0x/D templates are functional programming, D templates are a limited memory-hungry subset of Haskell with a noisy syntax :-) (This also means that taking a look at Haskell syntax and implementation may allow to improve D syntax and D implementation of templates, to reduce the memory they need when they are used to perform computations on true values. This reminds me the famous quite 'Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp.').
The D2 code that uses templates doesn't compile because it performs too many template expansions (the C++0x version needs -ftemplate-depth-2000 to be compiled).
This is a function of the Haskell version:
search :: Int -> [Int] -> Int
search len [] = search len [1]
search len [10] = -1
search len (10:next:rest) = search len ((next+1):rest)
search len (digit:rest) = search_i len good final (digit:rest)
where good = test_candidate (digit:rest)
final = good && 1 + (length rest) == len
A translation to D2:
template search(int length, digits...) if (AreAllIntegers!digits) {
static if (digits.length == 0)
enum int search = search!(length, 1);
else static if (digits.length == 1 && digits[0] == 10)
enum int search = -1;
else static if (digits.length > 1 && digits[0] == 10)
enum int search = search!(length, digits[1]+1, digits[2..$]);
else
enum int search = search_i!(length,
test_candidate!digits,
test_candidate!digits && digits.length == length,
digits);
}
The D2 translation shows two things:
- The variadic template arguments (digits) are typed both in Haskell ([Int]) and C++0x (int digit, int... rest), but not in D2, so I've had to add a template constraint (AreAllIntegers!digits).
- The Haskell code uses a "where" statement. Several people have asked for "private" declarations inside D2 templates that don't break the eponymous template trick. But a different solution is to introduce a "where", this is hypothetical D2/D3 syntax:
// typesafe variadic template, syntax like Typesafe Variadic Functions
template search(int length, int[] digits...) {
static if (digits.length == 0)
enum int search = search!(length, 1);
else static if (digits.length == 1 && digits[0] == 10)
enum int search = -1;
else static if (digits.length > 1 && digits[0] == 10)
enum int search = search!(length, digits[1]+1, digits[2..$]);
else
enum int search = search_i!(length, good, final, digits);
where {
enum bool good = test_candidate!digits;
enum bool isFinal = good && digits.length == length;
};
}
This syntax is not so good, probably there are better ways to solve the same problem. But the need exists, I'd like some way to define other constants in a template that uses the eponymous template trick.
-------------
By the way, it's quite easy to solve the problem with D2 CTFE:
int x(int[] r, int v, int l) {
int tot = l == 9 ? v : 0;
foreach (i; r)
if (((v * 10 + i) % (l + 1)) == 0) {
int[] sele;
foreach (j; r)
if (j != i)
sele ~= j;
tot += x(sele, v*10 + i, l + 1);
}
return tot;
}
pragma(msg, x([1,2,3,4,5,6,7,8,9], 0, 0));
void main() {}
Bye,
bearophile
More information about the Digitalmars-d
mailing list