Thank you for the kind words. I cannot comment on the performance hit yet but this is something I plan to examine soon. Based on experience I can guess that the performance decrease from using recursion could be about an order of magnitude or more for large arrays. Fortran really shines performance-wise when applied to heavy computations on very large multi-dimensional arrays - I don't think functional techniques should be applied in such cases. However, I think that Fortran programmers can benefit by applying functional techniques on parts of code that do a lot of complex logic but are not computationally heavy. Pareto principle is especially valid in HPC Fortran codes - most compute time is spent in a small % of code base. Those should be left alone.
One of the issues that really leaped out at me was head and tail. In the functional paradigms where those are common, they're both O(1) because they apply to cons lists, which are a form of linked list. Head is probably still O(1) but if tail is O(n) you really need to point that out, as even with relatively small data sets O(n^2) can be noticeable.
Perhaps it's obvious to a Fortran programmer that it will be O(1) because Fortran has slicing built in, I dunno, but still, documenting the general space and time complexity would be worth doing. (Plus even if Fortran does slices natively, it's still nice in a library like this to guarantee to your users that you're using it correctly and it won't copy n-1 elements on every call, and to clearly say whether they can safely modify the results. As I assume Fortran is not big on the immutable arrays.)
in the implementation of the tail_xxx functions does allocate a new array.
I wrote a test program to use foldl to calculate the sum of an array, and it seems to have n^2 time complexity. Also a test program summing an array of length 10000 of 64bit integers uses 395816 kbytes of memory, which is close to 8 * 10000^2 / 2 / 1024 = 390625.
Thank you jerf and sampo for your very helpful comments. This is something that I had on my mind during the implementation but focused primarily on expressiveness.
While the array slicing in Fortran is O(1), the implementation of tail does make a copy. Though a good compiler should be able to replace tail(x) with x(2:), the Fortran standard does not guarantee it to do so. The first step forward that I see would be to replace tail(x) with x(2:) in the internal implementations of fold[lr].
In any case, the time complexity for these functions is definitely something I plan to document soon.
> replace tail(x) with x(2:) in the internal implementations of fold[lr].
Tried this for foldl with gfortran. Totally helps. Summing 10 000 int64's, memory consumption drops from 400M to 4M. Also time complexity becomes linear.
I don't see what's basically wrong with functional approaches to array programming; see the APL family and SISAL?
There is, or was, a definite problem with recursion in gfortran (when I looked some time ago). You can't (or couldn't, then) get tail call elimination in functions. I'd have hoped GCC would have been able to see through the structure of the assignment/return.
I really like your project. I do question its usefulness however. If you get any performance hit from using these, you beat the point of using Fortran (over say Python) in the first place :) Don't you think?
Yes, and having worked with Fortran code for years, we used the routines to calculate... and Python to analyze the data. A colleague even scrapped old Fortran routines in favor of Python + Numpy, as he could be more productive without a noticeable slowdown in his work, as the data analysis part was the bottleneck. So I reiterate my point: I like the project, I like the idea, but we need more information regarding the performance of the routines. Otherwise, using e.g. Python full-stack could be much less of a hassle.
Did you miss the point the OP just made above? Performance-critical code paths can be left alone while the usual set-up/tear-down code can make good use of this library.
