-
Notifications
You must be signed in to change notification settings - Fork 199
/
BuiltinOrder.daml
148 lines (137 loc) · 4.38 KB
/
BuiltinOrder.daml
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
-- Copyright (c) 2021 Digital Asset (Switzerland) GmbH and/or its affiliates. All rights reserved.
-- SPDX-License-Identifier: Apache-2.0
-- | Note: This is only supported in DAML-LF 1.11 or later.
--
-- This module provides variants of other standard library
-- functions that are based on the builtin Daml-LF ordering rather
-- than user-defined ordering. This is the same order also used
-- by `DA.Map`.
--
-- These functions are usually much more efficient than their
-- `Ord`-based counterparts.
--
-- Note that the functions in this module still require `Ord`
-- constraints. This is purely to enforce that you don’t
-- pass in values that cannot be compared, e.g., functions. The
-- implementation of those instances is not used.
module DA.List.BuiltinOrder
( dedup
, dedupOn
, dedupSort
, dedupOnSort
, sort
, sortOn
, unique
, uniqueOn
) where
import DA.Map (Map)
import qualified DA.Map as Map
-- | `dedup l` removes duplicate elements from a list. In particular,
-- it keeps only the first occurrence of each element.
--
-- `dedup` is stable so the elements in the output are ordered
-- by their first occurrence in the input. If you do not need
-- stability, consider using `dedupSort` which is more efficient.
--
-- ```
-- >>> dedup [3, 1, 1, 3]
-- [3, 1]
-- ```
dedup : Ord a => [a] -> [a]
dedup = dedupOn identity
-- | A version of `dedup` where deduplication is done
-- after applying the given function. Example use: `dedupOn (.employeeNo) employees`.
--
-- `dedupOn` is stable so the elements in the output are ordered
-- by their first occurrence in the input. If you do not need
-- stability, consider using `dedupOnSort` which is more efficient.
--
-- ```
-- >>> dedupOn fst [(3, "a"), (1, "b"), (1, "c"), (3, "d")]
-- [(3, "a"), (1, "b")]
-- ```
dedupOn f xs = Map.values (Map.fromList (Map.values deduped))
where
-- Fused Map.fromListWith + map/fold
deduped = snd (foldl insert (0, Map.empty) xs)
insert (i, m) x =
let k = f x
m' = case Map.lookup k m of
Some prev@(j, _)
| j <= i -> m
_ -> Map.insert k (i, x) m
in (i + 1, m')
-- | `dedupSort` is a more efficient variant of `dedup`
-- that does not preserve the order of the input elements.
-- Instead the output will be sorted acoording to the builtin Daml-LF
-- ordering.
--
-- ```
-- >>> dedupSort [3, 1, 1, 3]
-- [1, 3]
-- ```
dedupSort : Ord a => [a] -> [a]
dedupSort = dedupOnSort identity
-- | `dedupOnSort` is a more efficient variant of `dedupOn`
-- that does not preserve the order of the input elements.
-- Instead the output will be sorted on the values returned by the function.
--
-- For duplicates, the first element in the list will be included in the output.
--
-- ```
-- >>> dedupOnSort fst [(3, "a"), (1, "b"), (1, "c"), (3, "d")]
-- [(1, "b"), (3, "a")]
-- ```
dedupOnSort f xs =
let deduped = foldr (\x acc -> Map.insert (f x) x acc) Map.empty xs
in Map.values deduped
-- | Sort the list according to the Daml-LF ordering.
--
-- Values that are identical according to the builtin Daml-LF ordering
-- are indistinguishable so stability is not relevant here.
--
-- ```
-- >>> sort [3,1,2]
-- [1,2,3]
-- ```
sort : Ord a => [a] -> [a]
sort = sortOn identity
-- | `sortOn f` is a version of sort that allows sorting
-- on the result of the given function.
--
-- `sortOn` is stable so elements that map to the same sort key
-- will be ordered by their position in the input.
--
-- ```
-- >>> sortOn fst [(3, "a"), (1, "b"), (3, "c"), (2, "d")]
-- [(1, "b"), (2, "d"), (3, "a"), (3, "c")]
-- ```
sortOn : Ord b => (a -> b) -> [a] -> [a]
sortOn f xs = Map.values (snd (foldl insert (0, Map.empty) xs))
where
insert (i, m) x = (i + 1, Map.insert (f x, i) x m)
-- | Returns True if and only if there are no duplicate elements in the given list.
--
-- ```
-- >>> unique [1, 2, 3]
-- True
-- ```
unique : Ord a => [a] -> Bool
unique = uniqueOn identity
-- | Returns True if and only if there are no duplicate elements in the given list
-- after applyng function.
--
-- ```
-- >>> uniqueOn fst [(1, 2), (2, 42), (1, 3)]
-- False
-- ```
uniqueOn : Ord k => (a -> k) -> [a] -> Bool
uniqueOn f = goUniqueOn f Map.empty
-- hand-written recursion to shortcircuit.
goUniqueOn : Ord k => (a -> k) -> Map k () -> [a] -> Bool
goUniqueOn _ _ [] = True
goUniqueOn f m (x :: xs) =
let k = f x
in case Map.lookup (f x) m of
None -> goUniqueOn f (Map.insert k () m) xs
Some _ -> False