在列表中应用函数的"排列"

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

为此,您可以利用列表在使用applicatives和monad时表示非确定性值的事实.然后变得如此简单:

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

它基本上如下所示:"将列表中的每个项目映射到自身以及将f应用于它的结果.最后,返回整个列表中这两个值的所有可能组合的列表."

Answer 2

如果我正确理解你的问题,最好不要用排列来描述它.相反,它更接近于生成powersets.

powerset (x:xs) = let pxs = powerset xs in pxs ++ map (x :) pxs
powerset []     = [[]]

每次将另一个成员添加到列表的头部时,powerset的大小都会翻倍.powerset的后半部分与第一部分完全相同,但包括x.

对于您的问题,选择不是包括或排除x,而是选择是否应用f.

powersetapp f (x:xs) = let pxs = powersetapp f xs in map (x:) pxs ++ map (f x:) pxs
powersetapp f []     = [[]]

这就是你的"应用"功能所做的事情,模拟结果的Set.