ceph/src/boost/boost/phoenix/function/lazy_list.hpp

   1 ////////////////////////////////////////////////////////////////////////////
   2 // lazy_list.hpp
   3 //
   4 // Build lazy operations for Phoenix equivalents for FC++
   5 //
   6 // These are equivalents of the Boost FC++ functoids in list.hpp
   7 //
   8 // Implemented so far:
   9 //
  10 // head tail null
  11 //
  12 // strict_list<T> and associated iterator.
  13 //
  14 // list<T> and odd_list<T>
  15 //
  16 // cons cat
  17 //
  18 // Comparisons between list and odd_list types and separately for strict_list.
  19 //
  20 // NOTES: There is a fix at the moment as I have not yet sorted out
  21 //        how to get back the return type of a functor returning a list type.
  22 //        For the moment I have fixed this as odd_list<T> at two locations,
  23 //        one in list<T> and one in Cons. I am going to leave it like this
  24 //        for now as reading the code, odd_list<T> seems to be correct.
  25 //
  26 //        I am also not happy at the details needed to detect types in Cons.
  27 //
  28 // I think the structure of this file is now complete.
  29 // John Fletcher  February 2015.
  30 //
  31 ////////////////////////////////////////////////////////////////////////////
  32 /*=============================================================================
  33     Copyright (c) 2000-2003 Brian McNamara and Yannis Smaragdakis
  34     Copyright (c) 2001-2007 Joel de Guzman
  35     Copyright (c) 2015 John Fletcher
  36
  37     Distributed under the Boost Software License, Version 1.0. (See accompanying
  38     file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
  39 ==============================================================================*/
  40
  41 ///////////////////////////////////////////////////////////////////////
  42 // This is from Boost FC++ list.hpp reimplemented without Fun0 or Full0
  43 ///////////////////////////////////////////////////////////////////////
  44
  45 /*
  46 concept ListLike: Given a list representation type L
  47
  48 L<T> inherits ListLike and has
  49    // typedefs just show typical values
  50    typedef T value_type
  51    typedef L<T> force_result_type
  52    typedef L<T> delay_result_type
  53    typedef L<T> tail_result_type
  54    template <class UU> struct cons_rebind {
  55       typedef L<UU> type;        // force type
  56       typedef L<UU> delay_type;  // delay type
  57    };
  58
  59    L()
  60    L( a_unique_type_for_nil )
  61    template <class F> L(F)       // F :: ()->L
  62
  63    constructor: force_result_type( T, L<T> )
  64    template <class F>
  65    constructor: force_result_type( T, F )  // F :: ()->L
  66
  67    template <class It>
  68    L( It, It )
  69
  70    // FIX THIS instead of operator bool(), does Boost have something better?
  71    operator bool() const
  72    force_result_type force() const
  73    delay_result_type delay() const
  74    T head() const
  75    tail_result_type tail() const
  76
  77    static const bool is_lazy;   // true if can represent infinite lists
  78
  79    typedef const_iterator;
  80    typedef const_iterator iterator;  // ListLikes are immutable
  81    iterator begin() const
  82    iterator end() const
  83 */
  84
  85 //////////////////////////////////////////////////////////////////////
  86 // End of section from Boost FC++ list.hpp
  87 //////////////////////////////////////////////////////////////////////
  88
  89 #ifndef BOOST_PHOENIX_FUNCTION_LAZY_LIST
  90 #define BOOST_PHOENIX_FUNCTION_LAZY_LIST
  91
  92 #include <boost/phoenix/core.hpp>
  93 #include <boost/phoenix/function.hpp>
  94 #include <boost/intrusive_ptr.hpp>
  95 #include <boost/function.hpp>
  96 #include <boost/type_traits/type_with_alignment.hpp>
  97 //#include "lazy_reuse.hpp"
  98
  99 namespace boost {
 100
 101   namespace phoenix {
 102
 103 //////////////////////////////////////////////////////////////////////
 104 // These are the list types being declared.
 105 //////////////////////////////////////////////////////////////////////
 106
 107    template <class T> class strict_list;
 108     namespace impl {
 109    template <class T> class list;
 110    template <class T> class odd_list;
 111     }
 112    // in ref_count.hpp in BoostFC++ now in lazy_operator.hpp
 113    //typedef unsigned int RefCountType;
 114
 115 //////////////////////////////////////////////////////////////////////
 116 // a_unique_type_for_nil moved to lazy_operator.hpp.
 117 //////////////////////////////////////////////////////////////////////
 118
 119
 120 //////////////////////////////////////////////////////////////////////
 121 // Distinguish lazy lists (list and odd_list) from strict_list.
 122 //////////////////////////////////////////////////////////////////////
 123
 124     namespace lazy {
 125       // Copied from Boost FC++ list.hpp
 126       template <class L, bool is_lazy> struct ensure_lazy_helper {};
 127       template <class L> struct ensure_lazy_helper<L,true> {
 128          static void requires_lazy_list_to_prevent_infinite_recursion() {}
 129       };
 130       template <class L>
 131       void ensure_lazy() {
 132         ensure_lazy_helper<L,L::is_lazy>::
 133         requires_lazy_list_to_prevent_infinite_recursion();
 134       }
 135
 136     }
 137
 138 //////////////////////////////////////////////////////////////////////
 139 // Provide remove reference for types defined for list types.
 140 //////////////////////////////////////////////////////////////////////
 141
 142     namespace result_of {
 143
 144       template < typename L >
 145       class ListType
 146       {
 147       public:
 148         typedef typename boost::remove_reference<L>::type LType;
 149         typedef typename LType::value_type value_type;
 150         typedef typename LType::tail_result_type tail_result_type;
 151         typedef typename LType::force_result_type force_result_type;
 152         typedef typename LType::delay_result_type delay_result_type;
 153       };
 154
 155       template <>
 156       class ListType<a_unique_type_for_nil>
 157       {
 158       public:
 159         typedef a_unique_type_for_nil LType;
 160         //typedef a_unique_type_for_nil value_type;
 161       };
 162
 163       template <typename F, typename T>
 164       struct ResultType {
 165         typedef typename impl::odd_list<T> type;
 166       };
 167
 168     }
 169
 170 //////////////////////////////////////////////////////////////////////
 171 // ListLike is a property inherited by any list type to enable it to
 172 // work with the functions being implemented in this file.
 173 // It provides the check for the structure described above.
 174 //////////////////////////////////////////////////////////////////////
 175
 176    namespace listlike {
 177
 178        struct ListLike {};   // This lets us use is_base_and_derived() to see
 179        // (at compile-time) what classes are user-defined lists.
 180
 181
 182        template <class L, bool is_lazy> struct ensure_lazy_helper {};
 183        template <class L> struct ensure_lazy_helper<L,true> {
 184            static void requires_lazy_list_to_prevent_infinite_recursion() {}
 185        };
 186        template <class L>
 187        void ensure_lazy() {
 188          ensure_lazy_helper<L,L::is_lazy>::
 189          requires_lazy_list_to_prevent_infinite_recursion();
 190        }
 191
 192        template <class L, bool b>
 193        struct EnsureListLikeHelp {
 194            static void trying_to_call_a_list_function_on_a_non_list() {}
 195        };
 196        template <class L> struct EnsureListLikeHelp<L,false> { };
 197        template <class L>
 198        void EnsureListLike() {
 199           typedef typename result_of::ListType<L>::LType LType;
 200           EnsureListLikeHelp<L,boost::is_base_and_derived<ListLike,LType>::value>::
 201              trying_to_call_a_list_function_on_a_non_list();
 202        }
 203
 204       template <class L>
 205       bool is_a_unique_type_for_nil(const L& /*l*/) {
 206          return false;
 207       }
 208
 209       template <>
 210       bool is_a_unique_type_for_nil<a_unique_type_for_nil>
 211       (const a_unique_type_for_nil& /* n */) {
 212          return true;
 213       }
 214
 215       template <class L>
 216       struct detect_nil {
 217         static const bool is_nil = false;
 218       };
 219
 220       template <>
 221       struct detect_nil<a_unique_type_for_nil> {
 222        static const bool is_nil = true;
 223       };
 224
 225       template <>
 226       struct detect_nil<a_unique_type_for_nil&> {
 227        static const bool is_nil = true;
 228       };
 229
 230       template <>
 231       struct detect_nil<const a_unique_type_for_nil&> {
 232        static const bool is_nil = true;
 233       };
 234
 235     }
 236
 237 //////////////////////////////////////////////////////////////////////
 238 // Implement lazy functions for list types. cat and cons come later.
 239 //////////////////////////////////////////////////////////////////////
 240
 241 #ifndef BOOST_PHOENIX_FUNCTION_MAX_LAZY_LIST_LENGTH
 242 #define BOOST_PHOENIX_FUNCTION_MAX_LAZY_LIST_LENGTH 1000
 243 #endif
 244
 245     namespace impl {
 246
 247       struct Head
 248       {
 249         template <typename Sig>
 250         struct result;
 251
 252         template <typename This, typename L>
 253         struct result<This(L)>
 254         {
 255           typedef typename result_of::ListType<L>::value_type type;
 256         };
 257
 258         template <typename L>
 259         typename result<Head(L)>::type
 260         operator()(const L & l) const
 261         {
 262           listlike::EnsureListLike<L>();
 263           return l.head();
 264         }
 265
 266       };
 267
 268       struct Tail
 269       {
 270         template <typename Sig>
 271         struct result;
 272
 273         template <typename This, typename L>
 274         struct result<This(L)>
 275         {
 276           typedef typename result_of::ListType<L>::tail_result_type type;
 277         };
 278
 279         template <typename L>
 280         typename result<Tail(L)>::type
 281         operator()(const L & l) const
 282         {
 283           listlike::EnsureListLike<L>();
 284           return l.tail();
 285         }
 286
 287       };
 288
 289       struct Null
 290       {
 291         template <typename Sig>
 292         struct result;
 293
 294         template <typename This, typename L>
 295         struct result<This(L)>
 296         {
 297             typedef bool type;
 298         };
 299
 300         template <typename L>
 301         typename result<Null(L)>::type
 302         //bool
 303         operator()(const L& l) const
 304         {
 305           listlike::EnsureListLike<L>();
 306           return !l;
 307         }
 308
 309       };
 310
 311       struct Delay {
 312         template <typename Sig>
 313         struct result;
 314
 315         template <typename This, typename L>
 316         struct result<This(L)>
 317         {
 318           typedef typename result_of::ListType<L>::delay_result_type type;
 319         };
 320
 321         template <typename L>
 322         typename result<Delay(L)>::type
 323         operator()(const L & l) const
 324         {
 325           listlike::EnsureListLike<L>();
 326           return l.delay();
 327         }
 328
 329       };
 330
 331       struct Force {
 332         template <typename Sig>
 333         struct result;
 334
 335         template <typename This, typename L>
 336         struct result<This(L)>
 337         {
 338           typedef typename result_of::ListType<L>::force_result_type type;
 339         };
 340
 341         template <typename L>
 342         typename result<Force(L)>::type
 343         operator()(const L & l) const
 344         {
 345           listlike::EnsureListLike<L>();
 346           return l.force();
 347         }
 348
 349       };
 350
 351     }
 352     //BOOST_PHOENIX_ADAPT_CALLABLE(head, impl::head, 1)
 353     //BOOST_PHOENIX_ADAPT_CALLABLE(tail, impl::tail, 1)
 354     //BOOST_PHOENIX_ADAPT_CALLABLE(null, impl::null, 1)
 355     typedef boost::phoenix::function<impl::Head> Head;
 356     typedef boost::phoenix::function<impl::Tail> Tail;
 357     typedef boost::phoenix::function<impl::Null> Null;
 358     typedef boost::phoenix::function<impl::Delay> Delay;
 359     typedef boost::phoenix::function<impl::Force> Force;
 360     Head head;
 361     Tail tail;
 362     Null null;
 363     Delay delay;
 364     Force force;
 365
 366 //////////////////////////////////////////////////////////////////////
 367 // These definitions used for strict_list are imported from BoostFC++
 368 // unchanged.
 369 //////////////////////////////////////////////////////////////////////
 370
 371 namespace impl {
 372 template <class T>
 373 struct strict_cons : public boost::noncopyable {
 374    mutable RefCountType refC;
 375    T head;
 376    typedef boost::intrusive_ptr<strict_cons> tail_type;
 377    tail_type tail;
 378    strict_cons( const T& h, const tail_type& t ) : refC(0), head(h), tail(t) {}
 379
 380 };
 381 template <class T>
 382 void intrusive_ptr_add_ref( const strict_cons<T>* p ) {
 383    ++ (p->refC);
 384 }
 385 template <class T>
 386 void intrusive_ptr_release( const strict_cons<T>* p ) {
 387    if( !--(p->refC) ) delete p;
 388 }
 389
 390 template <class T>
 391 class strict_list_iterator
 392 : public std::iterator<std::input_iterator_tag,T,ptrdiff_t> {
 393    typedef boost::intrusive_ptr<strict_cons<T> > rep_type;
 394    rep_type l;
 395    bool is_nil;
 396    void advance() {
 397       l = l->tail;
 398       if( !l )
 399          is_nil = true;
 400    }
 401    class Proxy {  // needed for operator->
 402       const T x;
 403       friend class strict_list_iterator;
 404       Proxy( const T& xx ) : x(xx) {}
 405    public:
 406       const T* operator->() const { return &x; }
 407    };
 408 public:
 409    strict_list_iterator() : l(), is_nil(true) {}
 410    explicit strict_list_iterator( const rep_type& ll ) : l(ll), is_nil(!ll) {}
 411
 412    const T operator*() const { return l->head; }
 413    const Proxy operator->() const { return Proxy(l->head); }
 414    strict_list_iterator<T>& operator++() {
 415       advance();
 416       return *this;
 417    }
 418    const strict_list_iterator<T> operator++(int) {
 419       strict_list_iterator<T> i( *this );
 420       advance();
 421       return i;
 422    }
 423    bool operator==( const strict_list_iterator<T>& i ) const {
 424       return is_nil && i.is_nil;
 425    }
 426    bool operator!=( const strict_list_iterator<T>& i ) const {
 427       return ! this->operator==(i);
 428    }
 429 };
 430 }
 431
 432 //////////////////////////////////////////////////////////////////////
 433 //////////////////////////////////////////////////////////////////////
 434
 435    template <class T>
 436    class strict_list : public listlike::ListLike
 437    {
 438        typedef boost::intrusive_ptr<impl::strict_cons<T> > rep_type;
 439        rep_type rep;
 440        struct Make {};
 441
 442        template <class Iter>
 443        static rep_type help( Iter a, const Iter& b ) {
 444            rep_type r;
 445            while( a != b ) {
 446               T x( *a );
 447               r = rep_type( new impl::strict_cons<T>( x, r ) );
 448               ++a;
 449            }
 450            return r;
 451        }
 452
 453    public:
 454        static const bool is_lazy = false;
 455
 456        typedef T value_type;
 457        typedef strict_list force_result_type;
 458        typedef strict_list delay_result_type;
 459        typedef strict_list tail_result_type;
 460        template <class UU> struct cons_rebind {
 461            typedef strict_list<UU> type;
 462            typedef strict_list<UU> delay_type;
 463        };
 464
 465
 466    strict_list( Make, const rep_type& r ) : rep(r) {}
 467
 468    strict_list() : rep() {}
 469
 470    strict_list( a_unique_type_for_nil ) : rep() {}
 471
 472    template <class F>
 473    strict_list( const F& f ) : rep( f().rep ) {
 474      // I cannot do this yet.
 475      //functoid_traits<F>::template ensure_accepts<0>::args();
 476    }
 477
 478    strict_list( const T& x, const strict_list& y )
 479       : rep( new impl::strict_cons<T>(x,y.rep) ) {}
 480
 481    template <class F>
 482    strict_list( const T& x, const F& f )
 483       : rep( new impl::strict_cons<T>(x,f().rep) ) {}
 484
 485      operator bool() const { return (bool)rep; }
 486    force_result_type force() const { return *this; }
 487    delay_result_type delay() const { return *this; }
 488    T head() const {
 489 #ifndef BOOST_PHOENIX_NO_LAZY_EXCEPTIONS
 490       if( !*this )
 491          throw lazy_exception("Tried to take head() of empty strict_list");
 492 #endif
 493       return rep->head;
 494    }
 495    tail_result_type tail() const {
 496 #ifndef BOOST_PHOENIX_NO_LAZY_EXCEPTIONS
 497       if( !*this )
 498          throw lazy_exception("Tried to take tail() of empty strict_list");
 499 #endif
 500       return strict_list(Make(),rep->tail);
 501    }
 502
 503    template <class Iter>
 504    strict_list( const Iter& a, const Iter& b ) : rep( rep_type() ) {
 505       // How ironic.  We need to reverse the iterator range in order to
 506       // non-recursively build this!
 507       std::vector<T> tmp(a,b);
 508       rep = help( tmp.rbegin(), tmp.rend() );
 509    }
 510
 511    // Since the strict_cons destructor can't call the strict_list
 512    // destructor, the "simple" iterative destructor is correct and
 513    // efficient.  Hurray.
 514    ~strict_list() { while(rep && (rep->refC == 1)) rep = rep->tail; }
 515
 516    // The following helps makes strict_list almost an STL "container"
 517    typedef impl::strict_list_iterator<T> const_iterator;
 518    typedef const_iterator iterator;         // strict_list is immutable
 519    iterator begin() const { return impl::strict_list_iterator<T>( rep ); }
 520    iterator end() const   { return impl::strict_list_iterator<T>(); }
 521
 522    };
 523
 524     // All of these null head and tail are now non lazy using e.g. null(a)().
 525     // They need an extra () e.g. null(a)().
 526     template <class T>
 527     bool operator==( const strict_list<T>& a, a_unique_type_for_nil ) {
 528       return null(a)();
 529     }
 530     template <class T>
 531     bool operator==( a_unique_type_for_nil, const strict_list<T>& a ) {
 532       return null(a)();
 533     }
 534     template <class T>
 535     bool operator==( const strict_list<T>& a, const strict_list<T>& b ) {
 536         if( null(a)() && null(b)() )
 537             return true;
 538         if( null(a)() || null(b)() )
 539             return false;
 540         return (head(a)()==head(b)()) &&
 541             (tail(a)()==tail(b)());
 542     }
 543
 544     template <class T>
 545     bool operator<( const strict_list<T>& a, const strict_list<T>& b ) {
 546       if( null(a)() && !null(b)() )  return true;
 547         if( null(b)() )                      return false;
 548         if( head(b)() < head(a)() )    return false;
 549         if( head(a)() < head(b)() )    return true;
 550         return (tail(a)() < tail(b)());
 551     }
 552     template <class T>
 553     bool operator<( const strict_list<T>&, a_unique_type_for_nil ) {
 554         return false;
 555     }
 556     template <class T>
 557     bool operator<( a_unique_type_for_nil, const strict_list<T>& b ) {
 558       return !(null(b)());
 559     }
 560
 561 //////////////////////////////////////////////////////////////////////
 562 // Class list<T> is the primary interface to the user for lazy lists.
 563 //////////////////////////////////////////////////////////////////////{
 564     namespace impl {
 565       using fcpp::INV;
 566       using fcpp::VAR;
 567       using fcpp::reuser2;
 568
 569       struct CacheEmpty {};
 570
 571       template <class T> class Cache;
 572       template <class T> class odd_list;
 573       template <class T> class list_iterator;
 574       template <class It, class T>
 575       struct ListItHelp2 /*: public c_fun_type<It,It,odd_list<T> >*/ {
 576         // This will need a return type.
 577         typedef odd_list<T> return_type;
 578         odd_list<T> operator()( It begin, const It& end,
 579           reuser2<INV,VAR,INV,ListItHelp2<It,T>,It,It> r = NIL ) const;
 580       };
 581       template <class U,class F> struct cvt;
 582       template <class T, class F, class R> struct ListHelp;
 583       template <class T> Cache<T>* xempty_helper();
 584       template <class T, class F, class L, bool b> struct ConsHelp2;
 585
 586       struct ListRaw {};
 587
 588       template <class T>
 589       class list : public listlike::ListLike
 590       {
 591         // never NIL, unless an empty odd_list
 592         boost::intrusive_ptr<Cache<T> > rep;
 593
 594         template <class U> friend class Cache;
 595         template <class U> friend class odd_list;
 596         template <class TT, class F, class L, bool b> friend struct ConsHelp2;
 597         template <class U,class F> friend struct cvt;
 598
 599         list( const boost::intrusive_ptr<Cache<T> >& p ) : rep(p) { }
 600         list( ListRaw, Cache<T>* p ) : rep(p) { }
 601
 602         bool priv_isEmpty() const {
 603           return rep->cache().second.rep == Cache<T>::XNIL();
 604         }
 605         T priv_head() const {
 606 #ifndef BOOST_PHOENIX_NO_LAZY_EXCEPTIONS
 607           if( priv_isEmpty() )
 608              throw lazy_exception("Tried to take head() of empty list");
 609 #endif
 610           return rep->cache().first();
 611         }
 612         list<T> priv_tail() const {
 613 #ifndef BOOST_PHOENIX_NO_LAZY_EXCEPTIONS
 614           if( priv_isEmpty() )
 615             throw lazy_exception("Tried to take tail() of empty list");
 616 #endif
 617           return rep->cache().second;
 618         }
 619
 620
 621       public:
 622         static const bool is_lazy = true;
 623
 624         typedef T value_type;
 625         typedef list tail_result_type;
 626         typedef odd_list<T> force_result_type;
 627         typedef list delay_result_type;
 628         template <class UU> struct cons_rebind {
 629            typedef odd_list<UU> type;
 630            typedef list<UU> delay_type;
 631         };
 632
 633         list( a_unique_type_for_nil ) : rep( Cache<T>::XEMPTY() ) { }
 634         list() : rep( Cache<T>::XEMPTY() ) { }
 635
 636         template <class F>  // works on both ()->odd_list and ()->list
 637         // At the moment this is fixed for odd_list<T>.
 638         // I need to do more work to get the general result.
 639         list( const F& f )
 640           : rep( ListHelp<T,F,odd_list<T> >()(f) ) { }
 641         //: rep( ListHelp<T,F,typename F::result_type>()(f) ) { }
 642
 643         operator bool() const { return !priv_isEmpty(); }
 644         const force_result_type& force() const { return rep->cache(); }
 645         const delay_result_type& delay() const { return *this; }
 646         // Note: force returns a reference;
 647         // implicit conversion now returns a copy.
 648         operator odd_list<T>() const { return force(); }
 649
 650         T head() const { return priv_head(); }
 651         tail_result_type tail() const { return priv_tail(); }
 652
 653         // The following helps makes list almost an STL "container"
 654         typedef list_iterator<T> const_iterator;
 655         typedef const_iterator iterator;         // list is immutable
 656         iterator begin() const { return list_iterator<T>( *this ); }
 657         iterator end() const   { return list_iterator<T>(); }
 658
 659         // end of list<T>
 660       };
 661
 662 //////////////////////////////////////////////////////////////////////
 663 // Class odd_list<T> is not normally accessed by the user.
 664 //////////////////////////////////////////////////////////////////////
 665
 666       struct OddListDummyY {};
 667
 668       template <class T>
 669       class odd_list : public listlike::ListLike
 670       {
 671       public:
 672         typedef
 673         typename boost::type_with_alignment<boost::alignment_of<T>::value>::type
 674         xfst_type;
 675       private:
 676         union { xfst_type fst; unsigned char dummy[sizeof(T)]; };
 677
 678         const T& first() const {
 679            return *static_cast<const T*>(static_cast<const void*>(&fst));
 680         }
 681         T& first() {
 682            return *static_cast<T*>(static_cast<void*>(&fst));
 683         }
 684         list<T>  second;   // If XNIL, then this odd_list is NIL
 685
 686         template <class U> friend class list;
 687         template <class U> friend class Cache;
 688
 689         odd_list( OddListDummyY )
 690           : second( Cache<T>::XBAD() ) { }
 691
 692         void init( const T& x ) {
 693            new (static_cast<void*>(&fst)) T(x);
 694         }
 695
 696         bool fst_is_valid() const {
 697            if( second.rep != Cache<T>::XNIL() )
 698               if( second.rep != Cache<T>::XBAD() )
 699                  return true;
 700            return false;
 701         }
 702
 703         bool priv_isEmpty() const { return second.rep == Cache<T>::XNIL(); }
 704         T priv_head() const {
 705 #ifndef BOOST_PHOENIX_NO_LAZY_EXCEPTIONS
 706            if( priv_isEmpty() )
 707              throw lazy_exception("Tried to take head() of empty odd_list");
 708 #endif
 709            return first();
 710         }
 711
 712         list<T> priv_tail() const {
 713 #ifndef BOOST_PHOENIX_NO_LAZY_EXCEPTIONS
 714            if( priv_isEmpty() )
 715              throw lazy_exception("Tried to take tail() of empty odd_list");
 716 #endif
 717            return second;
 718         }
 719
 720       public:
 721         static const bool is_lazy = true;
 722
 723         typedef T value_type;
 724         typedef list<T> tail_result_type;
 725         typedef odd_list<T> force_result_type;
 726         typedef list<T> delay_result_type;
 727         template <class UU> struct cons_rebind {
 728           typedef odd_list<UU> type;
 729           typedef list<UU> delay_type;
 730         };
 731
 732         odd_list() : second( Cache<T>::XNIL() ) { }
 733         odd_list( a_unique_type_for_nil ) : second( Cache<T>::XNIL() ) { }
 734         odd_list( const T& x, const list<T>& y ) : second(y) { init(x); }
 735         odd_list( const T& x, a_unique_type_for_nil ) : second(NIL) { init(x); }
 736
 737         odd_list( const odd_list<T>& x ) : second(x.second) {
 738            if( fst_is_valid() ) {
 739               init( x.first() );
 740            }
 741         }
 742
 743         template <class It>
 744         odd_list( It begin, const It& end )
 745           : second( begin==end ? Cache<T>::XNIL() :
 746              ( init(*begin++), list<T>( begin, end ) ) ) {}
 747
 748         odd_list<T>& operator=( const odd_list<T>& x ) {
 749            if( this == &x ) return *this;
 750            if( fst_is_valid() ) {
 751              if( x.fst_is_valid() )
 752                first() = x.first();
 753              else
 754                first().~T();
 755            }
 756            else {
 757               if( x.fst_is_valid() )
 758                  init( x.first() );
 759            }
 760            second = x.second;
 761            return *this;
 762         }
 763
 764        ~odd_list() {
 765           if( fst_is_valid() ) {
 766             first().~T();
 767           }
 768         }
 769
 770         operator bool() const { return !priv_isEmpty(); }
 771         const force_result_type& force() const { return *this; }
 772         delay_result_type delay() const { return list<T>(*this); }
 773
 774         T head() const { return priv_head(); }
 775         tail_result_type tail() const { return priv_tail(); }
 776
 777         // The following helps makes odd_list almost an STL "container"
 778         typedef list_iterator<T> const_iterator;
 779         typedef const_iterator iterator;         // odd_list is immutable
 780         iterator begin() const { return list_iterator<T>( this->delay() ); }
 781         iterator end() const   { return list_iterator<T>(); }
 782
 783         // end of odd_list<T>
 784       };
 785
 786 //////////////////////////////////////////////////////////////////////
 787 // struct cvt
 788 //////////////////////////////////////////////////////////////////////
 789
 790       // This converts ()->list<T> to ()->odd_list<T>.
 791       // In other words, here is the 'extra work' done when using the
 792       // unoptimized interface.
 793       template <class U,class F>
 794       struct cvt /*: public c_fun_type<odd_list<U> >*/ {
 795         typedef odd_list<U> return_type;
 796         F f;
 797         cvt( const F& ff ) : f(ff) {}
 798         odd_list<U> operator()() const {
 799            list<U> l = f();
 800            return l.force();
 801         }
 802       };
 803
 804
 805 //////////////////////////////////////////////////////////////////////
 806 // Cache<T> and associated functions.
 807 //////////////////////////////////////////////////////////////////////
 808
 809 // I malloc a RefCountType to hold the refCount and init it to 1 to ensure the
 810 // refCount will never get to 0, so the destructor-of-global-object
 811 // order at the end of the program is a non-issue.  In other words, the
 812 // memory allocated here is only reclaimed by the operating system.
 813     template <class T>
 814     Cache<T>* xnil_helper() {
 815        void *p = std::malloc( sizeof(RefCountType) );
 816        *((RefCountType*)p) = 1;
 817        return static_cast<Cache<T>*>( p );
 818     }
 819
 820     template <class T>
 821     Cache<T>* xnil_helper_nil() {
 822        Cache<T>* p = xnil_helper<T>();
 823        return p;
 824     }
 825
 826     template <class T>
 827     Cache<T>* xnil_helper_bad() {
 828        Cache<T>* p = xnil_helper<T>();
 829        return p;
 830     }
 831
 832     template <class T>
 833     Cache<T>* xempty_helper() {
 834        Cache<T>* p = new Cache<T>( CacheEmpty() );
 835        return p;
 836     }
 837
 838     // This makes a boost phoenix function type with return type
 839     // odd_list<T>
 840     template <class T>
 841     struct fun0_type_helper{
 842        typedef boost::function0<odd_list<T> > fun_type;
 843        typedef boost::phoenix::function<fun_type> phx_type;
 844     };
 845
 846
 847       template <class T>
 848       struct make_fun0_odd_list {
 849
 850         typedef typename fun0_type_helper<T>::fun_type fun_type;
 851         typedef typename fun0_type_helper<T>::phx_type phx_type;
 852         typedef phx_type result_type;
 853
 854         template <class F>
 855         result_type operator()(const F& f) const
 856         {
 857             fun_type ff(f);
 858             phx_type g(ff);
 859             return g;
 860         }
 861
 862         // Overload for the case where it is a boost phoenix function already.
 863         template <class F>
 864         typename boost::phoenix::function<F> operator()
 865           (const boost::phoenix::function<F>& f) const
 866         {
 867             return f;
 868         }
 869
 870     };
 871
 872     template <class T>
 873     class Cache : boost::noncopyable {
 874        mutable RefCountType refC;
 875        // This is the boost::function type
 876        typedef typename fun0_type_helper<T>::fun_type fun_odd_list_T;
 877        // This is the boost::phoenix::function type;
 878        typedef typename fun0_type_helper<T>::phx_type fun0_odd_list_T;
 879        mutable fun0_odd_list_T fxn;
 880        mutable odd_list<T>     val;
 881        // val.second.rep can be XBAD, XNIL, or a valid ptr
 882        //  - XBAD: val is invalid (fxn is valid)
 883        //  - XNIL: this is the empty list
 884        //  - anything else: val.first() is head, val.second is tail()
 885
 886        // This functoid should never be called; it represents a
 887        // self-referent Cache, which should be impossible under the current
 888        // implementation.  Nonetheless, we need a 'dummy' function object to
 889        // represent invalid 'fxn's (val.second.rep!=XBAD), and this
 890        // implementation seems to be among the most reasonable.
 891        struct blackhole_helper /*: c_fun_type< odd_list<T> >*/ {
 892           typedef odd_list<T> return_type;
 893           odd_list<T> operator()() const {
 894 #ifndef BOOST_PHOENIX_NO_LAZY_EXCEPTIONS
 895             throw lazy_exception("You have entered a black hole.");
 896 #else
 897             return odd_list<T>();
 898 #endif
 899           }
 900        };
 901
 902        // Don't get rid of these XFOO() functions; they impose no overhead,
 903        // and provide a useful place to add debugging code for tracking down
 904        // before-main()-order-of-initialization problems.
 905        static const boost::intrusive_ptr<Cache<T> >& XEMPTY() {
 906           static boost::intrusive_ptr<Cache<T> > xempty( xempty_helper<T>() );
 907           return xempty;
 908        }
 909        static const boost::intrusive_ptr<Cache<T> >& XNIL() {
 910        // this list is nil
 911           static boost::intrusive_ptr<Cache<T> > xnil( xnil_helper_nil<T>() );
 912           return xnil;
 913        }
 914
 915        static const boost::intrusive_ptr<Cache<T> >& XBAD() {
 916        // the pair is invalid; use fxn
 917           static boost::intrusive_ptr<Cache<T> > xbad( xnil_helper_bad<T>() );
 918           return xbad;
 919        }
 920
 921        static fun0_odd_list_T /*<odd_list<T> >*/ the_blackhole;
 922        static fun0_odd_list_T& blackhole() {
 923          static fun0_odd_list_T the_blackhole;
 924          //( make_fun0_odd_list<T>()( blackhole_helper() ) );
 925          return the_blackhole;
 926        }
 927
 928        odd_list<T>& cache() const {
 929          if( val.second.rep == XBAD() ) {
 930             val = fxn()();
 931             fxn = blackhole();
 932          }
 933          return val;
 934        }
 935
 936        template <class U> friend class list;
 937        template <class U> friend class odd_list;
 938        template <class TT, class F, class L, bool b> friend struct ConsHelp2;
 939        template <class U,class F> friend struct cvt;
 940        template <class U, class F, class R> friend struct ListHelp;
 941        template <class U> friend Cache<U>* xempty_helper();
 942
 943        Cache( CacheEmpty ) : refC(0), fxn(blackhole()), val() {}
 944        Cache( const odd_list<T>& x ) : refC(0), fxn(blackhole()), val(x) {}
 945        Cache( const T& x, const list<T>& l ) : refC(0),fxn(blackhole()),val(x,l)
 946           {}
 947
 948        Cache( const fun0_odd_list_T& f )
 949          : refC(0), fxn(f), val( OddListDummyY() ) {}
 950
 951        // f must be a boost phoenix function object?
 952        template <class F>
 953        Cache( const F& f )    // ()->odd_list
 954          : refC(0), fxn(make_fun0_odd_list<T>()(f)), val( OddListDummyY() ) {}
 955
 956        // This is for ()->list<T> to ()->odd_list<T>
 957        struct CvtFxn {};
 958        template <class F>
 959        Cache( CvtFxn, const F& f )    // ()->list
 960          :  refC(0), fxn(make_fun0_odd_list<T>()(cvt<T,F>(f))), val( OddListDummyY() ) {}
 961
 962        template <class X>
 963        friend void intrusive_ptr_add_ref( const Cache<X>* p );
 964        template <class X>
 965        friend void intrusive_ptr_release( const Cache<X>* p );
 966     };
 967
 968     template <class T>
 969     void intrusive_ptr_add_ref( const Cache<T>* p ) {
 970         ++ (p->refC);
 971     }
 972     template <class T>
 973     void intrusive_ptr_release( const Cache<T>* p ) {
 974         if( !--(p->refC) ) delete p;
 975     }
 976
 977 //////////////////////////////////////////////////////////////////////
 978 // Rest of list's stuff
 979 //////////////////////////////////////////////////////////////////////
 980
 981 template <class T, class F> struct ListHelp<T,F,list<T> > {
 982    boost::intrusive_ptr<Cache<T> > operator()( const F& f ) const {
 983       return boost::intrusive_ptr<Cache<T> >
 984          (new Cache<T>(typename Cache<T>::CvtFxn(),f));
 985    }
 986 };
 987 template <class T, class F> struct ListHelp<T,F,odd_list<T> > {
 988    boost::intrusive_ptr<Cache<T> > operator()( const F& f ) const {
 989       return boost::intrusive_ptr<Cache<T> >(new Cache<T>(f));
 990    }
 991 };
 992
 993 template <class T>
 994 class list_iterator
 995 : public std::iterator<std::input_iterator_tag,T,ptrdiff_t> {
 996    list<T> l;
 997    bool is_nil;
 998    void advance() {
 999       l = l.tail();
1000       if( !l )
1001          is_nil = true;
1002    }
1003    class Proxy {  // needed for operator->
1004       const T x;
1005       friend class list_iterator;
1006       Proxy( const T& xx ) : x(xx) {}
1007    public:
1008       const T* operator->() const { return &x; }
1009    };
1010 public:
1011    list_iterator() : l(), is_nil(true) {}
1012    explicit list_iterator( const list<T>& ll ) : l(ll), is_nil(!ll) {}
1013
1014    const T operator*() const { return l.head(); }
1015    const Proxy operator->() const { return Proxy(l.head()); }
1016    list_iterator<T>& operator++() {
1017       advance();
1018       return *this;
1019    }
1020    const list_iterator<T> operator++(int) {
1021       list_iterator<T> i( *this );
1022       advance();
1023       return i;
1024    }
1025    bool operator==( const list_iterator<T>& i ) const {
1026       return is_nil && i.is_nil;
1027    }
1028    bool operator!=( const list_iterator<T>& i ) const {
1029       return ! this->operator==(i);
1030    }
1031 };
1032
1033
1034     } // namespace impl
1035
1036   using impl::list;
1037   using impl::odd_list;
1038   using impl::list_iterator;
1039
1040 //////////////////////////////////////////////////////////////////////
1041 // op== and op<, overloaded for all combos of list, odd_list, and NIL
1042 //////////////////////////////////////////////////////////////////////
1043 // All of these null head and tail are now non lazy using e.g. null(a)().
1044 // They need an extra () e.g. null(a)().
1045
1046 // FIX THIS comparison operators can be implemented simpler with enable_if
1047 template <class T>
1048 bool operator==( const odd_list<T>& a, a_unique_type_for_nil ) {
1049   return null(a)();
1050 }
1051 template <class T>
1052 bool operator==( const list<T>& a, a_unique_type_for_nil ) {
1053   return null(a)();
1054 }
1055 template <class T>
1056 bool operator==( a_unique_type_for_nil, const odd_list<T>& a ) {
1057   return null(a)();
1058 }
1059 template <class T>
1060 bool operator==( a_unique_type_for_nil, const list<T>& a ) {
1061   return null(a)();
1062 }
1063 template <class T>
1064 bool operator==( const list<T>& a, const list<T>& b ) {
1065   if( null(a)() && null(b)() )
1066       return true;
1067   if( null(a)() || null(b)() )
1068       return false;
1069   return (head(a)()==head(b)()) && (tail(a)()==tail(b)());
1070 }
1071 template <class T>
1072 bool operator==( const odd_list<T>& a, const odd_list<T>& b ) {
1073   if( null(a)() && null(b)() )
1074       return true;
1075   if( null(a)() || null(b)() )
1076       return false;
1077   return (head(a)()==head(b)()) && (tail(a)()==tail(b)());
1078 }
1079 template <class T>
1080 bool operator==( const list<T>& a, const odd_list<T>& b ) {
1081   if( null(a)() && null(b)() )
1082       return true;
1083   if( null(a)() || null(b)() )
1084       return false;
1085   return (head(a)()==head(b)()) && (tail(a)()==tail(b)());
1086 }
1087 template <class T>
1088 bool operator==( const odd_list<T>& a, const list<T>& b ) {
1089   if( null(a)() && null(b)() )
1090       return true;
1091   if( null(a)() || null(b)() )
1092       return false;
1093   return (head(a)()==head(b)()) && (tail(a)()==tail(b)());
1094 }
1095
1096 template <class T>
1097 bool operator<( const list<T>& a, const list<T>& b ) {
1098   if( null(a)() && !null(b)() )  return true;
1099   if( null(b)() )              return false;
1100   if( head(b)() < head(a)() )    return false;
1101   if( head(a)() < head(b)() )    return true;
1102   return (tail(a)() < tail(b)());
1103 }
1104 template <class T>
1105 bool operator<( const odd_list<T>& a, const list<T>& b ) {
1106   if( null(a)() && !null(b)() )  return true;
1107   if( null(b)() )              return false;
1108   if( head(b)() < head(a)() )    return false;
1109   if( head(a)() < head(b)() )    return true;
1110   return (tail(a)() < tail(b)());
1111 }
1112 template <class T>
1113 bool operator<( const list<T>& a, const odd_list<T>& b ) {
1114    if( null(a) && !null(b) )  return true;
1115    if( null(b) )              return false;
1116    if( head(b) < head(a) )    return false;
1117    if( head(a) < head(b) )    return true;
1118    return (tail(a) < tail(b));
1119 }
1120 template <class T>
1121 bool operator<( const odd_list<T>& a, const odd_list<T>& b ) {
1122   if( null(a)() && !null(b)() )  return true;
1123   if( null(b)() )              return false;
1124   if( head(b)() < head(a)() )    return false;
1125   if( head(a)() < head(b)() )    return true;
1126   return (tail(a)() < tail(b)());
1127 }
1128 template <class T>
1129 bool operator<( const odd_list<T>&, a_unique_type_for_nil ) {
1130    return false;
1131 }
1132 template <class T>
1133 bool operator<( const list<T>&, a_unique_type_for_nil ) {
1134    return false;
1135 }
1136 template <class T>
1137 bool operator<( a_unique_type_for_nil, const odd_list<T>& b ) {
1138   return !null(b)();
1139 }
1140 template <class T>
1141 bool operator<( a_unique_type_for_nil, const list<T>& b ) {
1142   return !null(b)();
1143 }
1144
1145 //////////////////////////////////////////////////////////////////////
1146 // Implement cat and cons after the list types are defined.
1147 //////////////////////////////////////////////////////////////////////
1148     namespace impl {
1149       using listlike::ListLike;
1150
1151       template <class T, class F, class L>
1152       struct ConsHelp2<T,F,L,true>
1153       {
1154          typedef typename boost::remove_reference<T>::type TT;
1155          typedef typename L::force_result_type type;
1156          static type go( const TT& x, const F& f ) {
1157             return type( x, f );
1158          }
1159       };
1160       template <class T, class F>
1161       struct ConsHelp2<T,F,list<T>,true>
1162       {
1163          typedef typename boost::remove_reference<T>::type TT;
1164          typedef list<TT> L;
1165          typedef typename L::force_result_type type;
1166          static type go( const TT& x, const F& f ) {
1167             return odd_list<TT>(x, list<TT>(
1168             boost::intrusive_ptr<Cache<TT> >(new Cache<T>(
1169             typename Cache<TT>::CvtFxn(),f))));
1170          }
1171        };
1172        template <class T, class F>
1173        struct ConsHelp2<T,F,odd_list<T>,true>
1174        {
1175           typedef typename boost::remove_reference<T>::type TT;
1176           typedef odd_list<TT> L;
1177           typedef typename L::force_result_type type;
1178           static type go( const TT& x, const F& f ) {
1179               return odd_list<TT>(x, list<TT>( ListRaw(), new Cache<T>(f) ));
1180           }
1181        };
1182        template <class T, class F>
1183        struct ConsHelp2<T,F,a_unique_type_for_nil,false>
1184        {
1185           typedef typename boost::remove_reference<T>::type TT;
1186           typedef odd_list<TT> type;
1187           static type go( const TT& x, const F& f ) {
1188              return odd_list<TT>(x, list<TT>( ListRaw(), new Cache<T>(f) ));
1189           }
1190        };
1191
1192        template <class T, class L, bool b> struct ConsHelp1 {
1193           typedef typename boost::remove_reference<T>::type TT;
1194           typedef typename L::force_result_type type;
1195           static type go( const TT& x, const L& l ) {
1196              return type(x,l);
1197           }
1198        };
1199       template <class T> struct ConsHelp1<T,a_unique_type_for_nil,false> {
1200         typedef typename boost::remove_reference<T>::type TT;
1201         typedef odd_list<TT> type;
1202         static type go( const TT& x, const a_unique_type_for_nil& n ) {
1203         return type(x,n);
1204         }
1205       };
1206       template <class T, class F> struct ConsHelp1<T,F,false> {
1207         // It's a function returning a list
1208         // This is the one I have not fixed yet....
1209         // typedef typename F::result_type L;
1210         // typedef typename result_of::template ListType<F>::result_type L;
1211         typedef odd_list<T> L;
1212         typedef ConsHelp2<T,F,L,boost::is_base_and_derived<ListLike,L>::value> help;
1213         typedef typename help::type type;
1214         static type go( const T& x, const F& f ) {
1215            return help::go(x,f);
1216         }
1217       };
1218
1219       template <class T, class L, bool b>
1220       struct ConsHelp0;
1221
1222       template <class T>
1223       struct ConsHelp0<T,a_unique_type_for_nil,true> {
1224         typedef typename boost::remove_reference<T>::type TT;
1225         typedef odd_list<T> type;
1226       };
1227
1228       template <class T>
1229       struct ConsHelp0<const T &,const a_unique_type_for_nil &,true> {
1230         typedef typename boost::remove_reference<T>::type TT;
1231         typedef odd_list<TT> type;
1232       };
1233
1234       template <class T>
1235       struct ConsHelp0<T &,a_unique_type_for_nil &,true> {
1236         typedef typename boost::remove_reference<T>::type TT;
1237         typedef odd_list<TT> type;
1238       };
1239
1240       template <class T, class L>
1241       struct ConsHelp0<T,L,false> {
1242           // This removes any references from L for correct return type
1243           // identification.
1244            typedef typename boost::remove_reference<L>::type LType;
1245            typedef typename ConsHelp1<T,LType,
1246            boost::is_base_and_derived<ListLike,LType>::value>::type type;
1247       };
1248
1249       /////////////////////////////////////////////////////////////////////
1250       // cons (t,l) - cons a value to the front of a list.
1251       // Note: The first arg,  t, must be a value.
1252       //       The second arg, l, can be a list or NIL
1253       //       or a function that returns a list.
1254       /////////////////////////////////////////////////////////////////////
1255       struct Cons
1256       {
1257         /* template <class T, class L> struct sig : public fun_type<
1258         typename ConsHelp1<T,L,
1259       boost::is_base_and_derived<ListLike,L>::value>::type> {};
1260         */
1261         template <typename Sig> struct result;
1262
1263         template <typename This, typename T, typename L>
1264         struct result<This(T, L)>
1265         {
1266           typedef typename ConsHelp0<T,L,
1267           listlike::detect_nil<L>::is_nil>::type type;
1268         };
1269
1270         template <typename This, typename T>
1271         struct result<This(T,a_unique_type_for_nil)>
1272         {
1273           typedef typename boost::remove_reference<T>::type TT;
1274           typedef odd_list<TT> type;
1275         };
1276
1277         template <typename T, typename L>
1278         typename result<Cons(T,L)>::type
1279         operator()( const T& x, const L& l ) const {
1280            typedef typename result_of::ListType<L>::LType LType;
1281            typedef ConsHelp1<T,LType,
1282            boost::is_base_and_derived<ListLike,LType>::value> help;
1283            return help::go(x,l);
1284           }
1285
1286         template <typename T>
1287         typename result<Cons(T,a_unique_type_for_nil)>::type
1288         operator()( const T& x, const a_unique_type_for_nil &n ) const {
1289            typedef typename result<Cons(T,a_unique_type_for_nil)>::type LL;
1290            typedef ConsHelp1<T,LL,
1291            boost::is_base_and_derived<ListLike,LL>::value> help;
1292            return help::go(x,n);
1293           }
1294
1295       };
1296     }
1297
1298     typedef boost::phoenix::function<impl::Cons> Cons;
1299     Cons cons;
1300
1301     namespace impl {
1302
1303       template <class L, class M, bool b>
1304       struct CatHelp0;
1305
1306       template <class LL>
1307       struct CatHelp0<LL,a_unique_type_for_nil,true> {
1308         typedef typename result_of::template ListType<LL>::LType type;
1309       };
1310
1311       template <class LL>
1312       struct CatHelp0<const LL &,const a_unique_type_for_nil &,true> {
1313         typedef typename result_of::template ListType<LL>::LType type;
1314         //typedef L type;
1315       };
1316
1317       template <class LL>
1318       struct CatHelp0<LL &,a_unique_type_for_nil &,true> {
1319         typedef typename result_of::template ListType<LL>::LType type;
1320         //typedef L type;
1321       };
1322
1323       template <class LL, class MM>
1324       struct CatHelp0<LL,MM,false> {
1325           // This removes any references from L for correct return type
1326           // identification.
1327         typedef typename result_of::template ListType<LL>::LType type;
1328         //    typedef typename ConsHelp1<T,LType,
1329         //   boost::is_base_and_derived<ListLike,LType>::value>::type type;
1330       };
1331
1332       /////////////////////////////////////////////////////////////////////
1333       // cat (l,m) - concatenate lists.
1334       // Note: The first arg,  l, must be a list or NIL.
1335       //       The second arg, m, can be a list or NIL
1336       //       or a function that returns a list.
1337       /////////////////////////////////////////////////////////////////////
1338       struct Cat
1339       {
1340          template <class L, class M, bool b, class R>
1341          struct Helper /*: public c_fun_type<L,M,R>*/ {
1342            template <typename Sig> struct result;
1343
1344            template <typename This>
1345            struct result<This(L,M)>
1346           {
1347              typedef typename result_of::ListType<L>::tail_result_type type;
1348           };
1349
1350            typedef R return_type;
1351            R operator()( const L& l, const M& m,
1352              reuser2<INV,VAR,INV,Helper,
1353              typename result_of::template ListType<L>::tail_result_type,M>
1354              r = NIL ) const {
1355              if( null(l)() )
1356                 return m().force();
1357              else
1358                 return cons( head(l)(), r( Helper<L,M,b,R>(), tail(l), m )() );
1359          }
1360       };
1361           template <class L, class M, class R>
1362           struct Helper<L,M,true,R> /*: public c_fun_type<L,M,R>*/ {
1363            template <typename Sig> struct result;
1364
1365            template <typename This>
1366            struct result<This(L,M)>
1367           {
1368              typedef typename result_of::ListType<L>::tail_result_type type;
1369           };
1370           typedef R return_type;
1371           R operator()( const L& l, const M& m,
1372              reuser2<INV,VAR,INV,Helper,
1373              typename result_of::template ListType<L>::tail_result_type,M>
1374              r = NIL ) const {
1375              if( null(l)() )
1376                 return m.force();
1377              else
1378                 return cons( head(l)(), r(Helper<L,M,true,R>(), tail(l), m )());
1379          }
1380       };
1381       template <class L, class R>
1382       struct Helper<L,a_unique_type_for_nil,false,R>
1383       /*: public c_fun_type<L,
1384         a_unique_type_for_nil,odd_list<typename L::value_type> > */
1385       {
1386         typedef odd_list<typename result_of::template ListType<L>::value_type> type;
1387         odd_list<typename result_of::template ListType<L>::value_type>
1388         operator()( const L& l, const a_unique_type_for_nil& ) const {
1389          return l;
1390         }
1391       };
1392    public:
1393         /*template <class L, class M> struct sig : public fun_type<
1394         typename RT<cons_type,typename L::value_type,M>::result_type>
1395       {}; */
1396    // Need to work out the return type here.
1397       template <typename Sig> struct result;
1398
1399       template <typename This, typename L, typename M>
1400       struct result<This(L,M)>
1401       {
1402         typedef typename CatHelp0<L,M,
1403           listlike::detect_nil<M>::is_nil>::type type;
1404         // typedef typename result_of::ListType<L>::tail_result_type type;
1405       };
1406
1407       template <typename This, typename L>
1408       struct result<This(L,a_unique_type_for_nil)>
1409       {
1410          typedef typename result_of::ListType<L>::tail_result_type type;
1411       };
1412       template <class L, class M>
1413       typename result<Cat(L,M)>::type operator()( const L& l, const M& m ) const
1414       {
1415          listlike::EnsureListLike<L>();
1416          return Helper<L,M,
1417          boost::is_base_and_derived<typename listlike::ListLike,M>::value,
1418                 typename result<Cat(L,M)>::type>()(l,m);
1419       }
1420
1421       template <class L>
1422       typename result<Cat(L,a_unique_type_for_nil)>::type operator()( const L& l, const a_unique_type_for_nil& /* n */ ) const
1423       {
1424          listlike::EnsureListLike<L>();
1425          return l;
1426       }
1427
1428       };
1429
1430
1431     }
1432
1433     typedef boost::phoenix::function<impl::Cat> Cat;
1434     Cat cat;
1435
1436
1437 //////////////////////////////////////////////////////////////////////
1438 // Handy functions for making list literals
1439 //////////////////////////////////////////////////////////////////////
1440 // Yes, these aren't functoids, they're just template functions.  I'm
1441 // lazy and created these mostly to make it easily to make little lists
1442 // in the sample code snippets that appear in papers.
1443
1444 struct UseList {
1445    template <class T> struct List { typedef list<T> type; };
1446 };
1447 struct UseOddList {
1448    template <class T> struct List { typedef odd_list<T> type; };
1449 };
1450 struct UseStrictList {
1451    template <class T> struct List { typedef strict_list<T> type; };
1452 };
1453
1454 template <class Kind = UseList>
1455 struct list_with {
1456    template <class T>
1457    typename Kind::template List<T>::type
1458    operator()( const T& a ) const {
1459       typename Kind::template List<T>::type l;
1460       l = cons( a, l );
1461       return l;
1462    }
1463
1464    template <class T>
1465    typename Kind::template List<T>::type
1466    operator()( const T& a, const T& b ) const {
1467       typename Kind::template List<T>::type l;
1468       l = cons( b, l );
1469       l = cons( a, l );
1470       return l;
1471    }
1472
1473    template <class T>
1474    typename Kind::template List<T>::type
1475    operator()( const T& a, const T& b, const T& c ) const {
1476       typename Kind::template List<T>::type l;
1477       l = cons( c, l );
1478       l = cons( b, l );
1479       l = cons( a, l );
1480       return l;
1481    }
1482
1483    template <class T>
1484    typename Kind::template List<T>::type
1485    operator()( const T& a, const T& b, const T& c, const T& d ) const {
1486       typename Kind::template List<T>::type l;
1487       l = cons( d, l );
1488       l = cons( c, l );
1489       l = cons( b, l );
1490       l = cons( a, l );
1491       return l;
1492    }
1493
1494    template <class T>
1495    typename Kind::template List<T>::type
1496    operator()( const T& a, const T& b, const T& c, const T& d,
1497                const T& e ) const {
1498       typename Kind::template List<T>::type l;
1499       l = cons( e, l );
1500       l = cons( d, l );
1501       l = cons( c, l );
1502       l = cons( b, l );
1503       l = cons( a, l );
1504       return l;
1505    }
1506 };
1507 //////////////////////////////////////////////////////////////////////
1508
1509   }
1510
1511 }
1512
1513 #endif