問題描述
Haskell 是否有一個函數可以創建將函數應用於列表的每個變體 (Haskell Is there a function for creating every variation of applying a function to a list)
我想創建一個將函數應用於列表的每個元素的變體列表。這是我的意思的一個簡單示例。
applyVar f [a, b, c]
>> [[(f a), b, c], [a, (f b), c], [a, b, (f c)]]
本質上，它將一個函數單獨應用於列表的每個元素，並將每個可能的應用程序存儲在一個數組中。
我不是太確定如何在不使用索引的情況下解決這樣的問題，因為我聽說它們效率不高。這是假設函數 f 返回與輸入列表相同的類型。
是否有預先存在的函數來獲得這種行為？如果不是，那將是什麼功能？
參考解法
方法 1:
To see if there's a pre‑existing function, first figure out its type. In this case, it's (a ‑> a) ‑> [a] ‑> [[a]]. Searching for that type on Hoogle only returns a handful of matches, and by inspection, none of them do what you want.
To write it yourself, note that it operates on a list, and the best way to figure out how to write a function on a list is to define it inductively. This means you need to build two cases: one for an empty list, and one for a non‑empty list that assumes you already know the answer for its tail:
applyVar f [] = _
applyVar f (x:xs) = _ ‑‑ use `applyVar f xs` somehow
Now we just need to fill in the two blanks. For the nil case, it's easy. For the cons case, note that the first sublist starts with f a, and the rest will all start with a. Then, note that the tails of the rest look an awful lot like the answer for the tail. From there, the pattern should become clear.
applyVar f [] = []
applyVar f (x:xs) = (f x:xs):map (x:) (applyVar f xs)
And here's a quick demo/test of it:
Prelude> applyVar (+10) [1,2,3]
[[11,2,3],[1,12,3],[1,2,13]]
方法 2:
Note that, as is often the case, lens contains some tools that provide this as a special case of some far more abstract tooling.
$ cabal repl ‑b lens,adjunctions
Resolving dependencies...
GHCi, version 8.10.3: https://www.haskell.org/ghc/ :? for help
> import Control.Lens
> import Control.Comonad.Representable.Store
> let updateEach f = map (peeks f) . holesOf traverse
> :t updateEach
updateEach :: Traversable t => (s ‑> s) ‑> t s ‑> [t s]
> updateEach negate [1..3]
[[‑1,2,3],[1,‑2,3],[1,2,‑3]]
> import qualified Data.Map as M
> updateEach (*3) (M.fromList [('a', 1), ('b', 2), ('c', 4)])
[fromList [('a',3),('b',2),('c',4)],fromList [('a',1),('b',6),('c',4)],fromList [('a',1),('b',2),('c',12)]]
This is honestly way overkill, unless you start needing some of the ways lens gets more compositional, like so:
> let updateEachOf l f = map (peeks f) . holesOf l
> updateEachOf (traverse . filtered even) negate [1..5]
[[1,‑2,3,4,5],[1,2,3,‑4,5]]
> updateEachOf (traverse . ix 2) negate [[1,2],[3,4,5],[6,7,8,9],[10]]
[[[1,2],[3,4,‑5],[6,7,8,9],[10]],[[1,2],[3,4,5],[6,7,‑8,9],[10]]]
But whether you ever end up needing it or not, it's cool to know that the tools exist.
方法 3:
Yes. Two functions, inits and tails:
foo :: (a ‑> a) ‑> [a] ‑> [[a]]
foo f xs = [ a ++ [f x] ++ b | a <‑ inits xs
| (x:b) <‑ tails xs]
(with ParallelListComp extension; equivalent to using zip over two applications of the two functions, to the same input argument, xs, in the regular list comprehension).
Trying it out:
> foo (100+) [1..5]
[[101,2,3,4,5],[1,102,3,4,5],[1,2,103,4,5],[1,2,3,104,5],[1,2,3,4,105]]
(by user11115921、Joseph Sible‑Reinstate Monica、Carl、Will Ness)