在haskell列表中的位置相等

Question

如果我有两个列表，我想定义元素之间的位置相等（在特定意义上）。例如，如果：

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"]] 

，我想可以说2 ∼ "c"的功能和返回的所有元组，其中2和c份额在列表中的相同位置。

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"]) 
    ] 

像这样的事情会在其他一些语言两个回路的事，但我花了一天时间尝试写在Haskell这个功能更好的一部分。我目前的尝试：

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 _ = [] 

眼下这给：

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

这是只有大约一半的权利;如果我坚持下去，我可能会做得对，但我只是想确保我不会重新发明轮子或什么。

那么...什么是地道的Haskell方式来做到这一点？有一个吗？我觉得我迫使Haskell成为势在必行，并且必须有一些更高阶的函数或方法来完成这个任务。

的大问题是我不知道前手名单。它们可以是任意数据类型，不同长度和/或（嵌套）深度。

将它们从用户输入解析为REPL并存储在ADT中，该ADT最多可以为Functor,Monad和Applicative。列表理解需要Alternative和MonadPlus，但不能做那些，因为然后分类理论会发疯。

Answer 1

大概就像这将是非常地道的（如果不是超高效）：

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

在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"]) 

这有两个效率的问题：1，它重新计算的位置在输入列表中重复输入元素，2.遍历所有输入列表对。因此这种方式是O（mnp），其中m是lss的长度，n是rss的长度，并且p是lss或rss的最长元素的长度。一个更高效的版本（每个输入列表只调用一次findIndex，并遍历很少的列表对; O（mn + mp + np + m log（m）+ n log（n）））如下所示：

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] 

基本思想是建立Map s，它告诉哪些输入列表在哪些位置上有给定的元素。然后这两个地图的交集将输入列表排列在同一位置上，因此我们可以将这些值的笛卡尔积乘以liftA2 (,)。

> 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"]) 

Answer 2

像这样的事情会是两个循环的一些其他语言的问题

列表中理解的话，其实很简单：

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

在ghci中

再次

阅读：对于每个子列表as从ass和（嵌套的）对每个子表bs在bss检查，如果当as和bs是zip -ed一起有any元组它等于(a,b)然后包括(as,bs)入结果。

这应该处理子列表包含重复元素时的情况。