在haskell列表中的位置相等

如果我有兩個列表，我想定義元素之間的位置相等（在特定意義上）。例如，如果：在haskell列表中的位置相等

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，但不能做那些，因爲然後分類理論會發瘋。

來源

2017-07-21 ITA

每個列表中的元素是否唯一唯一？ – immibis

是的，我正在看的情況。 – ITA

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

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

來源

2017-07-21 00:52:44

N.B.這考慮到兩個列表「相等」，如果它們都不*包含有問題的元素，例如'eqElem 0 0 [[1]] [[1]]'會輸出[[（[1]，[1]）]]。希望這裏的想法很清楚，如果你不喜歡那種行爲，你可以看到如何改變這個想法。 –

這很酷，但現在elemEq的類型爲： 'eqElem ::（a1-> Bool） - > [[a1]] - >（a - > Bool） - > [[a]] - > [（[ a1]，[a]）]' 如果我想保留它'eqElem :: a - > [[a]] - > b - > [[b]] - > [（[a]，[b ]）]'因爲我在我的原始示例中嘗試？ – ITA

@IvanAbraham對不起，複製粘貼錯誤。只需對'（==）'進行恰當的調用即可（正如我在編輯過的帖子中所做的那樣）。 –

像這樣的事情會是兩個循環的一些其他語言的問題

列表中理解的話，其實很簡單：

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)入結果。

這應該處理子列表包含重複元素時的情況。

來源

2017-07-21 02:07:46

在haskell列表中的位置相等

回答

相關問題