[Haskell-beginners] Cartesian Product in Standard Haskell Libraries

[Kim-Ee Yeoh]

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

Citation? That flies in the face of set theory. nay, even deeper than that,
i.e. fundamentally, how a product should behave.

Perhaps you've conflated it with the cardinality of the function space from
null to null, which is indeed 1: the trivial function.

Also observe that

    sequence [] :: (Monad m) => m [a]

and it's only a consequence of GHCi's type defaulting [1] that it's typed
[()]. Can you trace the chain of reasoning that leads to that type? In
particular, what happens to the Monad constraint?

[1] Section 2.4.7 of
http://www.haskell.org/ghc/docs/7.4.1/html/users_guide/interactive-evaluation.html



-- Kim-Ee


On Mon, Dec 24, 2012 at 2:01 PM, Jay Sulzberger <jays at panix.com> 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/4119730/cartesian-product>
>   http://stackoverflow.com/**questions/3387359/calculate-n-**
> ary-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<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>
>
> ______________________________**_________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/**mailman/listinfo/beginners<http://www.haskell.org/mailman/listinfo/beginners>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20121224/84338b37/attachment-0001.htm>