Ticket #2629: Nub.hs

File Nub.hs, 2.4 KB (added by Bart Massey, 6 years ago)
Line 
1--- Copyright © 2008 Bart Massey
2--- ALL RIGHTS RESERVED
3--- [This program is licensed under the "3-clause ('new') BSD License"]
4--- Please see the file COPYING in the source
5--- distribution of this software for license terms.
6
7{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances,
8             FunctionalDependencies #-}
9
10module Nub (StopList, nubWith, nub, nubOrd, nubInt)
11where
12
13import qualified Data.Set as Set
14import qualified Data.IntSet as IntSet
15
16-- | In artificial intelligence, a 'StopList' is a
17-- list of values that should be ignored in further
18-- processing.  'nubWith' uses a stop list to filter
19-- out duplicate elements.
20class StopList e s | s -> e where
21    emptyS :: s  -- ^ The empty stop list.
22    memberS :: e -> s -> Bool  -- ^ Is e an element of s?
23    insertS :: e -> s -> s  -- ^ Add e to s.  If e is already in s, the
24                            -- result is undefined.
25
26instance (Eq e) => StopList e [e] where
27    emptyS = []
28    memberS = elem
29    insertS = (:)
30
31instance (Ord e) => StopList e (Set.Set e) where
32    emptyS = Set.empty
33    memberS = Set.member
34    insertS = Set.insert
35
36instance StopList Int IntSet.IntSet where
37    emptyS = IntSet.empty
38    memberS = IntSet.member
39    insertS = IntSet.insert
40
41-- | The 'nubWith' function accepts as an argument
42-- a "stop list", a set of list elements that it
43-- uses as a filter to remove duplicate elements.
44-- The supplied filter is normally initially empty.
45nubWith :: (StopList e s) => s -> [e] -> [e]
46nubWith _ [] = []
47nubWith s (e : es)
48    | memberS e s = nubWith s es
49    | otherwise = e : nubWith (insertS e s) es
50
51-- | The 'nub' function removes duplicate elements from a list.
52-- In particular, it keeps only the first occurrence of each element.
53-- (The name 'nub' means \`essence\'.)
54-- It is a special case of 'nubBy', which allows the programmer to supply
55-- their own equality test.  It is also a special case of 'nubWith', which
56-- allows the programmer to specify their own "stop list".
57nub :: (Eq e) => [e] -> [e]
58nub = nubWith []
59
60-- | The 'nubOrd' function is much more efficient on ordered
61-- datatypes than 'nub'.  It is a special case of 'nubWith' with
62-- a 'Set' stop list.
63nubOrd :: (Ord e) => [e] -> [e]
64nubOrd = nubWith Set.empty
65
66-- | The 'nubInt' function is much more efficient on
67-- 'Int' lists than 'nub', and somewhat more efficient than
68-- 'nubOrd'.  It is a special case of 'nubWith' with
69-- an 'IntSet' stop list.
70nubInt :: [Int] -> [Int]
71nubInt = nubWith IntSet.empty