Re: Learning Scheme - critique

S. Robert James writes:

;;; The cardinality of the returned set =
;;; product of the cardilaties of each of the n-sets.

(define (cartesian-product. list-of-sets)
(define los list-of-sets)
(if (null? los)
'() ; The null cartesian-product is the empty set

Think again. I believe you are right that the size of the cartesian
product should be the product of the sizes of the sets - but the empty
product is taken to be 1, not 0.

(if (null? other-sets)
(map list first-set)

If you make the empty cartesian product be (()), you don't need this
special case. The right thing just happens.

(if (null? first-set)
'() ; If any of the n-sets are empty, their cartesian-
; product is empty

This special case vanishes if you follow my suggestion below. You can
simply trust `map' to do the right thing with the empty list. (Or you
could still keep this as an optimization, but it does make the code
longer.)

(let
((first-element (car first-set))
(other-elements (cdr first-set)))
(append
(map (lambda (y) (cons first-element y)) (cartesian-
product other-sets))
(cartesian-product (cons other-elements other-
sets)))))))))

That must be the inefficiency you perceived: you compute the cartesian
product of other-sets or more in two branches, recursively. It's like
the use of Fibonacci numbers to teach that recursion is inefficient.

I suggest you turn this around so that the cartesian product of
other-sets is computed just once, and then each element of first-set
is prepended to each element of that. Using a `map' within `map' for
this, the result is a list of lists that needs flattening. This is
best done with a special version of `map', but you can start with

(apply append (map ...))

All comments - be they on the algo, simplicity, conventions, or
style - are appreciated. Two things strike me as akward about it
already - 1. I would think that the algo should be much shorter and
2. tracing it shows the code to calculate things quite inefficiently
- but I'm not sure how to improve it. Any comments appreciated.

I hope my comments above are helpful. In case they are less than
clear, below is my code in rot-13 so as to not spoil all your own fun
too fast. (That special version of `map' I leave to you.)

(qrsvar (cebq frgf)
(vs (ahyy? frgf)
'(())
(yrg ((svefgf (pne frgf))
(erfgf (cebq (pqe frgf))))
(nccyl nccraq
(znc (ynzoqn (r)
(znc (ynzoqn (e)
(pbaf r e))
erfgf))
svefgf)))))
.

Relevant Pages

  • Re: Logging oddity: handlers mandatory in every single logger?
    ... for example when a Formatter ... string-> int is an internal hack to map easilty map Level name to their int identifier. ... Ah, interesting, I didn't think it could be defined as empty. ... Note how progammatically the list of handlers is set to an empty list. ...
    (comp.lang.python)
  • RE: Dynamic Maps In Orchestrations
    ... need to do a lot of checking for empty results and so on... ... If you give a wrong map type or the message ... > We did the whole untyped document dynamic mapping approach in our project. ... >> "construct keywords. ...
    (microsoft.public.biztalk.general)
  • Re: Cartesian outer join with plus-sign syntax
    ... Dijk) wrote: ... but it looks a lot like it, so I called the combination cartesian ... Yes, if table b is empty, the full outer join gives the desired ...
    (comp.databases.oracle.server)
  • Re: Empty constants
    ... final, read-only, empty constants for common classes. ... public static final Map MAP = new EmptyMap; ... where EmptyMap is a map implementation that has zero elements and throws an UnsupportedOperationException if you try to modify it. ... Now I just have EMPTY_ITERATOR, empty Object arrays, and a few things like empty StringBuffers. ...
    (comp.lang.java.programmer)
  • Re: Cartesian outer join with plus-sign syntax
    ... Dijk) wrote: ... but it looks a lot like it, so I called the combination cartesian ... Yes, if table b is empty, the full outer join gives the desired ...
    (comp.databases.oracle.server)