haskellリスト内の位置の等価性

Question

2つのリストがある場合、要素間の位置の等価性（特定の意味で）を定義します。たとえば、もし：

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

このような何かは他のいくつかの言語での2つのループの問題だろうが、私は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"])] 

。私はそれを維持するならば、私はおそらくそれを正しく得ることができますが、私はホイールや何かを再発明していないことを確認したいだけです。

だから、これを行う慣用的なハスケルの方法は何ですか？ 1つはありますか？私はハスケルを強制的に強制するように感じており、これを実現するために使用できるいくつかの高次関数や方法が必要であると感じています。

大きな問題は、私はが手の前にリストを知らないということです。それらは、任意のデータ型、異なる長さ、および/または（ネストされた）深度のものであり得る。

これらはユーザー入力からREPLに解析され、最大でFunctor,Monad、ApplicativeとすることができるADTに格納されます。リストの理解にはAlternativeとMonadPlusが必要ですが、カテゴリ理論が狂ってしまうため、リストの理解にはAlternativeとMonadPlusが必要です。

Answer 1

（超効率的でない場合）は、おそらくこのようなものは非常に慣用のようになります。これは、2つの効率の問題を抱えている

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

：GHCiの中

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

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を構築して、どの入力リストにどの要素がどの位置にあるかを特定することです。そして、これらの2つのマップの交差点は、同じ位置にある要素を持つ入力リストを並べているので、その値のデカルト積をliftA2 (,)で取ることができます。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"]) 

Answer 2

このような何かが、実際には、その後、非常に簡単いくつかの他の言語での二つのループ

リストの内包表記の問題で、次のようになります。

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

閲覧：すべてのサブリストについてasからまでとasとbsである場合zipが-ed場合bssチェック内のすべてのサブリストbsため（ネスト）は一緒に、結果に(as,bs)を含む(a,b)に等しいanyタプルがあります。

これは、サブリストに重複要素が含まれている場合に対応する必要があります。