New subject: Cartesian Product in Standard Haskell Libraries

24 Dec 2012

      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.

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>

Cartesian Product in Standard Haskell Libraries

Jay Sulzberger

Jay Sulzberger

Kim-Ee Yeoh

Chaddaï Fouché

Kim-Ee Yeoh

Jay Sulzberger

Jay Sulzberger

Kim-Ee Yeoh

Jay Sulzberger

Jay Sulzberger

Jay Sulzberger

tags

participants (3)