如何用惯用语写这个函数？

Question

我正在寻找一个函数来测试列表元素的谓词,为每个满足谓词的元素创建一个新列表,并仅将函数应用于该元素.

例:

someFunction :: (a -> Bool) -> (a -> a) -> [a] -> [[a]]
someFunction = ...

let ys = someFunction isOdd (* 2) [1..10]
    {- ys == [[2, 2, 3, 4, 5,  ...],
              [1, 2, 6, 4, 5,  ...],
              [1, 2, 3, 4, 10, ...],
              ...] -}

在ys,第一个列表等于原始列表,除了第一个元素,它满足谓词并乘以2.除了第三个元素之外,第二个列表也等于原始列表,依此类推.

我已经能够通过获取满足谓词的值的索引然后通过索引进行映射来编写这样的函数.然而,这似乎不是很实用,我希望看到一个更惯用的方法.

Answer 1

您可以从标准或应该是的部件组装此功能.接受的答案有关于拉链的正确线索.关于区分和组合的我的答案给出了相关操作的一般处理,但让我在这里具体说明.

我定义了"带有一个元素孔的列表"的类型,如下所示:

data Bwd x = B0 | Bwd x :< x deriving Show
type HoleyList x = (Bwd x, [x])

严格来说,我不需要引入后向列表来做到这一点,但如果我不得不扭转我的想法,我会很容易混淆.(碰巧这HoleyList是正式衍生物[].)

我现在可以在其上下文中定义什么是列表元素.

type InContext x = (HoleyList x, x)

这个想法是该对的第二个组成部分属于后向列表和前向列表.我可以定义将列表重新插入的功能(upF在通用处理中调用.)

plug :: InContext x -> [x]
plug ((B0, xs), y)      = y : xs
plug ((xz :< x, xs), y) = plug ((xz, y : xs), x)

我还可以定义一个函数,它提供了将列表分开的所有方法(downF通常).

selections :: [x] -> [InContext x]
selections = go B0 where
  go xz [] = []
  go xz (x : xs) = ((xz, xs), x) : go (xz :< x) xs

注意

map snd  (selections xs) = xs 
map plug (selections xs) = map (const xs) xs

现在我们很高兴遵循Bartek的食谱.

selectModify :: (a -> Bool) -> (a -> a) -> [a] -> [[a]]
selectModify p f = map (plug . (id *** f)) . filter (p . snd) . selections

即:通过测试筛选选择,将函数应用于焦点元素,然后一起插回.如果你有拉链设备,它是一个单行,它应该适用于任何可区分的仿函数,而不仅仅是列表!任务完成!

> selectModify ((1 ==) . (`mod` 2)) (2*) [1..10]
[[2,2,3,4,5,6,7,8,9,10]
,[1,2,6,4,5,6,7,8,9,10]
,[1,2,3,4,10,6,7,8,9,10]
,[1,2,3,4,5,6,14,8,9,10]
,[1,2,3,4,5,6,7,8,18,10]]

Answer 2

那个怎么样:

从列表开始:

[1,2,3,4]

复制列表n次,n是其大小(:: [[]]):

[
 [1,2,3,4],
 [1,2,3,4],
 [1,2,3,4],
 [1,2,3,4]
]

拆分每个元素上的列表(或多或少"对角线")(:: [([], [])]):

[
 ([],[1,2,3,4]),
 ([1],[2,3,4]),
 ([1,2],[3,4]),
 ([1,2,3],[4])
]

过滤掉head . snd不满足谓词的行

[
 ([],    [1,2,3,4]),
 ([1,2], [3,4])
]

将您的功能应用于剩余的头部

[
 ([],    [2,2,3,4])
 ([1,2], [6,4]),
]

将这些对连接起来

[
 [2,2,3,4],
 [1,2,6,4]
]

Answer 3

您可以使用手指（就像拉链一样：D 您可以在每个项目上移动手指：D 就像阅读时一样）

\n\n

someFunction :: (a -> Bool) -> (a -> a) -> [a] -> [[a]]\nsomeFunction check f xs = r [] xs\n  where r _  []     = []\n        r ps (y:ys) = let rs = r (ps ++ [y]) ys\n                      in  if check y then [ps ++ [f y] ++ ys] ++ rs\n                                     else rs\n

\n\n

r函数采用ps“已处理元素”和(y:ys)“待处理元素”。

\n\n

如果您需要线性成本（ps ++ [y]操作进行二次），请使用高效的尾部插入结构。

\n\n

使用splitAt你可以写

\n\n

someFunction check f xs = map (\\(a,(x:b)) -> a ++ [f x] ++ b) $\n                          filter (check.head.snd)\n                          [splitAt n xs | n <- [0..length xs - 1]]\n

\n\n

或者使用列表理解

\n\n

someFunction check f xs =\n    [ a ++ [f x] ++ b | n <- [0..length xs - 1]\n                      , let (a, (x:b)) = splitAt n xs\n                      , check x]\n

\n\n

使用zip@chi建议的解决方案采用线性成本（生成列表，最终为 O(n^2)）

\n\n

someFunction check f xs = \n    [ a ++ [f x] ++ b | (a, (x:b)) <- init $ zip (inits xs) (tails xs)\n                      , check x]\n

\n\n

最后（？）@\xc3\x98rjanJohansen注释删除init $（我保留了两个版本，我认为这是一个很好的例子）

\n\n

避免init $

\n\n

someFunction check f xs = \n    [ a ++ [f x] ++ b | (a, (x:b)) <- zip (inits xs) (tails xs)\n                      , check x]\n

\n\n

(xs, [])列表理解避免了最后一个“压缩”元素，@\xc3\x98rjanJohansen在这里指出了它是如何翻译的

\n\n

[e | p <- l, Q] = let ok p = [e | Q]\n                      ok _ = []\n                  in concatMap ok l\n

\n\n

（谢谢@WillNess）

\n