[Haskell-beginners] Cartesian Product in Standard Haskell Libraries

[Jay Sulzberger]

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>
>
>