Dynamic programming in q?

Community Support
1

A classic mechanism for functional programs to implement DP is via lazy evaluation – so all the subproblems are not evaluated until they are needed. Furthermore, a local state is usually required to cache solutions to each evaluated subproblem.

In q, however, neither lazy evaluation nor local state is possible. I could implement a DP algorithm using global state (as in a global variable), but that prevents my DP algorithm from being parallelized – since non-main threads are not allowed to make global modifications.

Does any one have experience/idea regarding efficient implementation of DP algorithms using q?

2

FWIW, I’ve only managed to implement a DP-based optimal path search algorithm using do[;] loops, which is a bit a code smell in q. Alternatively, any use of q adverbs require me to encapsulate my iterative logic inside a function, which cannot use any local state (as expressed previously, global state is not an option due to need for parallel execution). Does anyone have any insights into this dilemma?