On Mon, 24 Dec 2012, Jay Sulzberger wrote:
I need the usual Cartesian product of a list of lists. In the posts
http://stackoverflow.com/questions/4119730/cartesian-product http://stackoverflow.com/questions/3387359/calculate-n-ary-cartesian-product
it is recommended to use the sequence procedure, which is in the standard Prelude, as a "Cartesian product of a list of lists" function. That is we do have that
sequence [["a", "b"], ["c", "d"]]
evaluates to
[["a","c"],["a","d"],["b","c"],["b","d"]]
and often, sequence seems to give the expected answer. But we have also that, and here we quote from a GHCi session,
sequence [] [] it :: [()]
This looks to me to be a violation of the rule that the Cartesian product of an empty list of lists is a list with one element in it. It looks to be a violation because "[]" looks like a name for an empty list. But we also have
length (sequence []) 1 it :: Int
which almost reassures me.
But we also have
sequence [] [] it :: [()] length it 0 it :: Int
So if "it" is the result of evaluating (sequence []) then this seems to say the result is a list of length 0. Which seems in contradiction with the reassuring evaluation above. ad thinko in comments in Haskell transcript: The empty list in our monoid of lists is the zero, not the identity. Any one element list is an "identity", so of course our claimed monoid is also not actually a monoid, except, ah, there is a theory for dealing with the fact that '() is also an endstopper, and not just an empty list. Our "monoid" is really very much a monoidoid, and to take account of the triple identity of '() as endstopper and also empty list and identity for append, will, ah, yes, they are everywhere, VARIOUS FUNCTORS, perhaps not quite falling under the Haskell Functor typeclass. And some of this must be handled in the Haskell lists monad: argument: the thinko, in part, was due to a conflation of some different expressions involving T, mu, and eta, to use the terminology of http://en.wikipedia.org/wiki/Monad_%28mathematics%29 [page was last modified on 15 December 2012 at 16:03] and the fact that, and New Crazy Type theory deals with this, the only "definable" sets are those built from the empty set. oo--JS.
Appended are a Scheme session and a GHCi session showing some of what puzzles me. I remember when I wrote my now standard Cartesian product Scheme procedure I was delighted that, we get
(cprd '()) (())
which gives '() as the single element of the Cartesian product of an empty list of lists.
ad Old Types vs New: Indeed every particular application of the Scheme procedure cprd should be to (some instance of) some "type" of lists of lists, and thus the one element in the output, in case the list of lists is the empty list, should be of the type of the elements, that is, the inner lists, of the input list of lists. In Haskell I do not know enough to say, but, certainly the behavior of sequence-plus-GHCi-plus-printing-conventions was surprising to me.
Oi. Perhaps an/the object of type () just does not get printed clearly. So a list with only one object, and that one object of type (), gets printed on the page as
[]
which is a text name for the list, which is of length one, but this text name looks on the page just like the text name of an empty list.
oo--JS.
<blockquote what="Scheme session showing my standard version of Cartesian product" date="Monday 24 December 2012 01:30:37 -0500">
SCM version 5e5, Copyright (C) 1990-2006 Free Software Foundation. SCM comes with ABSOLUTELY NO WARRANTY; for details type `(terms)'. This is free software, and you are welcome to redistribute it under certain conditions; type `(terms)' for details. ;loading /usr/share/slib/require ;done loading /usr/share/slib/require.scm ;loading /usr/share/slib/require ;done loading /usr/share/slib/require.scm ;loading /usr/lib/scm/Link ;done loading /usr/lib/scm/Link.scm ;loading /usr/lib/scm/Transcen ;done loading /usr/lib/scm/Transcen.scm
(define cartesian:multiply-by-one-list (lambda (multiplier old-product) (if (equal? multiplier '()) '() (if (equal? (cdr multiplier) '()) (map (lambda (x) (cons (car multiplier) x)) old-product) (append (map (lambda (x) (cons (car multiplier) x)) old-product) (cartesian:multiply-by-one-list (cdr multiplier) old-product)))))) #<unspecified> (define cartesian:product (lambda (l) (if (equal? l '()) (list '()) (cartesian:multiply-by-one-list (car l) (cartesian:product (cdr l)))))) #<unspecified> (define cprd cartesian:product) #<unspecified> (cprd '()) (()) (cprd '(())) () (cprd '((a))) ((a)) (cprd '((a b))) ((a) (b)) (cprd '(() (a))) () (cprd '((a) ())) () (cprd '((a) (b))) ((a b)) (cprd '((a b) (c d))) ((a c) (a d) (b c) (b d)) (cprd '((a b) (c d) (e) (f g h))) ((a c e f) (a c e g) (a c e h) (a d e f) (a d e g) (a d e h) (b c e f) (b c e g) (b c e h) (b d e f) (b d e g) (b d e h)) (cprd '(() ())) () ;; OK, this looks right. On lists of lists of symbols ;; cprd seems to be a version of Cartesian product. (quit) ;EXIT
Process scheme finished
</blockquote>
<blockquote what="GHCi session showing sequence and an untested version of a Haskell Cartesian product function" point="To me sequence's behavior on the list of lists [] is puzzling. sequence seems not to obey the rule that the Cartesian product of an empty list of lists is a list with one element in it, whose name/manifestation, in general, might be hard to guess." date="Monday 24 December 2012 01:32:56 -0500">
GHCi, version 7.4.1: http://www.haskell.org/ghc/ :? for help Loading package ghc-prim ... linking ... done. Loading package integer-gmp ... linking ... done. Loading package base ... linking ... done. Prelude> :set +t Prelude> :set prompt "> "
sequence [] [] it :: [()] sequence [[]] [] it :: [[a]] sequence [["a"]] [["a"]] it :: [[[Char]]] sequence [["a", "b"]] [["a"],["b"]] it :: [[[Char]]] sequence [[], ["a"]] [] it :: [[[Char]]] sequence [["a"], []] [] it :: [[[Char]]] sequence [["a"], ["b"]] [["a","b"]] it :: [[[Char]]] sequence [["a", "b"], ["c", "d"]] [["a","c"],["a","d"],["b","c"],["b","d"]] it :: [[[Char]]] sequence [["a", "b"], ["c", "d"], ["e"], ["f", "g", "h"]] [["a","c","e","f"],["a","c","e","g"],["a","c","e","h"],["a","d","e","f"],["a","d","e","g"],["a","d","e","h"],["b","c","e","f"],["b","c","e","g"],["b","c","e","h"],["b","d","e","f"],["b","d","e","g"],["b","d","e","h"]] it :: [[[Char]]] length it 12 it :: Int 2 * 2 * 1 * 3 12 it :: Integer sequence [[], []] [] it :: [[a]] -- OK, it looks as though 'sequence' as suggested in the -- Stackoverflow post -- http://stackoverflow.com/questions/4119730/cartesian-product -- in Answer 10, does most of the time compute a version -- of Cartesian product very much as does the Scheme version. -- Let us do the example in the answer: sequence [[1,2,3],[4,5,6]] [[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]] it :: [[Integer]] length it 9 it :: Int 3 * 3 9 it :: Integer -- But this seems to violate the convention that -- Cartesian product, when handed an empty list of lists -- returns a list with one element. This convention -- makes the 'length' function a homomorphism from the monoid -- of lists, with cartesian product as multiplication, and the empty list -- as the identity element, to the monoid of non-negative integers -- with '*' as multiplication, and '1' as the identity element. -- Let us have a look again as what 'sequence' does: sequence [] [] it :: [()] length it 0 it :: Int sequence [[]] [] it :: [[a]] length it 0 it :: Int length (sequence []) 1 it :: Int :t (sequence []) (sequence []) :: Monad m => m [a] :t (sequence [[]]) (sequence [[]]) :: [[a]] -- Let us try a version of our Scheme procedure 'cprd'. let hmbol multiplier oldproduct = [ x:xs | x <- multiplier, xs <- oldproduct] hmbol :: [a] -> [[a]] -> [[a]] hmbol [] [["a"]] [] it :: [[[Char]]] hmbol [] [[]] [] it :: [[a]] hmbol ["a"] [[]] [["a"]] it :: [[[Char]]] hmbol ["a", "b"] [[]] [["a"],["b"]] it :: [[[Char]]] hmbol ["a", "b"] [] [] it :: [[[Char]]] hmbol ["a", "b"] [["c"]] [["a","c"],["b","c"]] it :: [[[Char]]] hmbol ["a", "b"] [["c"], ["d", "e"]] [["a","c"],["a","d","e"],["b","c"],["b","d","e"]] it :: [[[Char]]] hmbol ["a", "b"] [["c"], [], ["d", "e"]] [["a","c"],["a"],["a","d","e"],["b","c"],["b"],["b","d","e"]] it :: [[[Char]]] let hcprod = foldr hmbol [[]] hcprod :: [[a]] -> [[a]] hcprod [] [[]] it :: [[a]] hcprod [[]] [] it :: [[a]] hcprod [["a", "b"], ["c"], [], ["d", "e"]] [] it :: [[[Char]]] -- Let us repeat all the tests of 'cprod' in the Scheme session: hcprod [] [[]] it :: [[a]] hcprod [[]] [] it :: [[a]] hcprod [["a"]] [["a"]] it :: [[[Char]]] hcprod [["a", "b"]] [["a"],["b"]] it :: [[[Char]]] hcprod [[], ["a"]] [] it :: [[[Char]]] hcprod [["a"], []] [] it :: [[[Char]]] hcprod [["a"], ["b"]] [["a","b"]] it :: [[[Char]]] hcprod [["a", "b"], ["c", "d"]] [["a","c"],["a","d"],["b","c"],["b","d"]] it :: [[[Char]]] hcprod [["a", "b"], ["c", "d"], ["e"], ["f", "g", "h"]] [["a","c","e","f"],["a","c","e","g"],["a","c","e","h"],["a","d","e","f"],["a","d","e","g"],["a","d","e","h"],["b","c","e","f"],["b","c","e","g"],["b","c","e","h"],["b","d","e","f"],["b","d","e","g"],["b","d","e","h"]] it :: [[[Char]]] length it 12 it :: Int 2 * 2 * 1 * 3 12 it :: Integer hcprod [[], []] [] it :: [[a]] -- My two puzzles are: -- Why does -- sequence [] -- evaluate to -- [] -- and not a list with one element? -- Why is the type of the thing that -- sequence [] -- evaluates to -- [()] -- ? :q Leaving GHCi.
Process haskell finished
</blockquote>