News for hackers. Stuff that matters.
Re:Show HN: Functional programming for modern Fortran by jerf on Wednesday November 23, 2016 @11:10PM (#13028000)
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.)

Re:Show HN: Functional programming for modern Fortran by sampo on Thursday November 24, 2016 @02:01AM (#13028727)
I am afraid the line

    tail = x(2:)
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.

Re:Show HN: Functional programming for modern Fortran by milancurcic on Thursday November 24, 2016 @08:02AM (#13030084)
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.

Re:Show HN: Functional programming for modern Fortran by sampo on Thursday November 24, 2016 @11:49AM (#13031244)
> 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.