haskell - Merge multiple lists if condition is true -

i've been trying wrap head around while now, seems lack of haskell experience won't me through it. couldn't find similar question here on stackoverflow (most of them related merging sublists, without condition)

so here goes. let's have list of lists this:

[[1, 2, 3], [3, 5, 6], [20, 21, 22]] 

is there efficient way merge lists if sort of condition true? let's need merge lists share @ least 1 element. in case of example, result be:

[[1, 2, 3, 3, 5, 6], [20, 21, 22]] 

another example (when lists can merged):

[[1, 2], [2, 3], [3, 4]] 

and it's result:

[[1, 2, 2, 3, 3, 4]] 

thanks help!

i don't know efficiency, can break down what's going on , several different functionalities @ least. particular functionalities might optimizable, it's important clarify what's needed.

let me rephrase question: for set x, binary relation r, , binary operation +, produce set q = {x+y | x in x, y in x, xry}. example, might have x being set of lists, r being "xry if , if there's @ least 1 element in both x , y", , + being ++.

a naive implementation might copy set-builder notation itself

shareelement :: eq => [a] -> [a] -> bool shareelement xs ys = or [x == y | x <- xs, y <- ys]  v1 :: (a -> -> bool) -> (a -> -> b) -> [a] -> [b] v1 (?) (<>) xs = [x <> y | x <- xs, y <- xs, x ? y] 

then p = v1 shareelement (++) :: eq => [[a]] -> [[a]] might achieve want. except doesn't.

prelude> p [[1], [1]] [[1,1],[1,1],[1,1],[1,1]] 

the obvious problem 4 copies: 2 merging lists themselves, 2 merging lists each other "in both directions". problem occurs because list isn't same set can't kill uniques. of course, that's easy fix, we'll use set everywhere

import data.set set  v2 :: (a -> -> bool) -> (a -> -> b) -> set.set -> set.set b v2 (?) (<>) = set.fromlist . v1 (?) (<>) . set.tolist 

so can try again, p = v2 (shareelementonset.tolist) set.union with

prelude set> p $ set.fromlist $ map set.fromlist [[1,2], [2,1]] fromlist [fromlist [1,2]] 

which seems work. note have "go through" list because set can't made instance of monad or applicative due ord constraint.

i'd note there's lot of lost behavior in set. instance, fight either throwing away order information in list or having handle both x <> y , y <> x when our relation symmetric.

some more convenient versions can written like

v3 :: monoid => (a -> -> bool) -> [a] -> [a] v3 r = v2 r mappend 

and more efficient ones can built if assume relationship is, say, equality relation since instead of having o(n^2) operation can in o(nd) d number of partitions (cosets) of relation.

generally, it's interesting problem.