I've been learning about Racket sequences and noticed a hole where nested iteration is concerned. We have the in-parallel construct but no in-nested construct. There's the for*/... family, but that's syntactic, and can't be extended to an arbitrary number of sequences known only at run time, so here is my attempt at writing a generic in-nested sequence constructor.
;Returns a sequence where each element has as many
;values as the sum of the number of values produced
;by s-outer and s-inner
(provide/contract
[in-nested (-> sequence?
(or/c (-> any/c sequence?) sequence?)
sequence?)])
(define (in-nested outer-sequence inner-sequence)
(struct position (first-outer next-outer first-inner next-inner))
;Calls the sequence-generator and if successful, re-initiates the
;inner-sequence by calling it with the value from the
;sequence-generator. if the inner-sequence is empty, the
;sequence-generator is called again until either the
;sequence-generator runs dry, or we find an inner sequence that is
;not empty
;sequence-generator : -> (values (or/c list? #f) thunk?)
;return : (or/c position? #f)
(define (restart-inner sequence-generator)
(let-values (((first-outer next-outer) (sequence-generator)))
(let loop ((first-outer first-outer) (next-outer next-outer))
(if first-outer
(let-values (((first-inner next-inner)
(sequence-generate*
(call-with-values
(thunk (apply values first-outer))
inner-sequence))))
(if first-inner
(position first-outer next-outer first-inner next-inner)
(call-with-values next-outer loop)))
#f))))
(if (sequence? inner-sequence)
(in-nested outer-sequence (lambda _ inner-sequence))
(make-do-sequence
(thunk (values
(lambda (p)
(apply values (append (position-first-outer p)
(position-first-inner p))))
(lambda (p)
(let-values (((first-inner next-inner)
((position-next-inner p))))
(if first-inner
(position
(position-first-outer p)
(position-next-outer p)
first-inner
next-inner)
(restart-inner (position-next-outer p)))))
(restart-inner (thunk (sequence-generate* outer-sequence)))
identity
#f
#f)))))
To give you an idea of how you might use this code, here are some samples. I have these in a separate test file under rackunit.
;simple case
(for (((a b) (in-nested (in-list '(a b)) (in-list '(c d)))))
(printf "~a,~a " a b)) ;=> a,c a,d b,c b,d
;use outer variable in inner loop
(for (((a b) (in-nested (in-range 1 6)
(lambda (i) (in-range 1 i)))))
(display b))
There are of course many ways to define the combination and permutation using append-map or basic recursion, but these give you a pure sequence not a list or some other actualization of the sequence.
;returns all the ways you can choose n elements from items with replacement
(provide/contract
[combinations (-> list? (and/c exact-integer? positive?) sequence?)])
(define (combinations items n) ; -> list?
(let ((options (build-list (- n 1) (lambda _ (in-list items)))))
(in-values-sequence (foldl in-nested items options))))
(sequence->list (combinations '(a b c) 2))
;=> '((a a) (a b) (a c) (b a) (b b) (b c) (c a) (c b) (c c))
;returns all the ways you can choose n elements from items without replacement
;this is inefficient, don't use. Only for showing how in-nested works
(provide/contract
[combinations (-> list? (and/c exact-integer? positive?) sequence?)])
(define (permutaions items n)
(let ((options (make-list (- n 1) (lambda used (foldl remove items used)))))
(in-values-sequence (foldl (lambda (e a) (in-nested a e)) items options))))
(sequence->list (permutaions '(a b c) 2))
;=> '((a b) (a c) (b a) (b c) (c a) (c b))
I'm open to any and all suggestions for improvements. Can I make this more useful, more readable, shorter, faster, or more robust? As an aside, I've read that this kind of abstraction over nested iteration has important theoretical roles. Similar to the Monad Bind in Haskell, (though I'm not familiar with Haskell), or SelectMany which is the work horse of Linq for .NET
PS. I'm waiving the cc license and putting this work under the WTFPL license in case you want to use it.
