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

Question

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

 λ> map toUpper "abcd"
"ABCD"
 λ>

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

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

和sap代表连续申请。类型签名为：

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

例如，集合"abcd"的部分分区可以从"bcd"的分区中用('a':).

 λ> 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，鉴于类型签名，returns 没有任何意义。

sap 这样的原语是否存在于 Haskell 语言库中？？？或者有没有一种方法可以将它写得如此简短以至于它甚至不值得作为一个单独的函数，将它放在所谓的 Fairbairn threshold 之下？

脚注：可以这样写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 的方式我可能更喜欢使用 foldr,

sap f ls = zipWith (alterWith f) [0..] (iterate ls)
  where alterWith f i ls = take i ls ++ f (ls !! i) : drop (i+1) ls

alterWith 在 https://hackage.haskell.org/package/fft-0.1.8.6/docs/Math-FFT-Base.html#v:adjust 中作为 adjust 可用，但我非常不会为该功能带来如此重量级的东西。不过，我经常在项目中已经定义了类似 alterWith 的东西，如果这样的话，可以省略 sap 以支持上面对 zipWith 的调用。

Answer 2

Or is there a way to write it that is so short and simple that it does not even deserve to be a separate function, putting it below the so-called Fairbairn threshold?

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

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

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

Answer 3

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

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 4

利用 Data.List.HT.splitEverywhere:

import Data.List.HT

sap :: (a -> a) -> [a] -> [[a]]
sap f xs = [ pre ++ f x : post | (pre,x,post) <- splitEverywhere xs]

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

Missing Haskell primitive to apply a function to each element of a list successively?

haskell

combinatorics