查找列表中的兩個元素，按其出現順序排列

我在寫一個函數，它帶有一個列表和兩個可能包含在列表中的元素。該函數應該返回一個結構中的兩個元素，該結構按它們在列表中出現的順序對它們進行排序。查找列表中的兩個元素，按其出現順序排列

因此，對於數字我們就會有這樣的事：

xs = [4,6,3,2,1,8] 
f (3,1) --> (Just 3, Just 1) 
f (1,3) --> (Just 3, Just 1) 
f (9,1) --> (Just 1, Nothing) 
f (9,9) --> (Nothing, Nothing)

等..

我用的元組在那裏，因爲我其實只是在這兩個值感興趣，而不是一個任意數字。但是，如果有理由，將它建模爲列表也可以。

不管怎麼說，這裏是我想出了以下功能：

f :: Eq a => [a] -> (a, a) -> (Maybe a, Maybe a) 
f xs (a, b) = foldl g (Nothing, Nothing) xs where 
    g (Nothing, Nothing) x | x == a   = (Just a, Nothing) 
    g (Nothing, Nothing) x | x == b   = (Just b, Nothing) 
    g (Just a', Nothing) x | a' == a && x == b = (Just a, Just b) 
    g (Just b', Nothing) x | b' == b && x == a = (Just b, Just a) 
    g m x = m

它的工作，但我認爲這是相當多的模式在那裏匹配的，這有點容易出錯。那麼，有沒有人對這個問題有更好的抽象？

來源

2017-05-02 Anton Harald

我不知道你會認爲這些有多好，但是你可以做一些更多使用列表函數的東西。

我最初以爲先過濾掉無關項目，並分組：

f :: Eq a => [a] -> (a,a) -> (Maybe a, Maybe a) 
f xs (a, b) = 
    case (map head . group . filter (`elem` [a,b])) xs of 
    [] -> (Nothing, Nothing) 
    [c] -> (Just c, Nothing) 
    (c:d:_) -> (Just c, Just d)

但這並不一樣做您的實現上，例如， f [8,9,9] (9,9)，所以你需要特殊情況下，如果這是你關心的情況。

另一種方法是用dropWhile：

f' :: Eq a => [a] -> (a,a) -> (Maybe a, Maybe a) 
f' xs (a, b) = 
    case dropWhile (`notElem` [a, b]) xs of 
    [] -> (Nothing, Nothing) 
    (y:ys) -> (Just y, next) 
     where 
     next = case dropWhile (/=other) ys of 
       [] -> Nothing 
       (z:_) -> Just z 
     other = if y == a then b else a

與內殼實際上只是一個find所以它可以簡化一點：

f'' :: Eq a => [a] -> (a,a) -> (Maybe a, Maybe a) 
f'' xs (a, b) = 
    case dropWhile (`notElem` [a, b]) xs of 
    [] -> (Nothing, Nothing) 
    (y:ys) -> (Just y, find (==other) ys) 
     where 
     other = if y == a then b else a

注：這些函數永遠不會返回結果爲(Nothing, Just _)。這表明返回類型Maybe (a, Maybe a) 可能會更好。或者像None | One a | Two a a這樣的自定義類型。

或者，我們可以概括爲一個列表版本，允許根據您的喜好設置多個目標值。它使一個很好的展開：

f''' :: Eq a => [a] -> [a] -> [a] 
f''' xs ts = unfoldr g (xs, ts) 
    where 
    g (ys, us) = case dropWhile (`notElem` us) ys of 
        [] -> Nothing 
        (z:zs) -> Just (z, (zs, delete z us))

哪像這樣工作的：

λ> f''' [4,2,5,3,1] [1,2,3] 
[2,3,1] 
λ> f''' [4,2,5,3,1] [1,2,6] 
[2,1] 
λ> f''' [7,9,8,9] [9,9] 
[9,9]

我幾乎重塑intersect在這裏，但不完全是。它具有我們希望保留第一個列表的順序的行爲，但重複的順序並不相同 - 例如intersect [4,2,2,5] [1,2]是[2,2]。

來源

2017-05-02 10:35:50

如果你想減少模式匹配的數量，那麼最好不要傳遞(Maybe a, Maybe a)對，並且模式匹配。你可以把你的函數分成兩個遞歸函數，第一個函數找到第一個元素，然後調用第二個函數。這可以這樣進行：

f :: Eq a => (a, a) -> [a] -> (Maybe a, Maybe a) 
f (a, b) = goFirst 
    where 
    goFirst [] = (Nothing, Nothing) 
    goFirst (x:xs) 
     | x == a = (Just a, goSecond b xs) 
     | x == b = (Just b, goSecond a xs) 
     | otherwise = goFirst xs 

    goSecond _ [] = Nothing 
    goSecond y (x:xs) 
     | x == y = Just y 
     | otherwise = goSecond y xs

事實並非如此短的優雅，你可能會想，但它是可讀的，快的（我想補充一點，你應該永遠使用foldl功能），不易出錯。

如果你正在尋找一些抽象，你可以看看First幺半羣與對幺半羣。使用半羣實例First數據類型，你可以像這樣開始：

import Data.Bifunctor (bimap) 
import Data.Monoid (First (..), mconcat) 

g :: Eq a => (a, a) -> [a] -> (Maybe a, Maybe a) 
g (a, b) = bimap getFirst getFirst . mconcat . map fMapper 
    where 
    fMapper x 
     | x == a = (First (Just a), mempty) 
     | x == b = (mempty, First (Just b)) 
     | otherwise = mempty

雖然此功能不會做的正是你想要的東西：

ghci> let xs = [4,6,3,2,1,8] 
ghci> g (3, 1) xs 
(Just 3,Just 1) 
ghci> g (1, 3) xs 
(Just 1,Just 3)

要使用這種方法可以實現最初的目標給每個元素添加索引，然後按索引對First進行排序，但這個解決方案很可怕並且很難看。使用First monoid是誘人的，但我不知道如何在這裏優雅地使用它。

但是你可以從第一和第二的解決方案相結合的想法：

import Data.Bool (bool) 
import Data.Monoid (First (..)) 

h :: Eq a => (a, a) -> [a] -> (Maybe a, Maybe a) 
h (a, b) = goFirst 
    where 
    goFirst [] = (Nothing, Nothing) 
    goFirst (x:xs) 
     | x == a = (Just a, goSecond b xs) 
     | x == b = (Just b, goSecond a xs) 
     | otherwise = goFirst xs 

    goSecond y = getFirst . foldMap (bool mempty (First (Just y)) . (== y))

來源

2017-05-02 11:04:29 Shersh

下面是與列表一個可能的解決方案，以下類型的：

f :: Eq a => [a] -> [a] -> [Maybe a]

我會叫列表中搜索haystack和搜索needles的元素。首先，我們可以搜索haystack每個needle，並返回一對價值和它被發現的，如果任何指標，用findIndex：

findIndices needles haystack = 
    [ (needle, findIndex (== needle) haystack) 
    | needle <- needles 
    ] 

findIndices [1, 3] xs == [(1, Just 4), (3, Just 2)]

（請注意，這總是使用第一的指數發生 - 我不知道這是你想要的你可以擴展它放到倍，因爲它的發現，除去每次出現）

然後通過索引排序，這份名單：。

sortBy (comparing snd) [(1, Just 4), (3, Just 2)] 
== 
[(3, Just 2), (1, Just 4)]

最後提取，這是實際存在的每個指標的值，使用(<$) :: Functor f => a -> f b -> f a：

[value <$ mIndex | (value, mIndex) <- [(3, Just 2), (1, Just 4)]] 
== 
[Just 3, Just 1]

（x <$ f相當於const x <$> f）

可是當我們嘗試這種對輸入其中的一些元素AREN」 t上找不到，我們得到錯誤的結果，其中Nothing小號來一開始，而不是結束：

findIndices [9, 1] xs == [(9, Nothing), (1, Just 4)] 

sortBy (comparing snd) [(9, Nothing), (1, Just 4)] 
== 
[(9, Nothing), (1, Just 4)]

這是因爲Nothing被認爲小於任何Just值。由於我們希望相反，我們可以利用Data.Ord的Down NEWTYPE，通過傳遞Down . snd代替snd作爲比較扭轉Maybe的排序順序：

sortBy (comparing (Down . snd)) [(9, Nothing), (1, Just 4)] 
== 
[(1, Just 4), (9, Nothing)]

但這也反轉的排序順序指數本身，這是我們不希望：

sortBy (comparing (Down . snd)) [(1, Just 4), (3, Just 2)] 
== 
[(1, Just 4), (3, Just 2)]

因此，我們可以添加另一Down圍繞指數：

findIndices needles haystack = 
    [ (needle, Down <$> findIndex (== needle) haystack) 
    | needle <- needles 
    ] 

sortBy (comparing Down) [Just (Down 2), Nothing, Just (Down 1)] 
== 
[Just (Down 1), Just (Down 2), Nothing] 

sortBy (comparing (Down . snd)) 
    [(1, Down (Just 4)), (3, Down (Just 2))] 
== 
[(3, Down (Just 2)), (1, Down (Just 4))]

最後把它放在一起：

f :: (Eq a) => [a] -> [a] -> [Maybe a] 
f needles haystack = 
    [ value <$ index 
    | (value, index) <- sortBy (comparing (Down . snd)) 
    [ (needle, Down <$> findIndex (== needle) haystack) 
    | needle <- needles 
    ] 
    ] 

f [1, 3] xs == [Just 3, Just 1] 
f [3, 1] xs == [Just 3, Just 1] 
f [1, 9] xs == [Just 1, Nothing] 
f [9, 9] xs == [Nothing, Nothing]

，或雖未列表內涵與較短的名稱：

f :: (Eq a) => [a] -> [a] -> [Maybe a] 
f ns hs 
    = map (\ (v, i) -> v <$ i) 
    $ sortBy (comparing (Down . snd)) 
    $ map (\ n -> (n, Down <$> findIndex (== n) hs)) ns

\ (v, i) -> v <$ i也可以寫爲uncurry (<$)，但是這可能會有點神祕，如果你不習慣於無點的風格。另外，如果您不關心Nothing，則可以使用mapMaybe而不是map，將返回類型從[Maybe a]更改爲僅[a]。

來源

2017-05-02 11:28:53

查找列表中的兩個元素，按其出現順序排列

回答

相關問題