haskell - 如何将列表中的元素与所有其他元素相乘？

Question

例如，list = [1,2,3,4]。 listProduct list 返回 [1,2,3,4,6,8,9,12,16] 即 [(1*1),(1* 2),(1*3),(1*4),(2*3),(2*4),(3*3),(3*4),(4*4)]

我记得看到有一些东西可以做到这一点，但我再也找不到该资源了。

Answer 1

您可以使用列表理解以简单的方式编写此内容:

listProduct xs = [x * y | x <- xs, y <- xs]

但是，使用列表 monad 更为惯用:

import Control.Monad

listProduct = join $ liftM2 (*)

(相当于listProduct xs = liftM2 (*) xs xs)

要理解这个版本，您可以将 liftM2 视为一种广义的 Cartesian product (liftM2 (,) 是笛卡尔积本身)。如果您将 liftM2 的定义专门化为列表 monad，则可以更轻松地了解其工作原理:

liftM2 f mx my = do { x <- mx; y <- my; return (f x y) }
-- expand the do notation
liftM2 f mx my = mx >>= (\x -> my >>= (\y -> return (f x y)))
-- substitute the list monad's definition of (>>=)
liftM2 f mx my = concatMap (\x -> concatMap (\y -> [f x y]) my) mx
-- simplify
liftM2 f mx my = concatMap (\x -> map (\y -> f x y) my) mx
-- simplify again
liftM2 f mx my = concatMap (\x -> map (f x) my) mx

因此 listProduct 的单子(monad)定义扩展为:

listProduct xs = concatMap (\x -> map (x *) xs) xs

(请注意，从技术上讲，您不需要此处的完整列表 monad；所需的只是列表的 Applicative 实例，并且 listProduct = join $ liftA2 (*) 的工作方式如下嗯。但是，更容易展示它如何与 Monadic 定义配合使用，因为列表的 Applicative 实例是根据 Monad 实例定义的。)