haskell - How to insert a list in a list in all possible ways? -

i trying enumerate possible merges of 2 lists. in example inserting "bb" "aaa" like

["bbaaa", "babaa", "baaba", "baaab", "abbaa", "ababa", "abaab", "aabba", "aabab", "aaabb"] 

what did this

import data.list   insert'' :: char -> string -> [(string, string)] -> string insert'' _ _ ([]) = [] insert'' h b ((x, y):xs) =   (x ++ [h] ++ (insert' (b, y))) ++ (insert'' h b xs)  insert' :: (string, string) -> string insert' ([], ys) = ys insert' (xs, ys) =    insert'' h b lists        h = head xs      b = tail xs      lists = zip (tails ys) (inits ys)  

this returns ("aaa", "bb")

"bbaaababaaabaababbaababaababbabababb" 

a concatenated string, tried making list of strings, cannot wrap head around function. seems infinite type construction.

how rewrite function, return list of strings?

an other implementation idea in daniel wagners first post choose in each step element 1 of lists , prepending results generated function called remaining parts of list:

interleave :: [a] -> [a] -> [[a]] interleave xs           []           = [xs] interleave []           ys           = [ys] interleave xs@(x : xs') ys@(y : ys') =    map (x :) (interleave xs' ys) ++ map (y :) (interleave xs ys') 

for intial example produces:

ghci> interleave "bb" "aaa" ["bbaaa","babaa","baaba","baaab","abbaa","ababa","abaab","aabba","aabab","aaabb"]