Re: combinations iterator

"mark.hoemmen@xxxxxxxxx" <mark.hoemmen@xxxxxxxxx> writes:

On Jan 1, 2:47 pm, Pascal Bourguignon <p...@xxxxxxxxxxxxxxxxx> wrote:
http://darcs.informatimago.com/darcs/public/lisp/common-lisp/combinat...

what i was thinking of for the second question (generalizing the idea
of iterator over a process) was something like this. If you want a
list of all the combinations of the elements of a given list, you do
something like this:

(defun combinations (list)
(cond ((null list) nil)
((atom list) (combinations (list list)))
((null (cdr list)) (cons list nil))
(t (append (cons (first list) (combinations (cdr list)))
(combinations (cdr list))))))

However, to get an iterator over the output list without actually
constructing the output list, we need some new operators. Suppose
(YIELD x) means "the value x should pop up the chain of YIELDs back to
the iterator, and when the chain ends, the result should be returned
now by the iterator," and (SEQ x y z ...) means "the iterator should
follow the sequence x, y, z if x, y, z, etc. YIELD something." Then we
could write:

(defun combinations (list)
(cond ((null list) (yield nil))
((atom list) (yield (combinations (list list))))
((null (cdr list))
(seq (yield list) (yield nil)))
(t (seq (yield (cons (first list) (combinations (cdr
list))))
(yield (combinations (cdr list)))))))

well, something like that; I'm not being very precise. The idea is
that you just write your algorithms like you would before, but instead
of collecting data into a data structure, you YIELD each datum as you
generate it. I know the SERIES package has something vaguely like the
YIELD operator; could it be (efficiently) adapted to the above case?
Or is this a job for continuations?

Yes, continuations, or coroutines. It's possible that partial
continuations we can implement in CL would be enough for this.


--
__Pascal Bourguignon__ http://www.informatimago.com/

"What is this talk of "release"? Klingons do not make software
"releases". Our software "escapes" leaving a bloody trail of
designers and quality assurance people in its wake."
.

Relevant Pages

  • Re: C# iterators and suspend/resume in Simula 67
    ... ooops--Forgot the updated iterator syntax in my examples...not that it ... I was just saying that rather than doing a bunch of "yield return new ... But the yield statement has to be in the iterator method, ... be compiled IEnumerable classes and not true fibers or coroutines. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: combinations iterator
    ... ((null (cdr list)) ... (cons list nil)) ... to get an iterator over the output list without actually ... follow the sequence x, y, z if x, y, z, etc. YIELD something." ...
    (comp.lang.lisp)
  • Re: IEnumerable is strange
    ... That's exactly what 'yield return' is: ... int foo() ... and similarly investigate how foreach is ... The function implementing the iterator is technically never entered. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Any interest in lightweight coroutines in Java ala C# 2.0 iterators?
    ... > There is a link on that page to the proposed C# 2.0 Language Specification, ... reasonable to approach any new language feature proposal with a degree ... one yield return statement, no yield break statements, and no try / ... persuaded, however, that the code that would then go into an iterator / ...
    (comp.lang.java.programmer)
  • Re: Some notes
    ... >> to not evaluate the argument of the next yield. ... Your alternative evaluates every item in the _args iterator, ... def someof: ... normal generators might well be deemed nonskippable ones). ...
    (comp.lang.python)