list - 在列表上应用函数的 "permutations"

Question

创建列表或集合的排列非常简单。我需要将函数应用于列表中所有元素的所有子集的每个元素，按照它们出现的顺序。例如:

apply f [x,y] = { [x,y], [f x, y], [x, f y], [f x, f y] }

我的代码是一个巨大的管道或昂贵的计算，我不确定如何继续，或者它是否正确。我确信必须有更好的方法来完成这项任务——也许在列表 monad 中——但我不确定。这是我的代码:

apply :: Ord a => (a -> Maybe a) -> [a] -> Set [a]
apply p xs = let box = take (length xs + 1) . map (take $ length xs) in
  (Set.fromList . map (catMaybes . zipWith (flip ($)) xs) . concatMap permutations
   . box . map (flip (++) (repeat Just)) . flip iterate []) ((:) p)

总体思路是:

(1) make the list 
      [[], [f], [f,f], [f,f,f], ... ]
(2) map (++ repeat Just) over the list to obtain
      [[Just, Just, Just, Just, ... ],
       [f   , Just, Just, Just, ... ],
       [f   , f   , Just, Just, ... ],
                                ... ]
(3) find all permutations of each list in (2) shaved to the length of the input list        
(4) apply the permuted lists to the original list, garnering all possible applications
    of the function f to each (possibly empty) subset of the original list, preserving
    the original order.

不过，我确信有更好的方法。我只是不知道。这种方式昂贵、困惑，而且很容易出错。 Justs 在那里是因为预期的应用。

Answer 1

为此，您可以在使用应用程序和 monad 时利用列表表示不确定值这一事实。然后它变得很简单:

apply f = mapM (\x -> [x, f x])

它基本上是这样写的:“将列表中的每个项目映射到它本身以及将 f 应用于它的结果。最后，返回整个列表中这两个值的所有可能组合的列表。”