Skip to content

Commit c80c8f0

Browse files
forkilatkin
forki
authored and
latkin
committed
Implement Array.takeWhile, List.takeWhile
Commits: implementing "takeWhile" for array and list Check for ArgumentNullException in Array.takeWhile Performance optimization for Array.takeWhile Do not use array slicing in Array.takeWhile Use a temporary array for List.takeWhile Use mutable list version instead of temp array for List.takeWhile Adding surface area for takeWhile Adding more test cases for takeWhile Fix bug in List.takeWhile where predicate of first element is false Apply dsyme's suggestion on takeWhile
1 parent 3c39e6e commit c80c8f0

10 files changed

Lines changed: 88 additions & 1 deletion

File tree

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

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -199,6 +199,19 @@ type ArrayModule() =
199199
CheckThrowsInvalidOperationExn (fun () -> Array.take 5 [|"str1";"str2";"str3";"str4"|] |> ignore)
200200
CheckThrowsArgumentNullException (fun () -> Array.take 5 null |> ignore)
201201

202+
[<Test>]
203+
member this.takeWhile() =
204+
Assert.AreEqual([||],Array.takeWhile (fun x -> failwith "should not be used") [||])
205+
Assert.AreEqual([|1;2;4;5|],Array.takeWhile (fun x -> x < 6) [|1;2;4;5;6;7|])
206+
Assert.AreEqual([|"a"; "ab"; "abc"|],Array.takeWhile (fun (x:string) -> x.Length < 4) [|"a"; "ab"; "abc"; "abcd"; "abcde"|])
207+
Assert.AreEqual([|"a"; "ab"; "abc"; "abcd"; "abcde"|],Array.takeWhile (fun _ -> true) [|"a"; "ab"; "abc"; "abcd"; "abcde"|])
208+
Assert.AreEqual([||],Array.takeWhile (fun _ -> false) [|"a"; "ab"; "abc"; "abcd"; "abcde"|])
209+
Assert.AreEqual([||],Array.takeWhile (fun _ -> false) [|"a"|])
210+
Assert.AreEqual([|"a"|],Array.takeWhile (fun _ -> true) [|"a"|])
211+
Assert.AreEqual([|"a"|],Array.takeWhile (fun x -> x <> "ab") [|"a"; "ab"; "abc"; "abcd"; "abcde"|])
212+
213+
CheckThrowsArgumentNullException (fun () -> Array.takeWhile (fun _ -> failwith "should not be used") null |> ignore)
214+
202215
[<Test>]
203216
member this.Blit() =
204217
// int array

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

Lines changed: 11 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -180,7 +180,6 @@ type ListModule() =
180180
let emptyChosen = List.choose funcInt emptySrc
181181
Assert.AreEqual(emptySrc, emptyChosen)
182182

183-
184183
()
185184

186185
[<Test>]
@@ -203,6 +202,17 @@ type ListModule() =
203202
Assert.AreEqual(0,List.compareWith (fun x y -> 0) ["1";"2"] ["1";"3"])
204203
Assert.AreEqual(1,List.compareWith (fun x y -> 1) ["1";"2"] ["1";"3"])
205204
Assert.AreEqual(-1,List.compareWith (fun x y -> -1) ["1";"2"] ["1";"3"])
205+
206+
[<Test>]
207+
member this.takeWhile() =
208+
Assert.AreEqual([],List.takeWhile (fun x -> failwith "should not be used") [])
209+
Assert.AreEqual([1;2;4;5],List.takeWhile (fun x -> x < 6) [1;2;4;5;6;7])
210+
Assert.AreEqual(["a"; "ab"; "abc"],List.takeWhile (fun (x:string) -> x.Length < 4) ["a"; "ab"; "abc"; "abcd"; "abcde"])
211+
Assert.AreEqual(["a"; "ab"; "abc"; "abcd"; "abcde"],List.takeWhile (fun _ -> true) ["a"; "ab"; "abc"; "abcd"; "abcde"])
212+
Assert.AreEqual([],List.takeWhile (fun _ -> false) ["a"; "ab"; "abc"; "abcd"; "abcde"])
213+
Assert.AreEqual([],List.takeWhile (fun _ -> false) ["a"])
214+
Assert.AreEqual(["a"],List.takeWhile (fun _ -> true) ["a"])
215+
Assert.AreEqual(["a"],List.takeWhile (fun x -> x <> "ab") ["a"; "ab"; "abc"; "abcd"; "abcde"])
206216

207217
[<Test>]
208218
member this.Concat() =

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

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -163,6 +163,7 @@ Microsoft.FSharp.Collections.ArrayModule: T[] Singleton[T](T)
163163
Microsoft.FSharp.Collections.ArrayModule: T[] SortBy[T,TKey](Microsoft.FSharp.Core.FSharpFunc`2[T,TKey], T[])
164164
Microsoft.FSharp.Collections.ArrayModule: T[] SortWith[T](Microsoft.FSharp.Core.FSharpFunc`2[T,Microsoft.FSharp.Core.FSharpFunc`2[T,System.Int32]], T[])
165165
Microsoft.FSharp.Collections.ArrayModule: T[] Sort[T](T[])
166+
Microsoft.FSharp.Collections.ArrayModule: T[] TakeWhile[T](Microsoft.FSharp.Core.FSharpFunc`2[T,System.Boolean], T[])
166167
Microsoft.FSharp.Collections.ArrayModule: T[] Take[T](Int32, T[])
167168
Microsoft.FSharp.Collections.ArrayModule: T[] Where[T](Microsoft.FSharp.Core.FSharpFunc`2[T,System.Boolean], T[])
168169
Microsoft.FSharp.Collections.ArrayModule: T[] ZeroCreate[T](Int32)
@@ -306,6 +307,7 @@ Microsoft.FSharp.Collections.ListModule: Microsoft.FSharp.Collections.FSharpList
306307
Microsoft.FSharp.Collections.ListModule: Microsoft.FSharp.Collections.FSharpList`1[T] SortWith[T](Microsoft.FSharp.Core.FSharpFunc`2[T,Microsoft.FSharp.Core.FSharpFunc`2[T,System.Int32]], Microsoft.FSharp.Collections.FSharpList`1[T])
307308
Microsoft.FSharp.Collections.ListModule: Microsoft.FSharp.Collections.FSharpList`1[T] Sort[T](Microsoft.FSharp.Collections.FSharpList`1[T])
308309
Microsoft.FSharp.Collections.ListModule: Microsoft.FSharp.Collections.FSharpList`1[T] Tail[T](Microsoft.FSharp.Collections.FSharpList`1[T])
310+
Microsoft.FSharp.Collections.ListModule: Microsoft.FSharp.Collections.FSharpList`1[T] TakeWhile[T](Microsoft.FSharp.Core.FSharpFunc`2[T,System.Boolean], Microsoft.FSharp.Collections.FSharpList`1[T])
309311
Microsoft.FSharp.Collections.ListModule: Microsoft.FSharp.Collections.FSharpList`1[T] Take[T](Int32, Microsoft.FSharp.Collections.FSharpList`1[T])
310312
Microsoft.FSharp.Collections.ListModule: Microsoft.FSharp.Collections.FSharpList`1[T] Where[T](Microsoft.FSharp.Core.FSharpFunc`2[T,System.Boolean], Microsoft.FSharp.Collections.FSharpList`1[T])
311313
Microsoft.FSharp.Collections.ListModule: Microsoft.FSharp.Core.FSharpOption`1[System.Int32] TryFindIndex[T](Microsoft.FSharp.Core.FSharpFunc`2[T,System.Boolean], Microsoft.FSharp.Collections.FSharpList`1[T])

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

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -157,6 +157,7 @@ Microsoft.FSharp.Collections.ArrayModule: T[] Singleton[T](T)
157157
Microsoft.FSharp.Collections.ArrayModule: T[] SortBy[T,TKey](Microsoft.FSharp.Core.FSharpFunc`2[T,TKey], T[])
158158
Microsoft.FSharp.Collections.ArrayModule: T[] SortWith[T](Microsoft.FSharp.Core.FSharpFunc`2[T,Microsoft.FSharp.Core.FSharpFunc`2[T,System.Int32]], T[])
159159
Microsoft.FSharp.Collections.ArrayModule: T[] Sort[T](T[])
160+
Microsoft.FSharp.Collections.ArrayModule: T[] TakeWhile[T](Microsoft.FSharp.Core.FSharpFunc`2[T,System.Boolean], T[])
160161
Microsoft.FSharp.Collections.ArrayModule: T[] Take[T](Int32, T[])
161162
Microsoft.FSharp.Collections.ArrayModule: T[] Where[T](Microsoft.FSharp.Core.FSharpFunc`2[T,System.Boolean], T[])
162163
Microsoft.FSharp.Collections.ArrayModule: T[] ZeroCreate[T](Int32)
@@ -300,6 +301,7 @@ Microsoft.FSharp.Collections.ListModule: Microsoft.FSharp.Collections.FSharpList
300301
Microsoft.FSharp.Collections.ListModule: Microsoft.FSharp.Collections.FSharpList`1[T] SortWith[T](Microsoft.FSharp.Core.FSharpFunc`2[T,Microsoft.FSharp.Core.FSharpFunc`2[T,System.Int32]], Microsoft.FSharp.Collections.FSharpList`1[T])
301302
Microsoft.FSharp.Collections.ListModule: Microsoft.FSharp.Collections.FSharpList`1[T] Sort[T](Microsoft.FSharp.Collections.FSharpList`1[T])
302303
Microsoft.FSharp.Collections.ListModule: Microsoft.FSharp.Collections.FSharpList`1[T] Tail[T](Microsoft.FSharp.Collections.FSharpList`1[T])
304+
Microsoft.FSharp.Collections.ListModule: Microsoft.FSharp.Collections.FSharpList`1[T] TakeWhile[T](Microsoft.FSharp.Core.FSharpFunc`2[T,System.Boolean], Microsoft.FSharp.Collections.FSharpList`1[T])
303305
Microsoft.FSharp.Collections.ListModule: Microsoft.FSharp.Collections.FSharpList`1[T] Take[T](Int32, Microsoft.FSharp.Collections.FSharpList`1[T])
304306
Microsoft.FSharp.Collections.ListModule: Microsoft.FSharp.Collections.FSharpList`1[T] Where[T](Microsoft.FSharp.Core.FSharpFunc`2[T,System.Boolean], Microsoft.FSharp.Collections.FSharpList`1[T])
305307
Microsoft.FSharp.Collections.ListModule: Microsoft.FSharp.Core.FSharpOption`1[System.Int32] TryFindIndex[T](Microsoft.FSharp.Core.FSharpFunc`2[T,System.Boolean], Microsoft.FSharp.Collections.FSharpList`1[T])

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

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -120,6 +120,19 @@ namespace Microsoft.FSharp.Collections
120120
Array.Copy(array, 0, res, 0, count)
121121
res
122122

123+
[<CompiledName("TakeWhile")>]
124+
let takeWhile predicate (array: 'T[]) =
125+
checkNonNull "array" array
126+
if array.Length = 0 then empty else
127+
let mutable count = 0
128+
while count < array.Length && predicate array.[count] do
129+
count <- count + 1
130+
131+
let res : 'T[] = Microsoft.FSharp.Primitives.Basics.Array.zeroCreateUnchecked count
132+
133+
Array.Copy(array, 0, res, 0, count)
134+
res
135+
123136
[<CompiledName("Append")>]
124137
let append (array1:'T[]) (array2:'T[]) =
125138
checkNonNull "array1" array1

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

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -657,6 +657,18 @@ namespace Microsoft.FSharp.Collections
657657
[<CompiledName("Take")>]
658658
val take: count:int -> array:'T[] -> 'T[]
659659

660+
/// <summary>Returns an array that contains all elements of the original array while the
661+
/// given predicate returns <c>true</c>, and then returns no further elements.</summary>
662+
///
663+
/// <param name="predicate">A function that evaluates to false when no more items should be returned.</param>
664+
/// <param name="array">The input array.</param>
665+
///
666+
/// <returns>The result array.</returns>
667+
///
668+
/// <exception cref="System.ArgumentNullException">Thrown when the input array is null.</exception>
669+
[<CompiledName("TakeWhile")>]
670+
val takeWhile: predicate:('T -> bool) -> array:'T[] -> 'T[]
671+
660672
/// <summary>Builds a list from the given array.</summary>
661673
/// <param name="array">The input array.</param>
662674
/// <returns>The list of array elements.</returns>

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

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -90,6 +90,9 @@ namespace Microsoft.FSharp.Collections
9090
[<CompiledName("Take")>]
9191
let take count (list : 'T list) = Microsoft.FSharp.Primitives.Basics.List.take count list
9292

93+
[<CompiledName("TakeWhile")>]
94+
let takeWhile p (list: 'T list) = Microsoft.FSharp.Primitives.Basics.List.takeWhile p list
95+
9396
[<CompiledName("IterateIndexed")>]
9497
let iteri f list = Microsoft.FSharp.Primitives.Basics.List.iteri f list
9598

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

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -587,6 +587,16 @@ namespace Microsoft.FSharp.Collections
587587
[<CompiledName("Take")>]
588588
val take: count:int -> list:'T list -> 'T list
589589

590+
/// <summary>Returns a list that contains all elements of the original list while the
591+
/// given predicate returns <c>true</c>, and then returns no further elements.</summary>
592+
///
593+
/// <param name="predicate">A function that evaluates to false when no more items should be returned.</param>
594+
/// <param name="list">The input list.</param>
595+
///
596+
/// <returns>The result list.</returns>
597+
[<CompiledName("TakeWhile")>]
598+
val takeWhile: predicate:('T -> bool) -> list:'T list -> 'T list
599+
590600
/// <summary>Builds an array from the given list.</summary>
591601
/// <param name="list">The input list.</param>
592602
/// <returns>The array containing the elements of the list.</returns>

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

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -466,6 +466,27 @@ module internal List =
466466
res <- arr.[i] :: res
467467
res
468468

469+
let rec takeWhileFreshConsTail cons p l =
470+
match l with
471+
| [] -> setFreshConsTail cons []
472+
| x::xs ->
473+
if p x then
474+
let cons2 = freshConsNoTail x
475+
setFreshConsTail cons cons2
476+
takeWhileFreshConsTail cons2 p xs
477+
else
478+
setFreshConsTail cons []
479+
480+
let takeWhile p (l: 'T list) =
481+
match l with
482+
| [] -> l
483+
| x :: ([] as nil) -> if p x then l else nil
484+
| x::xs ->
485+
if not (p x) then [] else
486+
let cons = freshConsNoTail x
487+
takeWhileFreshConsTail cons p xs
488+
cons
489+
469490
// NOTE: This implementation is now only used for List.sortWith. We should change that to use the stable sort via arrays
470491
// below, and remove this implementation.
471492
module StableSortImplementation =

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

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -28,6 +28,7 @@ module internal List =
2828
val zip3 : 'T1 list -> 'T2 list -> 'T3 list -> ('T1 * 'T2 * 'T3) list
2929
val ofArray : 'T[] -> 'T list
3030
val take : int -> 'T list -> 'T list
31+
val takeWhile : ('T -> bool) -> 'T list -> 'T list
3132
val toArray : 'T list -> 'T[]
3233
val sortWith : ('T -> 'T -> int) -> 'T list -> 'T list
3334

0 commit comments

Comments
 (0)