haskell list中的独特元素

好吧，这可能会在前奏中，但是：是否有标准库函数用于查找列表中的唯一元素？我（重新）执行，澄清是：haskell list中的独特元素

has :: (Eq a) => [a] -> a -> Bool 
has [] _ = False 
has (x:xs) a 
    | x == a = True 
    | otherwise = has xs a 

unique :: (Eq a) => [a] -> [a] 
unique [] = [] 
unique (x:xs) 
    | has xs x = unique xs 
    | otherwise = x : unique xs

来源

2010-06-23 muhmuhten

+10

你'has'也是标准;它只是'flip elem'。 – Nefrubyr 2010-06-23 08:19:04

或甚至'有xs =（\'elem \'xs）'。 – yatima2975 2010-06-23 09:08:16

@ yatima2975你为什么用elem作为中缀？ – dopatraman 2016-06-09 02:07:54

nub功能从Data.List（不，它实际上不是在前奏）绝对做你想要的东西，但它不是和你的unique函数完全一样。它们都保留了元素的原始顺序，但unique保留了每个元素的最后一个，而nub保留了第一个元素。

你可以这样做是为了nub行为酷似unique，如果这是重要的（虽然我有一种感觉，它不是）：

unique = reverse . nub . reverse

此外，nub只对小名单良好。它的复杂性是二次的，所以如果你的列表可以包含数百个元素，它开始变慢。

如果您将类型限制为具有Ord实例的类型，则可以使其更好地缩放。上nub这种变化仍然保留在列表中元素的顺序，但其复杂程度O(n * log n)：

import qualified Data.Set as Set 

nubOrd :: Ord a => [a] -> [a] 
nubOrd xs = go Set.empty xs where 
    go s (x:xs) 
    | x `Set.member` s = go s xs 
    | otherwise  = x : go (Set.insert x s) xs 
    go _ _    = []

事实上，它已经proposed添加nubOrd到Data.Set。

来源

2010-06-23 10:21:49 Yitz

可以说它最好只是将它作为一个集合而不是使用列表中的第一个地址 – alternative 2013-10-16 13:27:34

老实说：'nub'对任何名单。即使在具有2个元素的列表中，“nubOrd”也是[更快]（https://github.com/nh2/haskell-ordnub#dont-use-nub）。 – nh2 2016-01-13 14:43:29

这有点像“地图筛”，类似于不纯的“散列筛”。 – CMCDragonkai 2016-09-23 15:34:08

我搜索了(Eq a) => [a] -> [a]上Hoogle。

第一个结果是nub（从列表中删除重复元素）。

Hoogle太棒了。

来源

2010-06-23 01:51:59 Artelius

此外，你可以提供你自己的平等功能，像这样： nubBy ::（a - > a - > Bool） - > [a] - > [a] – 2010-06-23 10:22:55

如果巴特有时间我们可能会看到一个nubOrd，这将会更合理的表现明智。 – 2010-06-24 07:16:07

值得一提的是'nub'函数来自'Data.List'包。 – 2014-10-07 21:25:36

我认为唯一应该返回一个元素列表，只在原始列表中出现一次;也就是说，出现多次的原始列表中的任何元素都不应包含在结果中。

我可以提出一个替代的定义，unique_alt：

unique_alt :: [Int] -> [Int] 
    unique_alt [] = [] 
    unique_alt (x:xs) 
     | elem x (unique_alt xs) = [ y | y <- (unique_alt xs), y /= x ] 
     | otherwise    = x : (unique_alt xs)

下面是一些例子，强调unique_alt和unqiue之间的差异：

unique  [1,2,1]   = [2,1] 
    unique_alt [1,2,1]   = [2] 

    unique  [1,2,1,2]  = [1,2] 
    unique_alt [1,2,1,2]  = [] 

    unique  [4,2,1,3,2,3] = [4,1,2,3] 
    unique_alt [4,2,1,3,2,3] = [4,1]

来源

2012-08-10 10:22:37

这实际上就是Data.List.Unique（unique）的定义，虽然我个人认为，我从来没有运行过这个用例，而“squash lists只包含一个重复项”的函数是许多面包和黄油操作。 – 2015-11-07 19:28:12

import Data.Set (toList, fromList) 
uniquify lst = toList $ fromList lst

来源

2012-08-28 04:05:37 dpatru

+24

'uniquify = toList。 fromList' – muhmuhten 2012-09-16 02:29:15

这改变了元素的顺序。 – sjakobi 2016-07-22 22:13:28

-1

另一种方式来删除重复：

unique :: [Int] -> [Int] 
unique xs = [x | (x,y) <- zip xs [0..], x `notElem` (take y xs)]

来源

2013-01-05 03:13:44

算法在Haskell创造一个独特的名单：

data Foo = Foo { id_ :: Int 
       , name_ :: String 
       } deriving (Show) 

alldata = [ Foo 1 "Name" 
      , Foo 2 "Name" 
      , Foo 3 "Karl" 
      , Foo 4 "Karl" 
      , Foo 5 "Karl" 
      , Foo 7 "Tim" 
      , Foo 8 "Tim" 
      , Foo 9 "Gaby" 
      , Foo 9 "Name" 
      ] 

isolate :: [Foo] -> [Foo] 
isolate [] = [] 
isolate (x:xs) = (fst f) : isolate (snd f) 
    where 
    f = foldl helper (x,[]) xs 
    helper (a,b) y = if name_ x == name_ y 
        then if id_ x >= id_ y 
          then (x,b) 
          else (y,b) 
        else (a,y:b) 

main :: IO() 
main = mapM_ (putStrLn . show) (isolate alldata)

输出：

Foo {id_ = 9, name_ = "Name"} 
Foo {id_ = 9, name_ = "Gaby"} 
Foo {id_ = 5, name_ = "Karl"} 
Foo {id_ = 8, name_ = "Tim"}

来源

2016-05-02 11:59:11 Manuel

haskell list中的独特元素

回答

相关问题