Haskell delete Chars from String

问题:

I'm trying to write a function of the form

f :: String -> [String]
f str = ...

that returns the list of all the strings formed by removing exactly one character from str. For example:

ghci> f "stack"
["tack","sack","stck","stak","stac"]

Because String and [Char] are synonymous, I could use the index, but I know that you should avoid doing that in Haskell. Is there a better way besides using the index?

回答1:

You could use recursion like so:

f :: [a] -> [[a]]
f [] = []
f (s:ss) = ss : map (s:) (f ss)

回答2:

The Josh Kirklin's solution as a one-liner:

f = tail . foldr (\x ~(r:rs) -> (x : r) : r : map (x :) rs) [[]]

回答3:

Maybe a more readable way to describe it is:

gaps :: [a] -> [[a]]
gaps xs = zipWith removeAt [0..] $ replicate (length xs) xs

removeAt i xs = ys ++ zs
    where
        (ys,_:zs) = splitAt i xs

But practically, it is slower than the other solutions.