expand list of lists by adding element once to every list

Question

I implement function which adds an element once to every list of a list.

example:

f :: a -> [[a]] -> [[[a]]]
f 7 [[1],[2],[3]]
[[[7,1],[2],[3]],[[1],[7,2],[3]],[[1],[2],[7,3]]]

I start with this solution:

f :: a -> [[a]] -> [[[a]]]
f e xs = ((\n -> (\(x,l)-> if x==n then e:l else l) <$> zip [1..] xs)  <$> [1..length xs])

Can you please provide some more nice implementations of this function?

Answer 1

You can implement this with recursion. As base case we consider an empty list:

f _ [] = []

for non-empty lists (x:xs) we can use the first item, which is the first sublist. We thus can produce a list where we prepend the first sublist x with the element e, followed by the remaining items xs, so (e:x) : xs is the first item. For the remaining items we recurse on the tail of the list xs and will for each sublist prepend this with the sublist x:

f e (x:xs) = ((e:x) : xs) : map (x:) (f e xs)

so putting these together gives us:

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

Answer 2

Write splits which gives all possible ways of splitting a list

splits :: [a] -> [([a], [a])]
splits xs = zip (inits xs) (tails xs)

for example

> splits "abc"
[("","abc"),("a","bc"),("ab","c"),("abc","")]

and using it write a function that operates on each element of a list

onEach :: (a -> a) -> [a] -> [[a]]
onEach f xs = [ys ++ f z : zs | (ys, z:zs) <- splits xs]

like this

> onEach toUpper "abc"
["Abc","aBc","abC"]

and now f is just

f :: a -> [[a]] -> [[[a]]]
f x = onEach (x:)