Positional equality in haskell list

Question

If I have two lists, I want to define a positional equality (in a particular sense) between elements. For example if:

k = [[3,1,2,4],[1,4,2,3],[1,3,4,2]]
s = [["a","b","c","d"],["d","a","c","b"],["c","b","a","d"],["d","b","c","a"]]

and I want to be able to say 2 ∼ "c" to a function and return all tuples where 2 and c share the same position in the list.

res= [([3,1,2,4],["a","b","c","d"])
     ,([3,1,2,4],["d","a","c","b"])
     ,([3,1,2,4],["d","b","c","a"])
     ,([1,4,2,3],["a","b","c","d"])
     ,([1,4,2,3],["d","a","c","b"])
     ,([1,4,2,3],["d","b","c","a"])
     ]

Something like this would be a matter of two loops in some other language, but I have spent the better part of a day trying to write this function in Haskell. My current attempt:

eqElem i1 (l1:ls1) i2 (l2:ls2) =  helper1 i1 l1 i2 l2 0 where
  helper1 i1 (p:ps) i2 l2 ctr1
    | i1 == p = helper2 i2 l2 ctr1 0
    | otherwise = helper1 i1 ps i2 l2 (ctr1+1)
  helper2 i2 (p:ps) ctr1 ctr2
    | i2==p && ctr1==ctr2 = (l1,l2):(eqElem i1 (l1:ls1) i2 ls2)
    | otherwise = helper2 i2 ps ctr1 (ctr2+1)
  helper2 i2 [] ctr1 ctr2 = eqElem i1 ls1 i2 (l2:ls2)
eqElem i1 [] i2 _ = []

Right now this gives:

*Main Lib> eqElem 2 k "c" s
[([3,1,2,4],["a","b","c","d"]),([3,1,2,4],["d","a","c","b"])] 

which is only about half right; I can probably get it right if I keep at it but I just want to make sure that I am not reinventing the wheel or something.

So...what is the idiomatic Haskell way to do this? Is there one? I feel like I am forcing Haskell to be imperative and that there must be some higher order function or method that can be used to get this done.

The big issue is that I do not know the lists before hand. They can be of arbitrary data type, of differing lengths, and/or (nested) depths.

They are parsed from user input to a REPL and stored in an ADT that can be at best made a Functor, Monad and Applicative. List comprehension would require Alternative and MonadPlus but can't make those because then Category theory would get mad.

Answer 1

Something like this would be a matter of two loops in some other language

List comprehension then, quite straightforward in fact:

eqElem a b ass bss =
  [ (as,bs) | as <- ass, bs <- bss, any (==(a,b)) $ zip as bs ]

Reading: For every sublist as from ass and (nested) for every sublist bs in bss check if when as and bs are zip-ed together there is any tuple which equals to (a,b) then include (as,bs) into result.

This should handle a situation when sublists contain duplicated elements.

Answer 2

Probably something like this would be very idiomatic (if not super efficient):

import Data.List
eqElem l r lss rss =
    [ (ls, rs)
    | ls <- lss
    , rs <- rss
    , findIndex (l==) ls == findIndex (r==) rs
    ]

In ghci:

> mapM_ print $ eqElem 2 "c" [[3,1,2,4],[1,4,2,3],[1,3,4,2]] [["a","b","c","d"],["d","a","c","b"],["c","b","a","d"],["d","b","c","a"]]
([3,1,2,4],["a","b","c","d"])
([3,1,2,4],["d","a","c","b"])
([3,1,2,4],["d","b","c","a"])
([1,4,2,3],["a","b","c","d"])
([1,4,2,3],["d","a","c","b"])
([1,4,2,3],["d","b","c","a"])

This has two efficiency problems: 1. it recomputes the location of the input elements in the input lists repeatedly, and 2. it iterates over all pairs of input lists. So this way is O(mnp) where m is the length of lss, n is the length of rss, and p is the length of the longest element of lss or rss. A more efficient version (which only calls findIndex once per input list, and iterates over many fewer pairs of lists; O(mn+mp+np+m log(m)+n log(n))) would look like this:

import Control.Applicative
import qualified Data.Map as M

eqElem l r lss rss
    = concat . M.elems
    $ M.intersectionWith (liftA2 (,)) (index l lss) (index r rss)
    where
    index v vss = M.fromListWith (++) [(findIndex (v==) vs, [vs]) | vs <- vss]

The basic idea is to build up Maps which tell which input lists have the given elements at which positions. Then the intersection of these two maps line up input lists that have the given elements at the same positions, so we can just take the Cartesian product of the values there with liftA2 (,).

Again in ghci:

> mapM_ print $ eqElem 2 "c" [[3,1,2,4],[1,4,2,3],[1,3,4,2]] [["a","b","c","d"],["d","a","c","b"],["c","b","a","d"],["d","b","c","a"]]
([1,4,2,3],["d","b","c","a"])
([1,4,2,3],["d","a","c","b"])
([1,4,2,3],["a","b","c","d"])
([3,1,2,4],["d","b","c","a"])
([3,1,2,4],["d","a","c","b"])
([3,1,2,4],["a","b","c","d"])