Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitbebe9a2

Browse files
forkilatkin
authored andcommitted
Implement Array.distinct, List.distinct
Commits: implementing "distinct" for array and list fix typo Use a HashSet instead of dictionary for "distinct" Show possible ArgumentNullException in docs for Array.distinct Use only one test method for "distinct" Adding surface area for "distinct" Use mutable list for "distinct" Make Array.distinct use a temp array instead of array comprehension Adding some test cases for distinct We don't need StructBox any more in Array.distinct We don't need StructBox any more in List.distinct We don't need StructBox any more in Seq.distinct Move the List.distinct back to local.fs Add test cases for distinct which show null handling Fix typos
1 parent70146cf commitbebe9a2

File tree

11 files changed

+109
-9
lines changed

11 files changed

+109
-9
lines changed

‎src/fsharp/FSharp.Core.Unittests/FSharp.Core/Microsoft.FSharp.Collections/ArrayModule.fs‎

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -143,6 +143,26 @@ type ArrayModule() =
143143
CheckThrowsArgumentNullException(fun()-> Array.averageBy funcd nullArr|> ignore)
144144

145145
()
146+
147+
[<Test>]
148+
memberthis.distinct()=
149+
// distinct should work on empty array
150+
Assert.AreEqual([||], Array.distinct[||])
151+
152+
// distinct not should work on null
153+
CheckThrowsArgumentNullException(fun()-> Array.distinctnull|> ignore)
154+
155+
// distinct should filter out simple duplicates
156+
Assert.AreEqual([|1|], Array.distinct[|1|])
157+
Assert.AreEqual([|1|], Array.distinct[|1;1|])
158+
Assert.AreEqual([|1;2;3|], Array.distinct[|1;2;3;1|])
159+
Assert.AreEqual([|[1;2];[1;3]|], Array.distinct[|[1;2];[1;3];[1;2];[1;3]|])
160+
Assert.AreEqual([|[1;1];[1;2];[1;3];[1;4]|], Array.distinct[|[1;1];[1;2];[1;3];[1;4]|])
161+
Assert.AreEqual([|[1;1];[1;4]|], Array.distinct[|[1;1];[1;1];[1;1];[1;4]|])
162+
163+
Assert.AreEqual([|null|], Array.distinct[|null|])
164+
letlist=new System.Collections.Generic.List<int>()
165+
Assert.AreEqual([|null, list|], Array.distinct[|null, list|])
146166

147167
[<Test>]
148168
memberthis.Blit()=

‎src/fsharp/FSharp.Core.Unittests/FSharp.Core/Microsoft.FSharp.Collections/ListModule.fs‎

Lines changed: 17 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -46,7 +46,7 @@ type ListModule() =
4646
()
4747

4848
[<Test>]
49-
memberthis.Avarage()=
49+
memberthis.Average()=
5050
// empty float32 List
5151
letemptyFloatList= List.empty<System.Single>
5252
CheckThrowsArgumentException(fun()-> List.average emptyFloatList|> ignore)
@@ -77,7 +77,6 @@ type ListModule() =
7777

7878
()
7979

80-
8180
[<Test>]
8281
memberthis.AverageBy()=
8382
// empty double List
@@ -109,7 +108,23 @@ type ListModule() =
109108

110109
()
111110

111+
[<Test>]
112+
memberthis.distinct()=
113+
// distinct should work on empty list
114+
Assert.AreEqual([], List.distinct[])
115+
116+
// distinct should filter out simple duplicates
117+
Assert.AreEqual([1], List.distinct[1])
118+
Assert.AreEqual([1], List.distinct[1;1])
119+
Assert.AreEqual([1;2;3], List.distinct[1;2;3;1])
120+
Assert.AreEqual([[1;2];[1;3]], List.distinct[[1;2];[1;3];[1;2];[1;3]])
121+
Assert.AreEqual([[1;1];[1;2];[1;3];[1;4]], List.distinct[[1;1];[1;2];[1;3];[1;4]])
122+
Assert.AreEqual([[1;1];[1;4]], List.distinct[[1;1];[1;1];[1;1];[1;4]])
112123

124+
Assert.AreEqual([null], List.distinct[null])
125+
letlist=new System.Collections.Generic.List<int>()
126+
Assert.AreEqual([null, list], List.distinct[null, list])
127+
113128

114129
[<Test>]
115130
memberthis.Choose()=

‎src/fsharp/FSharp.Core.Unittests/SurfaceArea.4.0.fs‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -149,6 +149,7 @@ Microsoft.FSharp.Collections.ArrayModule: T[] Append[T](T[], T[])
149149
Microsoft.FSharp.Collections.ArrayModule: T[] Concat[T](System.Collections.Generic.IEnumerable`1[T[]])
150150
Microsoft.FSharp.Collections.ArrayModule: T[] Copy[T](T[])
151151
Microsoft.FSharp.Collections.ArrayModule: T[] Create[T](Int32, T)
152+
Microsoft.FSharp.Collections.ArrayModule: T[] Distinct[T](T[])
152153
Microsoft.FSharp.Collections.ArrayModule: T[] Empty[T]()
153154
Microsoft.FSharp.Collections.ArrayModule: T[] Filter[T](Microsoft.FSharp.Core.FSharpFunc`2[T,System.Boolean], T[])
154155
Microsoft.FSharp.Collections.ArrayModule: T[] GetSubArray[T](T[], Int32, Int32)
@@ -288,6 +289,7 @@ Microsoft.FSharp.Collections.ListModule: Microsoft.FSharp.Collections.FSharpList
288289
Microsoft.FSharp.Collections.ListModule: Microsoft.FSharp.Collections.FSharpList`1[TState] Scan[T,TState](Microsoft.FSharp.Core.FSharpFunc`2[TState,Microsoft.FSharp.Core.FSharpFunc`2[T,TState]], TState, Microsoft.FSharp.Collections.FSharpList`1[T])
289290
Microsoft.FSharp.Collections.ListModule: Microsoft.FSharp.Collections.FSharpList`1[T] Append[T](Microsoft.FSharp.Collections.FSharpList`1[T], Microsoft.FSharp.Collections.FSharpList`1[T])
290291
Microsoft.FSharp.Collections.ListModule: Microsoft.FSharp.Collections.FSharpList`1[T] Concat[T](System.Collections.Generic.IEnumerable`1[Microsoft.FSharp.Collections.FSharpList`1[T]])
292+
Microsoft.FSharp.Collections.ListModule: Microsoft.FSharp.Collections.FSharpList`1[T] Distinct[T](Microsoft.FSharp.Collections.FSharpList`1[T])
291293
Microsoft.FSharp.Collections.ListModule: Microsoft.FSharp.Collections.FSharpList`1[T] Empty[T]()
292294
Microsoft.FSharp.Collections.ListModule: Microsoft.FSharp.Collections.FSharpList`1[T] Filter[T](Microsoft.FSharp.Core.FSharpFunc`2[T,System.Boolean], Microsoft.FSharp.Collections.FSharpList`1[T])
293295
Microsoft.FSharp.Collections.ListModule: Microsoft.FSharp.Collections.FSharpList`1[T] Initialize[T](Int32, Microsoft.FSharp.Core.FSharpFunc`2[System.Int32,T])

‎src/fsharp/FSharp.Core.Unittests/SurfaceArea.Portable.fs‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -143,6 +143,7 @@ Microsoft.FSharp.Collections.ArrayModule: T[] Append[T](T[], T[])
143143
Microsoft.FSharp.Collections.ArrayModule: T[] Concat[T](System.Collections.Generic.IEnumerable`1[T[]])
144144
Microsoft.FSharp.Collections.ArrayModule: T[] Copy[T](T[])
145145
Microsoft.FSharp.Collections.ArrayModule: T[] Create[T](Int32, T)
146+
Microsoft.FSharp.Collections.ArrayModule: T[] Distinct[T](T[])
146147
Microsoft.FSharp.Collections.ArrayModule: T[] Empty[T]()
147148
Microsoft.FSharp.Collections.ArrayModule: T[] Filter[T](Microsoft.FSharp.Core.FSharpFunc`2[T,System.Boolean], T[])
148149
Microsoft.FSharp.Collections.ArrayModule: T[] GetSubArray[T](T[], Int32, Int32)
@@ -282,6 +283,7 @@ Microsoft.FSharp.Collections.ListModule: Microsoft.FSharp.Collections.FSharpList
282283
Microsoft.FSharp.Collections.ListModule: Microsoft.FSharp.Collections.FSharpList`1[TState] Scan[T,TState](Microsoft.FSharp.Core.FSharpFunc`2[TState,Microsoft.FSharp.Core.FSharpFunc`2[T,TState]], TState, Microsoft.FSharp.Collections.FSharpList`1[T])
283284
Microsoft.FSharp.Collections.ListModule: Microsoft.FSharp.Collections.FSharpList`1[T] Append[T](Microsoft.FSharp.Collections.FSharpList`1[T], Microsoft.FSharp.Collections.FSharpList`1[T])
284285
Microsoft.FSharp.Collections.ListModule: Microsoft.FSharp.Collections.FSharpList`1[T] Concat[T](System.Collections.Generic.IEnumerable`1[Microsoft.FSharp.Collections.FSharpList`1[T]])
286+
Microsoft.FSharp.Collections.ListModule: Microsoft.FSharp.Collections.FSharpList`1[T] Distinct[T](Microsoft.FSharp.Collections.FSharpList`1[T])
285287
Microsoft.FSharp.Collections.ListModule: Microsoft.FSharp.Collections.FSharpList`1[T] Empty[T]()
286288
Microsoft.FSharp.Collections.ListModule: Microsoft.FSharp.Collections.FSharpList`1[T] Filter[T](Microsoft.FSharp.Core.FSharpFunc`2[T,System.Boolean], Microsoft.FSharp.Collections.FSharpList`1[T])
287289
Microsoft.FSharp.Collections.ListModule: Microsoft.FSharp.Collections.FSharpList`1[T] Initialize[T](Int32, Microsoft.FSharp.Core.FSharpFunc`2[System.Int32,T])

‎src/fsharp/FSharp.Core/array.fs‎

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -146,6 +146,22 @@ namespace Microsoft.FSharp.Collections
146146
for i=0to len-1do
147147
f array.[i]
148148

149+
[<CompiledName("Distinct")>]
150+
letdistinct(array:'T[])=
151+
checkNonNull"array" array
152+
lettemp= Microsoft.FSharp.Primitives.Basics.Array.zeroCreateUnchecked array.Length
153+
let mutablei=0
154+
155+
lethashSet= HashSet<'T>(HashIdentity.Structural<'T>)
156+
for vin arraydo
157+
if hashSet.Add(v)then
158+
temp.[i]<- v
159+
i<- i+1
160+
161+
letres= Microsoft.FSharp.Primitives.Basics.Array.zeroCreateUnchecked i: 'T[]
162+
Array.Copy(temp,0, res,0, i)
163+
res
164+
149165
[<CompiledName("Map")>]
150166
let inlinemap(f:'T->'U)(array:'T[])=
151167
checkNonNull"array" array

‎src/fsharp/FSharp.Core/array.fsi‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -138,6 +138,18 @@ namespace Microsoft.FSharp.Collections
138138
[<CompiledName("Choose")>]
139139
val choose:chooser:('T-> 'U option)->array:'T[]-> 'U[]
140140

141+
///<summary>Returns an array that contains no duplicate entries according to generic hash and
142+
///equality comparisons on the entries.
143+
///If an element occurs multiple times in the array then the later occurrences are discarded.</summary>
144+
///
145+
///<param name="array">The input array.</param>
146+
///
147+
///<returns>The result array.</returns>
148+
///
149+
///<exception cref="System.ArgumentNullException">Thrown when the input array is null.</exception>
150+
[<CompiledName("Distinct")>]
151+
val distinct:array:'T[]-> 'T[]when 'T:equality
152+
141153
///<summary>Returns an empty array of the given type.</summary>
142154
[<GeneralizableValue>]
143155
[<CompiledName("Empty")>]

‎src/fsharp/FSharp.Core/list.fs‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -40,6 +40,9 @@ namespace Microsoft.FSharp.Collections
4040

4141
[<CompiledName("Iterate")>]
4242
letiter f list= Microsoft.FSharp.Primitives.Basics.List.iter f list
43+
44+
[<CompiledName("Distinct")>]
45+
letdistinct(list:'T list)= Microsoft.FSharp.Primitives.Basics.List.distinct HashIdentity.Structural<'T> list
4346

4447
[<CompiledName("OfArray")>]
4548
letofArray(array:'T array)= Microsoft.FSharp.Primitives.Basics.List.ofArray array

‎src/fsharp/FSharp.Core/list.fsi‎

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -88,6 +88,16 @@ namespace Microsoft.FSharp.Collections
8888
[<CompiledName("Contains")>]
8989
val inline contains:value:'T->source:'T list->bool when 'T:equality
9090

91+
///<summary>Returns a list that contains no duplicate entries according to generic hash and
92+
///equality comparisons on the entries.
93+
///If an element occurs multiple times in the list then the later occurrences are discarded.</summary>
94+
///
95+
///<param name="list">The input list.</param>
96+
///
97+
///<returns>The result list.</returns>
98+
[<CompiledName("Distinct")>]
99+
val distinct:list:'T list-> 'T list when 'T:equality
100+
91101
///<summary>Returns an empty list of the given type.</summary>
92102
[<GeneralizableValue>]
93103
[<CompiledName("Empty")>]

‎src/fsharp/FSharp.Core/local.fs‎

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -30,6 +30,28 @@ module internal List =
3030
let inlinesetFreshConsTail cons t= cons.(::).1<- t
3131
let inlinefreshConsNoTail h= h::(#"ldnull": 'T list #)
3232

33+
let recdistinctToFreshConsTail cons(hashSet:HashSet<_>)list=
34+
match listwith
35+
|[]-> setFreshConsTail cons[]
36+
|(x::rest)->
37+
if hashSet.Add(x)then
38+
letcons2= freshConsNoTail x
39+
setFreshConsTail cons cons2
40+
distinctToFreshConsTail cons2 hashSet rest
41+
else
42+
distinctToFreshConsTail cons hashSet rest
43+
44+
letdistinct(comparer:System.Collections.Generic.IEqualityComparer<'T>)(list:'T list)=
45+
match listwith
46+
|[]->[]
47+
|[h]->[h]
48+
|(x::rest)->
49+
lethashSet= System.Collections.Generic.HashSet<'T>(comparer)
50+
hashSet.Add(x)|> ignore
51+
letcons= freshConsNoTail x
52+
distinctToFreshConsTail cons hashSet rest
53+
cons
54+
3355

3456
let recmapToFreshConsTail cons f x=
3557
match xwith

‎src/fsharp/FSharp.Core/local.fsi‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -7,6 +7,7 @@ open Microsoft.FSharp.Core
77
openMicrosoft.FSharp.Collections
88

99
moduleinternalList=
10+
valdistinct:System.Collections.Generic.IEqualityComparer<'T>->'T list->'T list
1011
valinit:int->(int->'T)->'T list
1112
valiter:('T-> unit)->'T list->unit
1213
valfilter:predicate:('T-> bool)->'T list->'T list

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp