expand list of lists by adding element once to every list

user_304423 0
Viewed 229

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?

list haskell
3 Answers

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)
user_675790

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:)
user_41689720

Answer of David Flercher with onEach :: (a -> a) -> [a] -> [[a]] very interesting, I do some generalization with typeclass, I think this is usefull when we need some versions of objects mutated in one parameter..:

class Eachable e where
  each :: (a -> a) -> e a -> [e a]

Now we can each on different types for example on Lists:

instance Eachable [] where
  each _ [] = []
  each g (x:xs) = ((g x) : xs) : map (x:) (each g xs)

 each (+1) [1,2,3]
[[2,2,3],[1,3,3],[1,2,4]]

and Trees

data Tree a = Empty | Node (Tree a) a (Tree a) deriving Show

instance Eachable Tree where
  each _ Empty = []
  each g t@(Node l a r) = (\i -> e g 1 i t) <$> [1..count t] where
                                                               e _ _ _ Empty = Empty
                                                               e g c i (Node l a r) = Node l' a' r' where
                                                                                                      a' = if c==i then g a else a
                                                                                                      l' = if c==i then l else e g (c+1) i l
                                                                                                      r' = if c==i then r else e g (c+(count l)+1) i r
count Empty = 0
count (Node l _ r) = 1 + count l + count r

tr = Node (Node Empty 1 Empty) 2 (Node Empty 3 Empty)
each (+1) tr
[Node (Node Empty 1 Empty) 3 (Node Empty 3 Empty),Node (Node Empty 2 Empty) 2 (Node Empty 3 Empty),Node (Node Empty 1 Empty) 2 (Node Empty 4 Empty)]

and others:

data Animal a = Animal {speed::a,size::a,smart::a} deriving Show

instance Eachable Animal where
  each g (Animal sp sz sm) = [Animal (g sp) sz sm, Animal sp (g sz) sm, Animal sp sz (g sm)]

each (+1) $ Animal 1 1 1
[Animal {speed = 2, size = 1, smart = 1},Animal {speed = 1, size = 2, smart = 1},Animal {speed = 1, size = 1, smart = 2}]
user_3044230
Related