Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Length-indexed list type
#include <iostream>
#include <functional>
#include <memory>
#include <assert.h>
// Based on Bartosz Milewski's immutable list class.
// http://bartoszmilewski.com/2013/11/13/functional-data-structures-in-c-lists/
// Defined externally to List because it needs to be independent from the size parameter.
template <typename T>
struct Item {
Item(T v, std::shared_ptr<const Item<T>> const & tail) : _val(v), _next(tail) {}
T _val;
std::shared_ptr<const Item<T>> _next;
};
// List type, parameterised over type and length.
template <typename T, int size>
class List {
public:
List() {}
List(T v, List<T, size-1> const & tail) : _head(std::make_shared<Item<T>>(v, tail._head)) {}
explicit List(std::shared_ptr<const Item<T>> items) : _head(items) {}
bool isEmpty() const { return !_head; }
T front() const {
assert(!isEmpty());
return _head->_val;
}
List<T, size-1> pop_front() const {
assert(!isEmpty());
return List<T, size-1>(_head->_next);
}
List<T, size+1> push_front(T v) const {
return List<T, size+1>(v, *this);
}
// may be null
std::shared_ptr<const Item<T>> _head;
};
// Helper for constructing empty lists.
template <typename T>
List<T, 0> empty() {
return List<T, 0>();
}
// Apply a function to each list element.
template <typename T, int size>
void forEach(List<T, size> lst, std::function<void(T)> f) {
f(lst.front());
forEach<T, size-1>(lst.pop_front(), f);
}
template <>
void forEach(List<int, 0> lst, std::function<void(int)> f) {
}
template<typename T, int size>
void print(List<T, size> lst) {
forEach<T, size>(lst, [](T v) {
std::cout << "(" << v << ") ";
});
std::cout << std::endl;
}
// (a -> b -> c) -> [a] -> [b] -> [c]
template <typename T, typename U, typename V, int size>
List<T, size> zipWith(std::function<T(U, V)> f, List<U, size> us, List<V, size> vs) {
return zipWith<T, U, V, size - 1>(
f,
us.pop_front(),
vs.pop_front()).push_front(f(us.front(), vs.front()));
}
template <>
List<int, 0> zipWith(std::function<int(int, int)>, List<int, 0> us, List<int, 0> vs) {
return empty<int>();
}
// (a -> b -> a) -> a -> [b] -> a
template <typename T, typename U, int size>
T fold(std::function<T(U, T)> f, T acc, List<U, size> xs) {
T nextAcc = f(xs.front(), acc);
return fold<T, U, size - 1>(f, nextAcc, xs.pop_front());
}
template <>
int fold(std::function<int(int, int)> f, int acc, List<int, 0> xs) {
return acc;
}
// Typesafe dot product on lists.
template <typename T, int size>
T dotProduct(List<T, size> a, List<T, size> b) {
return fold<T, T, size>(
[](T x, T y) { return x + y; },
0,
zipWith<T, T, T, size>(
[](T x, T y) { return x * y; },
a,
b));
}
int main(int argc, char *argv[]) {
// [3, 4, 5]
auto x = empty<int>().push_front(5).push_front(4).push_front(3);
print(x);
// [9, 2, 1]
auto y = empty<int>().push_front(1).push_front(2).push_front(9);
print(y);
int z = dotProduct(x, y);
std::cout << z << std::endl;
getchar();
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment