Length-indexed list type

lengthindexed.cpp

#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;
}