search

elm-community / list-extra

Convenience functions for working with List.
http://package.elm-lang.org/packages/elm-community/list-extra/latest
MIT License
135 stars 58 forks source link

Add cartesianProduct function #84

Closed rlefevre closed 6 years ago

rlefevre commented 6 years ago

Hi,

I needed this for a project, and this is quite useful, so I thought I might as well do a pull request, in case you think it has its place in List.Extra.

I kept the name sequence because it is typically named like this for monads (like in core/Task) but in the list context, maybe cartesian or cartesianProduct might be better.

The implementation is almost identical to sequence in core/Task (but using lift2 instead of map2 to explore all combinations).

Chadtech commented 6 years ago

Hey this looks pretty good to me.

I find the name cartesianProduct a lot nicer. cartesianProduct suggest to me exactly what you implemented, while sequence doesnt suggest much of anything. That could just be reflecting my unique experience.

rlefevre commented 6 years ago

I think you're right. The sequence name does not make much sense in a context limited to lists. I renamed it to cartesianProduct and made a few syntactic improvements (hopefully).

rlefevre commented 6 years ago

Hmm, maybe one issue is that cartesianProduct [[]] == [] but cartesianProduct [] == [[]]. This seems wrong.

jvoigtlaender commented 6 years ago

@rlefevre, mathematically this is exactly correct. What one should expect of a Cartesian product of several lists is something like length (cartesianProduct lists) == product (map length lists) where product = foldr (*) 1.

The two examples you give do satisfy this property. If you changed those cases, e.g., swapping their results, the property would not anymore hold.

rlefevre commented 6 years ago

Ah, thank you very much. I had a doubt about cartesianProduct [] == [[]] because sequence [] == [] in haskell. I should have reviewed my maths about the nullary cartesian product

In any category, the product of an empty family is a terminal object of that category [...] and the terminal object is a singleton set.

This was the occasion to add a test. Thanks again.

jvoigtlaender commented 6 years ago

I don’t think it is true that in Haskell, the sequence function on the empty list gives the empty list. It certainly gives „return []“, which in the case of the list monad is exactly [[]].

rlefevre commented 6 years ago

You're right again, I was tricked by the list monad and ghci that produces (as expected) the same output for [] and return []. Thank you for the clarification.