This is another area where the functional logic language family is more powerful. There, we can loop over multi-valued choices (like little forks whose scope is limited to the enclosing loop) and gather all of their results in sequence through backtracking.
-
Show this thread
-
Here, let "a..b" represent the choice of all values in the range from a to b, and "for(a) do b" loop over all choices in a, producing an array containing the values of b. Then we can write a simple loop like:pic.twitter.com/yVYAUSLSR3
3 replies 2 retweets 31 likesShow this thread -
New expressive power comes from our ability to nest choices inside of loops, where each iteration explores all choices. Then we can variably "exponentiate", and write PrintXY as:pic.twitter.com/loFkBD2RaC
6 replies 4 retweets 41 likesShow this thread -
Is this a quirky, special-case language feature? Definitely not; it has well-defined semantics and increases the expressive power of loops. And it's what 14-year-old me intuitively tried to do in Apple BASIC.
5 replies 0 retweets 35 likesShow this thread -
Tim Sweeney Retweeted Tikhon Jelvis
There are many interesting solutions in this thread. The C and JavaScript solutions seen akin to mechanical devices that crank out solutions. One is an astonishingly short Haskell composition of library functions:https://twitter.com/tikhonjelvis/status/1265453175219183616?s=20 …
Tim Sweeney added,
3 replies 4 retweets 48 likesShow this thread -
There is generally a barrier to reading these solutions. In one case you have to run through the behavior of imperative code in your head to understand what it does. In another you have to understand the near magical incantation of pointfree function compositions.
6 replies 0 retweets 44 likesShow this thread -
The more a solution can resemble a simple recitation of the problem to be solved, and rely on the compiler to generate the code, the better for ease of reading and writing code.
10 replies 2 retweets 68 likesShow this thread -
Replying to @TimSweeneyEpic
The problem is, there are infinitely many ways to formulate a problem and each one has different performance implications. Your formulation implies generating ALL strings of length N and then filtering out those, that have symbols other than X and Y, which is very inefficient.pic.twitter.com/yerQIxLRFe
2 replies 0 retweets 0 likes -
Replying to @degorov76
Many of the matching constructs that exist in functional logic languages (and also regular expressions) have “reverse” algorithms that can actually enumerate all possible matches efficiently, without generating temporary values that may fail.
2 replies 0 retweets 2 likes -
Replying to @TimSweeneyEpic @degorov76
For example, consider the regular expression [XY]{7} which coincides with this problem when the count is 7. If you have an efficient generator for regular expression components E, and F, you can recursively define one for E*, E+, EF, E|F, etc.
1 reply 0 retweets 1 like
Conversely, many of the functional logic constructs that generate a choice of values can also match a specified known value through a series of tests which don’t add combinatorial inefficiency to the program.
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.