can we change it to support define a List?
fililili opened this issue · 5 comments
For example, a list can be defined in Haskell as List a = Nil | Cons a (List a), can we support it by changing std::tuple and std::variant? Going a step further, can we do it at zero cost?
Hi! Sorry for the delayed response. I've been finishing up the semester and starting at a new job.
We can do this, but I wouldn't recommend it. Recursive Variant was built for the use case of representing types in an abstract syntax tree. Something like an AST can have multiple unrelated types, and it makes sense to use something like a variant in this case.
Under the current implementation, a variant containing either Nil or Cons will be more heavyweight than a pointer-based implementation, like
template <class T>
struct List;
template <class T>
struct Element {
T value;
List<T> tail;
};
template <class T>
struct List {
std::unique_ptr<Element<T>> elem;
};We can then define cons and foreach on the list in a straightforward and functional way:
template <class T>
List<T> cons(T value, std::nullptr_t) {
return {std::make_unique<Element<T>>(
std::move(value),
List<T>{})};
}
template <class T>
List<T> cons(T value, List<T> tail) {
return {std::make_unique<Element<T>>(
std::move(value),
std::move(tail))};
}
template <class T, class Fn>
void foreach(List<T> const& list, Fn func) {
if (list.elem) {
func(list.elem->value);
foreach(list.elem->tail, func);
}
}These can both be used in the way you're familiar with:
int main() {
auto list = cons(0, cons(1, cons(2, nullptr)));
foreach(list, [](int value) {
printf("%i\n", value);
});
}We can also define iterators and whatnot, however those require more code. Here's a live example in godbolt
Is this Zero Cost?
No. There are a lot of clever optimizations you can do with linked lists (blocking, converting them to vectors under the hood, etc). Functional languages like haskell can do these in many cases, but C++ compilers weren't designed to do that. If you ask for a linked list, in all but the most trivial cases it'll give you a linked list, exactly as you implemented it. To rephrase that, linked lists can be fast in some functional languages because it's not actually using a linked list under the hood. The language "cheats" and replaces linked lists with more performant data structures during the compilation of the program.
You can implement some of these optimizations yourself (making a linked list that uses blocks of elements, for example), however that requires more work and makes the implementation more complex.
Aside from teaching purposes, I cannot recommend using traditional linked lists in production C++ code. They have poor cache locality, poor performance characteristics in typical use cases, and there are plenty of good implementations out there that use a lot of clever optimizations to run faster.
@codeinred
Thanks for reply. However, I have a preliminary idea now. List = 1 + T * List = 1 + T + T^2 + T^2 * List = 1 + T + T^2 + .... T^n + ... and this is exactly what vector means, so some language can convert linked list to vector implicitly. Can we use these equality to provide a general optimization mechanism?
I mean, yes. In general vectors and lists support the same set of operations, with the only difference that a vector makes it fast to add elements at the end, but a list makes it fast to add elements to the beginning.
It's easy to just write an adaptor for a vector that treats the end as the beginning, so it acts like a list.
Insertion in the middle can be slow for both cases, but it can actually be faster for small to medium size vectors just because of cache locality.
If you want to learn more about this in C++, I recommend looking at this talk called Postmodern Immutable Data Structures! It's about how to write performant functional datastructures in C++.
@codeinred wow, thanks. That's exactly what I want.
Good luck with your work! If you don't have any other questions, I'm going to close out the issue!