# Ticket #2629: Nub.hs

File Nub.hs, 2.4 KB (added by , 8 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 | |

10 | module Nub (StopList, nubWith, nub, nubOrd, nubInt) |

11 | where |

12 | |

13 | import qualified Data.Set as Set |

14 | import 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. |

20 | class 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 | |

26 | instance (Eq e) => StopList e [e] where |

27 | emptyS = [] |

28 | memberS = elem |

29 | insertS = (:) |

30 | |

31 | instance (Ord e) => StopList e (Set.Set e) where |

32 | emptyS = Set.empty |

33 | memberS = Set.member |

34 | insertS = Set.insert |

35 | |

36 | instance 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. |

45 | nubWith :: (StopList e s) => s -> [e] -> [e] |

46 | nubWith _ [] = [] |

47 | nubWith 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". |

57 | nub :: (Eq e) => [e] -> [e] |

58 | nub = 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. |

63 | nubOrd :: (Ord e) => [e] -> [e] |

64 | nubOrd = 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. |

70 | nubInt :: [Int] -> [Int] |

71 | nubInt = nubWith IntSet.empty |