// linked lists in C++ with closure ops and lambda terms
#include<iostream>
#include<memory>
#include<functional>   /* requires -std=c++14 */
using namespace std;

// Linked list with smart pointer:
template<typename T>
struct cell {
  T item;
  shared_ptr<cell<T>> next{nullptr};  // counted pointer to next cell
  cell(T i, shared_ptr<cell<T>> n) : item{i} {next=n;}
  cell(T i) : item{i} {};

  // The only methods to define are foreach and reduce:

  void foreach(function<void(T&)> f) {
    f(item);
    if (next) next->foreach(f);  // tail-recursive call!
  }//foreach

  template<typename U>
  U reduce(function<U(U,T)> op, U accumulator) {
    accumulator = op(accumulator,item);
    if (next) return next->reduce(op,accumulator);
    else return accumulator;  // also tail-recursive
  }//reduce
};//cell

// convenient functions:
shared_ptr<cell<int>> cons(int i, shared_ptr<cell<int>>&& n) {
  return make_shared<cell<int>>(i,n);
}

int car(shared_ptr<cell<int>>& m) { return m->item; }
int car(shared_ptr<cell<int>>&& m) { return m->item; }
shared_ptr<cell<int>> cdr(shared_ptr<cell<int>>& m) { return m->next; }
shared_ptr<cell<int>> cdr(shared_ptr<cell<int>>&& m) { return m->next; }

// define all other operations with foreach/reduce.

int length(shared_ptr<cell<int>>&& m) {
  int cx = 0;
  m->foreach([&cx](auto& y){ cx++; });
  return cx;
}

bool search(int x, shared_ptr<cell<int>>&& m) {
  bool found = false;
  m->foreach([&](auto& y){ if (x==y) found = true;});
  return found;
}

int main() {
  auto m = cons(2,cons(3,cons(5,cons(7,nullptr))));
  cout << car(cdr(cdr(m))) << endl; // 5

    // use foreach to print
  m->foreach([](auto& x) {cout << x << " ";});
  cout << endl;

  // use reduce to sum up values
  int sum = m->reduce<int>([](int x, int y){return x+y;}, 0);
  cout << "sum is " << sum << endl;

  cout << "10 is in list: " << search(10,move(m)) << endl;
  cout << "11 is in list: " << search(11,move(m)) << endl;

  // shareable linked list

  auto m2 = cons(9,cdr(m));
  
  // use foreach to mutate values via l-value reference parameter
  m->foreach([](auto& x) { x=x*2; });

  // shared mutations
  m2->foreach([](auto& x) {cout << x << " ";});  cout << endl;
  m->foreach([](auto& x) {cout << x << " ";});  cout << endl;
}//main