You could change my C++ contains() to have a linked-list arg instead, it will still clone the rest of the list each iteration. Linked lists aren't a magic bullet, and neither is the solution to the cloning problem unusable for vectors
. Linked lists also have known performance issues on modern cpus (
http://youtu.be/YQs6IC-vgmo). In normal C++ I could avoid it by using list-mutating functions (i.e. pop_front() and then move() to move the result into the recursion), but that's not the goal here, the goal is to model a pure functional approach. Strictly speaking all the parameters should be const (aka immutable), which would prevent mutating operations.
The standard C++ algorithms currently take pairs of iterators instead, which would make a functional contains look like this:
template<typename t, typename it>
bool contains(const t& i_find, it begin, it end)
{
return begin == end ? false : (*begin == i_find ? true : contains(i_find, std::next(begin), end));
}
which is much uglier to call than the last version (although I have generalized it for use with any type):
auto list = {1,2,3,4}
contains(x, list.begin(), list.end());
With ranges you get:
template<typename t, typename range>
bool contains(const t& i_find, range&& list)
{
return list.begin() == list.end() ? false : (*list.begin() == i_find ? true : contains(i_find, std::make_range(std::next(list.begin()), list.end())));
}
http://ideone.com/gyso7mwhich is almost identical to what I wrote originally (although again, generalized for any type/container), and can be called directly with a list or any other container type, or even a range (as is done in the recursion).
It doesn't work on a bare initializer list without an extra overload because an initializer list is not a deducible type in C++.
If you really want it for tuples (the types of the elements in the tuple are fixed at compile-time in C++) you can do:
template<typename t_find>
bool contains(const t_find& i_find)
{
return false;
}
template<typename t_find, typename... t_rest>
bool contains(const t_find& i_find, t_find&& i_head, t_rest&&... i_rest)
{
return i_find == i_head ? true : contains(i_find, std::forward<t_rest>(i_rest)...)
}
template<typename t_find, typename t_head, typename... t_rest>
bool contains(const t_find& i_find, t_head&& i_head, t_rest&&... i_rest)
{
return contains(i_find, std::forward<t_rest>(i_rest)...)
}
http://ideone.com/kaD2lUAs with the totally compile-time template version I put up first, this version employs functional-language-like tricks like repeating the same name twice in one overload and using two different names in another to automatically call one version if the types are equal, and popping an element off a list by having an explicit variable for the head and an unspecific list for the "rest" to slice a list.
(this version maps the "tuple" from functional languages to c++'s variadic parameter packs, if you want it for an std::tuple, you either need a way to slice a tuple or you just "apply" the tuple to this version to unpack it into the function arguments)
(this version will only compare objects of matching type and assumes everything else doesn't match, if you want to allow comparison between different types you probably need to use enable_if on whether such a comparison operator exists to avoid a compile-time error, but it's still very much doable. Most purely functional languages are runtime-typed, so would either automatically return false from such a comparison or throw a runtime error (needing a similar workaround))
If you want runtime *types* as well as values, then you'd simply need to use a "variant" type with one of the above versions (probably the range one).
Prolog is indeed something that C++ can't directly model, thanks to its built-in first-order-logic solver, but I'll be damned if it's not possible to do somehow, I'm just not planning to build a logic solver myself to do it
EDIT: As a little addendum, I saw something showing a C++ compiler that parsed the C++ source code into a lisp expression tree, essentially turning C++ into lisp and compiling
that. With the compiler written in C++, that's some nice circles if you think about it too hard.
Author
Topic: if self.isCoder(): post() #Programming Thread (Read 903622 times)