Is there any way to process a changing list using higher-order functions in Clojure and not using explicit recursion? For example, consider the following problem (that I made up to illustrate what I have in mind):
Problem: Given a list of unique integers of unknown order. Write a that produces an output list as follows:
- For any even integer, keep the same relative position in the output list.
- For any odd integer, multiply by ten, and put the new number at a new place: at the back of the original list.
So for example, from original vector [1 2 3 4 5], we get: [2 4 10 30 50]
I know how to solve this using explicit recursion. For example:
(defn process
[v]
(loop
[results []
remaining v]
(if (empty? remaining)
results
(if (even? (first remaining))
(recur (conj results (first remaining)) (rest remaining))
(recur results (conj (vec (rest remaining)) (* 10 (first remaining))))))))
This works fine. Notice that remaining changes as the function does its work. I'm doing the housekeeping here too: shuffling elements from remaining to results. What I would like to do is use a higher-order function that does the housekeeping for me. For example, if remaining did not change as the function does its work, I would use reduce and just kick off the process without worrying about loop or recur.
So my question is: is there any way to process an input (in this example, v) that changes over the course of its operations, using a higher-order function?
(Side note for more context: this question was inspired by Advent of Code 2020, Question 7, first part. There, the natural way to approach it, is to use recursion. I do here (in the find-all-containers function; which is the same way other have approached it, for example, here in the find-outer-bags function, or here in the sub-contains? function.)
This is much easier to do without recursion than with it! Since you only care about the order of evens relative to other evens, and likewise for odds, you can start by splitting the list in two. Then, map the right function over each, and simply concatenate the results.
(defn process [xs]
(let [evens (filter even? xs)
odds (filter odd? xs)]
(concat evens (map #(* 10 %) odds))))
As to the advent of code problem, I recommend working with a better data structure than a list or a vector. A map is a better way to represent what's going on, because you can easily look up the properties of each sub-bag by name. If you have a map from bag color to contents, you can write a simple (recursive) function that asks: "Can color a contain color b?" For leaf nodes the answer is no, for nodes equal to the goal color it's yes, and for branches you recurse on the contents.