缺少 Haskell 原语以将函数连续应用于列表的每个元素？

Question

在 Haskell 中，众所周知，map原语可用于将给定函数应用于列表的所有元素：

 ?> map toUpper "abcd"
"ABCD"
 ?> 

在尝试生成有限集（列表）的所有分区时，以下类似的原语会很方便：

 ?> sap toUpper "abcd"
["Abcd","aBcd","abCd","abcD"]
 ?> 

与sap站立连续应用。类型签名将是：

sap :: (a -> a) -> [a] -> [[a]]

例如，集合“abcd”的部分分区可以从“bcd”的分区中通过用('a':)sap'来获得。

 ?> pbcd = [["b","c","d"],["b","cd"],["bc","d"],["c","bd"],["bcd"]]
 ?> 
 ?> concatMap (sap ('a':)) pbcd
[["ab","c","d"],["b","ac","d"],["b","c","ad"],["ab","cd"],["b","acd"],["abc","d"],["bc","ad"],["ac","bd"],["c","abd"],["abcd"]]
 ?> 

然后可以通过添加 'a' 作为它自己单独的单例来获得 5 个丢失的分区。

我的问题是，我一直无法在语言库中找到这样的原语，而且给定类型签名的Hoogle没有返回任何感兴趣的内容。

sapHaskell 语言库中是否存在这样的原语？？？或者有没有一种方法可以写得如此简短和简单，以至于它甚至不值得成为一个单独的函数，将其置于所谓的费尔贝恩阈值以下？

脚注：可以这样写sap：

sap :: (a -> a) -> [a] -> [[a]]
sap fn ls = fst  $  foldr  op  ([], [])  ls
   where  op x (ll,tl) = ( ((fn x):tl) : map (x:) ll , x:tl )

本质上，您从[[fn (last ls)]]种子开始，然后向左前进。但这似乎行人并不简单。

Answer 1

似乎最简单的版本是直接递归：

sap :: (a -> a) -> [a] -> [[a]]
sap _ [] = []
sap f (x:xs) = (f x : xs) : map (x:) (sap f xs)

对此的一种可能探索是作为paramorphism，它可以访问递归结果和未处理的余数。

sap f = para step where
    step Nil = []
    step (Cons x (xs, rest)) = (f x : xs) : map (x:) rest

（未检查，可能有愚蠢的错误）

不过，我不认为这是一个巨大的改进。我没有看到从问题本身分解递归的任何深刻见解。

为此，嗯......我过去曾使用holesOf过这个的通用版本。

sap :: Traversable t => (a -> a) -> t a -> [t a]
sap f = map (peeks f) . holesOf traverse

现在这肯定说明了什么。它已将类型概括为适用于 的所有实例Traversable。另一方面，所涉及的理论块对于最终结果来说太过分了，以至于我不确定它所说的实际上是什么。在第三（？）手上，它看起来很漂亮。

Answer 2

或者有没有一种方法可以将它写得如此简短和简单，以至于它甚至不值得成为一个单独的函数，使其低于所谓的费尔贝恩阈值？

这个。很少需要该功能，并且该(a -> a)参数不适用于非常通用的应用程序。

使用列表递归可以实现一个简短而简单的实现：

sap :: (a -> a) -> [a] -> [[a]]
sap _ []     = []
sap f (x:xs) = (f x:xs):((x:) <$> sap f xs)