Folding in c++

Today’s post is short and sweet, like a peach.

On the odd chance you’re morbidly curious how to fold an array with a function in c++ like myself, you’re in for a pleasant surprise (unless you’re intimately familiar with boost’s lambdas, in which case you will be appalled at how little thought was put into this whimsical hack).

This morning I cleaned up my proj (fork it) utility library and added an Array structure with a foldRight member, and refactored curry to take in either a va_arg parameter list or a mArray of functions.

I make no claims about its stability or memory non-leakiness of the data structure although a hundred million delete and allocation calls had a stable memory footprint.

It all starts with Fptr.h:

the new hotness of mArray.h (I pronounce it emory as in memory)

the test program for folding, sort.cpp (naming fail now it sorts too):

the test program for curry:

Side note: I had some trouble embedding javascript directly in this post but I hacked together a gist which makes gists wider, and in a metatastic way it makes itself wider:

Here’s the scripts I included below:

Related posts:



Be Sociable, Share!

Categories: Uncategorized
Tags: ,
  • Pingback: First Steps Sorting out Python — Victus Spiritus

  • John Haugeland

    This has to be the densest, most garbage-ridden attempt to reinvent std::accumulate() I’ve ever seen.

    More proof that you need to think really, really hard before listening to a blogger.

  • http://www.victusspiritus.com/ Mark Essel

    John have you implemented or read through STD::accumulate? I just heard of it from another commenter recently and would love to hear some experienced insight on it’s impl.

    I was experimenting with functions calling functions. It works but I made no claims it was the only, best or even good way to do it. What didn’t you like about the way I did it?

  • Linux Jon

    I can see Johns point, even if he is a little harsh. Just look at some mArray implementation issues:

    Exposing namespace std in a header file.
    Use of long instead of size_t for unsigned quantities.
    Your members should be named like the stl, e.g. nuke() should be clear().
    No STL like typedefs for size_type, iterators, value_type etc.
    Exits the program rather than throwing exceptions, although can still throw exceptions through operator new.
    Bizarre semantics (copy with NULL pointer doesn’t do anything?).
    C style variable declarations (put the variable in the for loop).
    Public internal functions.
    Operator= doesn’t check for self assignment.
    Protected members but no virtual dtor – make them private if you don’t want people to inherit from it.

    I could go on, but as John points out, this code doesn’t need to be written at all.

    > But template functions (like my array) are not POD and so aren’t supported by this.

    Its a template class, not a function. And accumulate doesn’t require POD data.

    Good luck on your travels through c++.

  • http://www.victusspiritus.com/ Mark Essel

    Great feedback!
    I have heard exposing STD namespace in headers was poor form, but never practically experienced why. Mind explaining the thinking here?

    long use is admittedly old habit, size_t or unsigned long would be a fine choice. Negatives enable circular ques derived from something like this structure.

    Throw vs exception, again for my purposes either is acceptable. I prefer a full stop when classes are misused or memory allocation fails, as it is usually a systemic failure.

    If I tell you to copy nothing, I should hope you’d do nothing :). How’s that bizarre?

    I reuse the looping vars in larger programs, sometimes breaking ou of loops and keeping knowledge of when, again old habit.

    Not checking for self assignment was poor form. I should have done that automatically, great catch! I’ve been wrestling for months at work with models far removed from low level data structures.

    Naming- if nuke makes no surprises over clear, renaming it isn’t an issue. I wasn’t looking at existing stl formats at the time, just coding from what I wanted out of an array structure. I erred on the side of least surprise with a unique name.

    stl typedefs, hmm. I’ll have to look in to the value of such.

    Appreciate the feedback.

    Although the code is written elsewhere, doesn’t mean the experience of writing it yourself isn’t worth doing. Stepping through stl or boost code can be an exercise in patience, it has its costs.

  • Jon

    > Mind explaining the thinking here?
    It creates abiguity for users of your header who have clashing types/variables in their own namespace.

    If you are thinking about indexing using negative numbers for indexing you aren’t really in the c++ mindset I’d wager. You should be using insert_iterators and reverse iterators to go backwards/add backwards. Indexing is generally poor form compared to using iterators/algorithms (e.g. std::accumulate/std::transform as pointed out above).

    >If I tell you to copy nothing, I should hope you’d do nothing :). How’s that bizarre?

    Null is semantically different from an empty collection. Allowing NULL to propigate through your programs is generally a bad idea, particularly in larger apps. You cannot tell an invalid ptr from an empty collection.

    The value of providing stl compatible methods and typedefs is that you don’t need to document your classes as heavily, and std algorithms will work on them automatically.

  • http://www.victusspiritus.com/ Mark Essel

    I can appreciate the commonality of stl iteration over any supporting collections, even if I’m rusty at using stl structures (recently that’s changed in the last 2-3 months, maps of key/ptrs come in handy).

    As to corrupting namespaces, I recognize the importance as code bases grow, I just haven’t run into naming problems too often. In the past we used names like (Lib)(Utility) to avoid conflicts. Only in my current integration work have I had to really be careful with our older libraries includes. I’ll do a full sweep on namespaces in headers, based on your feedback. I don’t want to step on other folks vector definitions because I lazily added using namespace std in headers. The one bonus is that it kept us from ever reusing stl reserved class names.

    Thanks again for taking time to explain your rationale.