Haskell: merging list of lists

Question

given a list of list pairs ::[a,a], I would like to return the possible combinations of lists, where the sublists have been merged on the last of one sublit matching head of the next.

for example -- combine two lists if they front and back match

merge :: Eq a => [[a]] -> [[a]]
merge (x:y:ys) | last x == head y = merge $ (x ++ (drop 1 y)) : ys
               | otherwise    = []
merge xs       = xs

combinations :: Eq a => [[a]] -> [[a]]
combinations = nub . concatMap merge . permutations

λ= merge [1,2] [2,3]
[1,2,3]


-- there should be no duplicate results
λ= combinations [[1,3],[1,3],[1,3],[1,3],[2,1],[2,1],[2,1],[2,2],[3,2],[3,2],[3,2]]
[[1,3,2,2,1,3,2,1,3,2,1,3],[1,3,2,1,3,2,2,1,3,2,1,3],1,3,2,1,3,2,1,3,2,2,1,3]]

-- the result must be a completely merged list or an empty list
λ= combinations [[1,3], [3,1], [2,2]]
[]

λ= combinations [[1,3], [3, 1]]
[[1,3,1],[3,1,3]]

λ= combinations [[1,3],[3,1],[3,1]]
[[3,1,3,1]]

I can't quite wrap my head around the recursion needed to do this efficiently.

Answer 1

I ended with this solution, but it contains duplicates (you can use Data.List(nub) to get rid of them).

import Data.List(partition)

main :: IO ()
main =  do
        print $ show tmp

input = [[1,3],[1,3],[1,3],[1,3],[2,1],[2,1],[2,1],[2,2],[3,2],[3,2],[3,2]]        

tmp = combinations input

-- this function turns list into list of pair, first element is element of the
-- input list, second element is rest of the list
each :: [a] -> [a] -> [(a, [a])]
each h [] = [] 
each h (x:xs) = (x, h++xs) : each (x:h) xs  

combinations :: (Eq a) => [[a]] -> [[a]]
combinations l = concat $ map combine $ each [] l
   where
      -- take pair ("prefix list", "unused lists")
      combine :: (Eq a) => ([a], [[a]]) -> [[a]]
      combine (x, []) = [x]
      combine (x, xs) = let
                           l = last x
                           -- split unused element to good and bad
                           (g, b) = partition (\e -> l == head e) xs
                           s = each [] g
                           -- add on element to prefix and pass rest (bad + good except used element) to recursion. so it eat one element in each recursive call.
                           combine' (y, ys) = combine (x ++ tail y, ys ++ b) 
                        -- try to append each good element, concat result
                        in concat $ map combine' s

Answer 2

I'm not sure if I fully understand what you want to do, so here are just a few notes and hints.

given a list of list pairs ::[a,a]

(...) for example

λ= merge [1,2] [2,3]

Firstly those are not lists of pairs, each element of the list is an integer not a pair. They just happen to be lists with two elements. So you can say they are of type [Int] or an instance of type [a].

the sublists have been merged on the last of one sublit matching head of the next.

This suggests that the size of the lists will grow, and that you will constantly need to inspect their first and last elements. Inspecting the last element of a list implies traversing it each time. You want to avoid that.

This suggests a representation of lists with extra information for easy access. You only need the last element, but I'll put first and last for symmetry.

-- lists together with their last element
data CL a = CL [a] a a 

cl :: [a] -> CL a 
cl [] = error "CL from empty list"
cl xs = CL xs (head xs) (last xs)

clSafe :: [a] -> Maybe (CL a)
clSafe [] = Nothing
clSafe xs = Just (cl xs)
 
clFirst (CL _ x _) = x
clLast  (CL _ _ x) = x

compatible cs ds = clLast cs == clFirst ds

Perhaps better, maybe you should have

data CL a = CL [a] a a | Nil 

And to include an empty list that is compatible with all others.

Another point to take into account is that if e.g., you have a list xs and want to find lists ys to combine as ys++xs, then you want it to be very easy to access all ys with a given last element. That suggests you should store them in a suitable structure. Maybe a hash table.