5

I'm playing with John Earnest's K implementation in the context of Project Euler problems.

Many of the problems involve taking the first n terms, or all terms <= n, from an infinite series (particularly primes). It could also involve taking items from a pre-existing list one at a time until a condition is satisfied.

In Python, one approach is to rely on the iterator protocol: you can take from an iterator until it's finished, or break out early when some condition is satisfied (say you've taken n items, or the last item you took satisfies a certain condition).

What are typical patterns in K (or other APLs) for achieving something similar - that is, taking from a list or generator until a condition is satisfied, without evaluating or processing the whole list? Do I have to rely on the techniques below, perhaps using some kind of internal state within f? Is this kind of approach discouraged and if so, why?

  f/x      / fixed point
n f/x      / apply f n times
p f/x      / do or while loop, with p a predicate function (stops when 0)

EDIT 2018-10-14: Some interesting notes on lazy iteration in APLs here.

chrispsn
  • 243
  • 1
  • 4
  • 1
    you know that `f\x`, `n f\x`, `p f\x` do the same while preserving intermediate results, right? – ngn Aug 19 '18 at 11:31
  • Yes - but let's assume the intermediate results are not needed. Unless I'm missing the potential of 'scan'? If helpful: I had in mind something like monadic `!` that generates ascending numbers or permutations until a consumer stops taking from it. – chrispsn Aug 19 '18 at 11:57
  • 2
    Well, isn't `p f/x` exactly that? For instance `{20>x*x}{1+x}/1` keeps generating the next natural number until its square becomes ≥20. Instead of `{1+x}` you could have a function that consumes `x` and returns its successor. – ngn Aug 19 '18 at 12:11
  • ...or maybe replace `{20>x*x}` with a function that consumes `x` and returns a boolean - whether it wants to continue. – ngn Aug 19 '18 at 12:20
  • Thanks - hmm, I'll think about a better motivating problem. Maybe it's a matter of getting more experience with the ways 'reduce' and 'scan' can be used, and of decomposing problems "the APL/K way". – chrispsn Aug 19 '18 at 12:45

1 Answers1

0

As you mentioned (and as suggested in a comment):

p f/x      / do or while loop, with p a predicate function (stops when 0)

Indeed, you can provide a predicate function that is applied to the result at each step. The iteration continues as long as the predicate result is 1b and stops otherwise. That's how, for example, to stop the computation of the Fibonacci sequence once it exceeds 100:

{*|x<100} {x,+/-2#x}/1 1
egor7
  • 4,678
  • 7
  • 31
  • 55