Отсутствует примитив Haskell для последовательного применения функции к каждому элементу списка?

Question

В Haskell хорошо известно, что примитив map можно использовать для применения данной функции к всем элементам списка:

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

При попытке для генерации всех разделов конечного набора (списка) пригодится следующий подобный примитив:

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

с sap, обозначающим последовательных приложений . Сигнатура типа может быть:

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

Например, часть разделов набора "abcd" может быть получена из разделов "bcd" путем sap'ing их с ('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"]]
 λ> 

и 5 отсутствующих разделов можно затем получить, добавив «a» в качестве отдельного отдельного синглтона.

Моя проблема в том, что я не смог найти такой примитив в языковые библиотеки, и что Hoogle , учитывая сигнатуру типа, не возвращает ничего интересного.

Существует ли такой примитив, как sap, где-нибудь в языковых библиотеках Haskell ??? Или есть способ написать его настолько коротким и простым, что он даже не заслуживает того, чтобы быть отдельной функцией, поместив его ниже так называемого порога Fairbairn ?

Сноска : можно написать 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)

Одним из возможных вариантов этого является параморфизм , который дает доступ к рекурсивному результату и необработанному остаток вместе.

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) не подходит для очень обобщенного c приложения.

Короткая и простая реализация может быть достигнута с помощью рекурсии списка:

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

Answer 3

Я не думаю, что оно существует где-либо, хотя отрицательное доказательство, конечно, невозможно .. Другой способ написать 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 доступно как adjust в https://hackage.haskell.org/package/fft-0.1.8.6/docs/Math-FFT-Base.html#v: настроить , но я бы очень не стал вносить что-то более тяжелое для этой функции. У меня часто есть что-то вроде alterWith, уже определенное в проекте, и если да, то это позволяет sap быть избранным в пользу вызова zipWith выше.

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]