2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I could have used in-nested yesterday. \$\endgroup\$ – soegaard May 4 '12 at 16:19
3
\$\begingroup\$

Neat!

It took me a while to see why your second form made sense; it seemed like the Wrong thing until I thought about having a general mechanism to allow later sequences to be closed over the values produced by earlier ones in the way that for* allows. It does have a strongly monadic feel, and ... hmmm...

Actually, one issue I do notice is that in order to use this in a "nice" way, as for example your middle examples do, you need to provide an explicit list of identifiers... but in this case, you know how many sequence clauses you need, and it's easier just to use for*. Your last example doesn't use this, but I'm not sure this is sufficiently common to prefer it over something built with recursion.

\$\endgroup\$
  • \$\begingroup\$ Hey, an answer from a Racket Developer, cool. I agree, using in-nested in a for-like form where you bind to a set of identifiers is not as nice as just using for* directly, but by the same reasoning, in-parallel is equally as pointless and it seems to have made the cut. \$\endgroup\$ – Marty Neal Mar 30 '12 at 21:04
  • \$\begingroup\$ Well, I wouldn't apply the word "pointless" to either one. in-parallel has a nice three-line description, which probably helps. Also, I see the problem you're solving as being one that's naturally solved by recursion, in contrast to in-parallel. \$\endgroup\$ – John Clements Apr 3 '12 at 16:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.