io.github.frenchy64.fully-satisfies.head-releasing

Variants of clojure.core functions (and internal helpers)
that release the head of seqs earlier, enabling lower peak memory
usage in some cases.

For example, many higher-order functions in this namespace release strong
references to arguments before calling their function arguments.
Realizing the following example would be prone to failure with an OutOfMemoryError using
clojure.core/map because map retains a strong reference to takes-75-percent-of-heap
when calling its function argument, which prevents memory from being reclaimed to create
another value of that size.

(map (fn [takes-75-percent-of-heap]
       (if (< (rand) 0.5)
         takes-75-percent-of-heap
         (generate-another-value-taking-75-percent-of-heap)))
     [takes-75-percent-of-heap])

In contrast, using head-releasing/map, the garbage collector can reclaim takes-75-percent-of-heap
while calculating (generate-another-value-taking-75-percent-of-heap) because
head-releasing/map does not strongly reference takes-75-percent-of-heap at that point.

The basic implementation trick to achieving this is to call (rest s) on the seq currently
being processed _before_ calling (f (first f)), so the strong reference to (first f)
is transferred from the higher-order function to f during the call to f.

There are potential caveats to this approach: https://clojure.org/reference/lazy#_extension_iseqs
If the underlying ISeq implementation defines rest in terms of next as in the article, then the
functions in this namespace will force two seq elements into memory simultaneously.
For example, the call below will throw an OutOfMemoryError before the fn is called because both
elements of the seq will be realized.

(map (fn [takes-75-percent-of-heap] nil)
     (lazy-seq-where-rest-calls-next
       (cons (->takes-75-percent-of-heap)
             (lazy-seq [(->takes-75-percent-of-heap)]))))

Infinite lazy seqs such as cycle or repeat always hold strong references to all their elements, so
the functions in this namespace will have no affect in the memory usage of processing these seqs.

Another caveat is that the functions here are perhaps more useful as
validation of the leaky-seq-detection framework and for pedalogical purposes about sequences
than as significant bump in real-world expressivity.
See the tests for how these implementations were verified:
  io.github.frenchy64.fully-satisfies.leaky-seq-detection-test

The author of this namespace can only speculate why the original functions were written this way.
Perhaps the idea of a fn releasing a strong reference to one of its arguments was too rare to risk
the caveats in using the default implementation of ISeq. Chunked seqs are also so prevalent
and have much higher memory requirements that the optimizations in this namespace might
have been deemed insignificant. For example, map processing a chunk of 32 must have enough memory
to hold both 32 elements of the input collection and 32 elements of the output collection simultaneously.
Chunked seqs also make programs such as the above unidiomatic since they are so difficult to get right
(see the hoops math.combinatorics jumps through to reduce the 32+32 elements of the previous example to
32+1).

At the very least, this work helps crystallize the differences between rest and next---or
more precisely, their similarities: while rest does not realize the next element, nor tell us whether
a seq has more elements, it is still an eager operation whose result, like next, releases a strong
reference to the first element of the seq.

every?

added in 1.0

(every? pred coll)
Returns true if (pred x) is logical true for every x in coll, else
false.

head-releasing/every? is additionally:
- thread-safe for mutable collections
- does not hold strong reference to argument of pred when it is called.

keep

added in 1.2

(keep f)(keep f coll)
Returns a lazy sequence of the non-nil results of (f item). Note,
this means false return values will be included.  f must be free of
side-effects.  Returns a transducer when no collection is provided.

Additionally, head-releasing/keep does not hold a strong reference
to the argument of f when it is called (unless a single chunked seq coll is provided).

keep-indexed

added in 1.2

(keep-indexed f)(keep-indexed f coll)
Returns a lazy sequence of the non-nil results of (f index item). Note,
this means false return values will be included.  f must be free of
side-effects.  Returns a stateful transducer when no collection is
provided.

Additionally, head-releasing/keep-indexed does not hold a strong reference
to the argument of f when it is called (unless a single chunked seq coll is provided).

map

added in 1.0

(map f)(map f coll)(map f c1 c2)(map f c1 c2 c3)(map f c1 c2 c3 & colls)
Returns a lazy sequence consisting of the result of applying f to
the set of first items of each coll, followed by applying f to the
set of second items in each coll, until any one of the colls is
exhausted.  Any remaining items in other colls are ignored. Function
f should accept number-of-colls arguments. Returns a transducer when
no collection is provided.

Additionally, head-releasing/map does not hold a strong reference
to the arguments of f when it is called (unless a single chunked seq coll is provided).

map-indexed

added in 1.2

(map-indexed f)(map-indexed f coll)
Returns a lazy sequence consisting of the result of applying f to 0
and the first item of coll, followed by applying f to 1 and the second
item in coll, etc, until coll is exhausted. Thus function f should
accept 2 arguments, index and item. Returns a stateful transducer when
no collection is provided.

Additionally, head-releasing/map-indexed does not hold a strong reference
to the argument of f when it is called (unless a single chunked seq coll is provided).

mapcat

added in 1.0

(mapcat f)(mapcat f & colls)
Returns the result of applying concat to the result of applying map
to f and colls.  Thus function f should return a collection. Returns
a transducer when no collections are provided.

Additionally, head-releasing/mapcat does not hold strong references to
the arguments of f when it is called (unless a single chunked seq coll is provided).

naive-seq-reduce

(naive-seq-reduce s f val)
Reduces a seq, ignoring any opportunities to switch to a more
specialized implementation.

Additionally, head-releasing/naive-seq-reduce does not retain
a strong reference to the arguments of f when it is called.

not-any?

added in 1.0

(not-any? pred coll)
Returns false if (pred x) is logical true for any x in coll,
else true.
      
Additionally, head-releasing/not-any? does not hold a strong reference
to the argument of pred when it is called.

not-every?

added in 1.0

(not-every? pred coll)
Returns false if (pred x) is logical true for every x in
coll, else true.

Additionally, head-releasing/not-every? does not hold a strong reference
to the argument of pred when it is called.

some

added in 1.0

(some pred coll)
Returns the first logical true value of (pred x) for any x in coll,
else nil.  One common idiom is to use a set as pred, for example
this will return :fred if :fred is in the sequence, otherwise nil:
(some #{:fred} coll)

Additionally, head-releasing/some does not hold a strong reference
to the argument of pred when it is called.