Skip to content

Commit 366777f

Browse files
PatrickMcDonaldlatkin
PatrickMcDonald
authored and
latkin
committed
Implement Seq.foldBack, Seq.reduceBack
commit b80eba279fa2f948674b466211c356868af83275 Author: latkin <latkin@microsoft.com> Date: Tue Oct 21 13:26:29 2014 -0700 Add a couple test cases for length-1 seqs commit e8080990fb9571bdbd0f93ce9afa6419da42772c Author: latkin <latkin@microsoft.com> Date: Tue Oct 21 13:19:59 2014 -0700 Normalizing doc comments across array, list, seq commit 5a51ef31350aec0b679bd4981827919b8c285699 Merge: 1b31d64 58b2330 Author: latkin <latkin@microsoft.com> Date: Tue Oct 21 12:30:18 2014 -0700 Merge branch 'foldBack' of https://git01.codeplex.com/forks/patrickmcdonald/visualfsharp into PR Conflicts: src/fsharp/FSharp.Core.Unittests/SurfaceArea.4.0.fs src/fsharp/FSharp.Core.Unittests/SurfaceArea.Portable.fs src/fsharp/FSharp.Core/seq.fsi commit 58b233045a597a5078d8695fdf8d8ce4d771d690 Author: Patrick McDonald <paddymcdonald@gmail.com> Date: Sat Aug 16 23:32:32 2014 +0100 Implement Seq.foldBack and Seq.reduceBack
1 parent 627c016 commit 366777f

8 files changed

Lines changed: 129 additions & 14 deletions

File tree

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

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -702,6 +702,42 @@ type SeqModule() =
702702
CheckThrowsArgumentNullException (fun () -> Seq.fold2 funcInt 0 (seq [1]) nullSeq |> ignore)
703703
()
704704

705+
[<Test>]
706+
member this.FoldBack() =
707+
// int Seq
708+
let funcInt x y = x-y
709+
let IntSeq = seq { 1..4 }
710+
let foldInt = Seq.foldBack funcInt IntSeq 6
711+
Assert.AreEqual((1-(2-(3-(4-6)))), foldInt)
712+
713+
// string Seq
714+
let funcStr (x:string) (y:string) = y.Remove(0,x.Length)
715+
let strSeq = seq [ "A"; "B"; "C"; "D" ]
716+
let foldStr = Seq.foldBack funcStr strSeq "ABCDE"
717+
Assert.AreEqual("E", foldStr)
718+
719+
// single element
720+
let funcStr2 elem acc = sprintf "%s%s" elem acc
721+
let strSeq2 = seq [ "A" ]
722+
let foldStr2 = Seq.foldBack funcStr2 strSeq2 "X"
723+
Assert.AreEqual("AX", foldStr2)
724+
725+
// Empty Seq
726+
let emptySeq = Seq.empty
727+
let foldEmpty = Seq.foldBack funcInt emptySeq 1
728+
Assert.AreEqual(1, foldEmpty)
729+
730+
// null Seq
731+
let nullSeq:seq<'a> = null
732+
CheckThrowsArgumentNullException (fun () -> Seq.foldBack funcInt nullSeq 1 |> ignore)
733+
734+
// Validate that foldBack with the cons operator and the empty list returns a copy of the sequence
735+
let cons x y = x :: y
736+
let identityFoldr = Seq.foldBack cons IntSeq []
737+
Assert.AreEqual([1;2;3;4], identityFoldr)
738+
739+
()
740+
705741
[<Test>]
706742
member this.ForAll() =
707743

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

Lines changed: 29 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -918,7 +918,35 @@ type SeqModule2() =
918918
CheckThrowsArgumentNullException (fun () -> Seq.reduce (fun (x:string) (y:string) -> x.Remove(0,y.Length)) nullSeq |> ignore)
919919
()
920920

921-
921+
[<Test>]
922+
member this.ReduceBack() =
923+
// int Seq
924+
let funcInt x y = x - y
925+
let IntSeq = seq { 1..4 }
926+
let reduceInt = Seq.reduceBack funcInt IntSeq
927+
Assert.AreEqual((1-(2-(3-4))), reduceInt)
928+
929+
// string Seq
930+
let funcStr (x:string) (y:string) = y.Remove(0,x.Length)
931+
let strSeq = seq [ "A"; "B"; "C"; "D" ; "ABCDE" ]
932+
let reduceStr = Seq.reduceBack funcStr strSeq
933+
Assert.AreEqual("E", reduceStr)
934+
935+
// string Seq
936+
let funcStr2 elem acc = sprintf "%s%s" elem acc
937+
let strSeq2 = seq [ "A" ]
938+
let reduceStr2 = Seq.reduceBack funcStr2 strSeq2
939+
Assert.AreEqual("A", reduceStr2)
940+
941+
// Empty Seq
942+
CheckThrowsArgumentException (fun () -> Seq.reduceBack funcInt Seq.empty |> ignore)
943+
944+
// null Seq
945+
let nullSeq:seq<'a> = null
946+
CheckThrowsArgumentNullException (fun () -> Seq.reduceBack funcInt nullSeq |> ignore)
947+
948+
()
949+
922950
[<Test>]
923951
member this.Scan() =
924952
// integer Seq

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

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -459,12 +459,14 @@ Microsoft.FSharp.Collections.SeqModule: T MaxBy[T,TResult](Microsoft.FSharp.Core
459459
Microsoft.FSharp.Collections.SeqModule: T Max[T](System.Collections.Generic.IEnumerable`1[T])
460460
Microsoft.FSharp.Collections.SeqModule: T MinBy[T,TResult](Microsoft.FSharp.Core.FSharpFunc`2[T,TResult], System.Collections.Generic.IEnumerable`1[T])
461461
Microsoft.FSharp.Collections.SeqModule: T Min[T](System.Collections.Generic.IEnumerable`1[T])
462+
Microsoft.FSharp.Collections.SeqModule: T ReduceBack[T](Microsoft.FSharp.Core.FSharpFunc`2[T,Microsoft.FSharp.Core.FSharpFunc`2[T,T]], System.Collections.Generic.IEnumerable`1[T])
462463
Microsoft.FSharp.Collections.SeqModule: T Reduce[T](Microsoft.FSharp.Core.FSharpFunc`2[T,Microsoft.FSharp.Core.FSharpFunc`2[T,T]], System.Collections.Generic.IEnumerable`1[T])
463464
Microsoft.FSharp.Collections.SeqModule: T Sum[T](System.Collections.Generic.IEnumerable`1[T])
464465
Microsoft.FSharp.Collections.SeqModule: TResult AverageBy[T,TResult](Microsoft.FSharp.Core.FSharpFunc`2[T,TResult], System.Collections.Generic.IEnumerable`1[T])
465466
Microsoft.FSharp.Collections.SeqModule: TResult Pick[T,TResult](Microsoft.FSharp.Core.FSharpFunc`2[T,Microsoft.FSharp.Core.FSharpOption`1[TResult]], System.Collections.Generic.IEnumerable`1[T])
466467
Microsoft.FSharp.Collections.SeqModule: TResult SumBy[T,TResult](Microsoft.FSharp.Core.FSharpFunc`2[T,TResult], System.Collections.Generic.IEnumerable`1[T])
467468
Microsoft.FSharp.Collections.SeqModule: TState Fold2[T1,T2,TState](Microsoft.FSharp.Core.FSharpFunc`2[TState,Microsoft.FSharp.Core.FSharpFunc`2[T1,Microsoft.FSharp.Core.FSharpFunc`2[T2,TState]]], TState, System.Collections.Generic.IEnumerable`1[T1], System.Collections.Generic.IEnumerable`1[T2])
469+
Microsoft.FSharp.Collections.SeqModule: TState FoldBack[T,TState](Microsoft.FSharp.Core.FSharpFunc`2[T,Microsoft.FSharp.Core.FSharpFunc`2[TState,TState]], System.Collections.Generic.IEnumerable`1[T], TState)
468470
Microsoft.FSharp.Collections.SeqModule: TState Fold[T,TState](Microsoft.FSharp.Core.FSharpFunc`2[TState,Microsoft.FSharp.Core.FSharpFunc`2[T,TState]], TState, System.Collections.Generic.IEnumerable`1[T])
469471
Microsoft.FSharp.Collections.SeqModule: T[] ToArray[T](System.Collections.Generic.IEnumerable`1[T])
470472
Microsoft.FSharp.Collections.SeqModule: Void Iterate2[T1,T2](Microsoft.FSharp.Core.FSharpFunc`2[T1,Microsoft.FSharp.Core.FSharpFunc`2[T2,Microsoft.FSharp.Core.Unit]], System.Collections.Generic.IEnumerable`1[T1], System.Collections.Generic.IEnumerable`1[T2])

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

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -453,12 +453,14 @@ Microsoft.FSharp.Collections.SeqModule: T MaxBy[T,TResult](Microsoft.FSharp.Core
453453
Microsoft.FSharp.Collections.SeqModule: T Max[T](System.Collections.Generic.IEnumerable`1[T])
454454
Microsoft.FSharp.Collections.SeqModule: T MinBy[T,TResult](Microsoft.FSharp.Core.FSharpFunc`2[T,TResult], System.Collections.Generic.IEnumerable`1[T])
455455
Microsoft.FSharp.Collections.SeqModule: T Min[T](System.Collections.Generic.IEnumerable`1[T])
456+
Microsoft.FSharp.Collections.SeqModule: T ReduceBack[T](Microsoft.FSharp.Core.FSharpFunc`2[T,Microsoft.FSharp.Core.FSharpFunc`2[T,T]], System.Collections.Generic.IEnumerable`1[T])
456457
Microsoft.FSharp.Collections.SeqModule: T Reduce[T](Microsoft.FSharp.Core.FSharpFunc`2[T,Microsoft.FSharp.Core.FSharpFunc`2[T,T]], System.Collections.Generic.IEnumerable`1[T])
457458
Microsoft.FSharp.Collections.SeqModule: T Sum[T](System.Collections.Generic.IEnumerable`1[T])
458459
Microsoft.FSharp.Collections.SeqModule: TResult AverageBy[T,TResult](Microsoft.FSharp.Core.FSharpFunc`2[T,TResult], System.Collections.Generic.IEnumerable`1[T])
459460
Microsoft.FSharp.Collections.SeqModule: TResult Pick[T,TResult](Microsoft.FSharp.Core.FSharpFunc`2[T,Microsoft.FSharp.Core.FSharpOption`1[TResult]], System.Collections.Generic.IEnumerable`1[T])
460461
Microsoft.FSharp.Collections.SeqModule: TResult SumBy[T,TResult](Microsoft.FSharp.Core.FSharpFunc`2[T,TResult], System.Collections.Generic.IEnumerable`1[T])
461462
Microsoft.FSharp.Collections.SeqModule: TState Fold2[T1,T2,TState](Microsoft.FSharp.Core.FSharpFunc`2[TState,Microsoft.FSharp.Core.FSharpFunc`2[T1,Microsoft.FSharp.Core.FSharpFunc`2[T2,TState]]], TState, System.Collections.Generic.IEnumerable`1[T1], System.Collections.Generic.IEnumerable`1[T2])
463+
Microsoft.FSharp.Collections.SeqModule: TState FoldBack[T,TState](Microsoft.FSharp.Core.FSharpFunc`2[T,Microsoft.FSharp.Core.FSharpFunc`2[TState,TState]], System.Collections.Generic.IEnumerable`1[T], TState)
462464
Microsoft.FSharp.Collections.SeqModule: TState Fold[T,TState](Microsoft.FSharp.Core.FSharpFunc`2[TState,Microsoft.FSharp.Core.FSharpFunc`2[T,TState]], TState, System.Collections.Generic.IEnumerable`1[T])
463465
Microsoft.FSharp.Collections.SeqModule: T[] ToArray[T](System.Collections.Generic.IEnumerable`1[T])
464466
Microsoft.FSharp.Collections.SeqModule: Void Iterate2[T1,T2](Microsoft.FSharp.Core.FSharpFunc`2[T1,Microsoft.FSharp.Core.FSharpFunc`2[T2,Microsoft.FSharp.Core.Unit]], System.Collections.Generic.IEnumerable`1[T1], System.Collections.Generic.IEnumerable`1[T2])

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

Lines changed: 8 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -291,13 +291,14 @@ namespace Microsoft.FSharp.Collections
291291
[<CompiledName("Fold")>]
292292
val fold<'T,'State> : folder:('State -> 'T -> 'State) -> state:'State -> array: 'T[] -> 'State
293293

294-
/// <summary>Applies a function to each element of the array, threading an accumulator argument
294+
/// <summary>Applies a function to each element of the array, starting from the end, threading an accumulator argument
295295
/// through the computation. If the input function is <c>f</c> and the elements are <c>i0...iN</c> then computes
296296
/// <c>f i0 (...(f iN s))</c></summary>
297297
/// <param name="folder">The function to update the state given the input elements.</param>
298298
/// <param name="array">The input array.</param>
299299
/// <param name="state">The initial state.</param>
300-
/// <returns>The final state.</returns>
300+
/// <returns>The state object after the folding function is applied to each element of the array.</returns>
301+
/// <exception cref="System.ArgumentNullException">Thrown when the input array is null.</exception>
301302
[<CompiledName("FoldBack")>]
302303
val foldBack<'T,'State> : folder:('T -> 'State -> 'State) -> array:'T[] -> state:'State -> 'State
303304

@@ -569,12 +570,13 @@ namespace Microsoft.FSharp.Collections
569570
[<CompiledName("Reduce")>]
570571
val reduce: reduction:('T -> 'T -> 'T) -> array:'T[] -> 'T
571572

572-
/// <summary>Applies a function to each element of the array, threading an accumulator argument
573+
/// <summary>Applies a function to each element of the array, starting from the end, threading an accumulator argument
573574
/// through the computation. If the input function is <c>f</c> and the elements are <c>i0...iN</c>
574-
/// then computes <c>f i0 (...(f iN-1 iN))</c>.
575-
/// Raises ArgumentException if the array has size zero.</summary>
576-
/// <param name="reduction">The function to reduce a pair of elements to a single element.</param>
575+
/// then computes <c>f i0 (...(f iN-1 iN))</c>.</summary>
576+
/// <param name="reduction">A function that takes in the next-to-last element of the list and the
577+
/// current accumulated result to produce the next accumulated result.</param>
577578
/// <param name="array">The input array.</param>
579+
/// <exception cref="System.ArgumentNullException">Thrown when the input array is null.</exception>
578580
/// <exception cref="System.ArgumentException">Thrown when the input array is empty.</exception>
579581
/// <returns>The final result of the reductions.</returns>
580582
[<CompiledName("ReduceBack")>]

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

Lines changed: 6 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -215,13 +215,13 @@ namespace Microsoft.FSharp.Collections
215215
[<CompiledName("Fold2")>]
216216
val fold2<'T1,'T2,'State> : folder:('State -> 'T1 -> 'T2 -> 'State) -> state:'State -> list1:'T1 list -> list2:'T2 list -> 'State
217217

218-
/// <summary>Applies a function to each element of the collection, threading an accumulator argument
218+
/// <summary>Applies a function to each element of the collection, starting from the end, threading an accumulator argument
219219
/// through the computation. If the input function is <c>f</c> and the elements are <c>i0...iN</c> then
220220
/// computes <c>f i0 (...(f iN s))</c>.</summary>
221221
/// <param name="folder">The function to update the state given the input elements.</param>
222222
/// <param name="list">The input list.</param>
223223
/// <param name="state">The initial state.</param>
224-
/// <returns>The final state value.</returns>
224+
/// <returns>The state object after the folding function is applied to each element of the list.</returns>
225225
[<CompiledName("FoldBack")>]
226226
val foldBack<'T,'State> : folder:('T -> 'State -> 'State) -> list:'T list -> state:'State -> 'State
227227

@@ -489,15 +489,14 @@ namespace Microsoft.FSharp.Collections
489489
[<CompiledName("Reduce")>]
490490
val reduce: reduction:('T -> 'T -> 'T) -> list:'T list -> 'T
491491

492-
/// <summary>Applies a function to each element of the collection, threading an accumulator argument
492+
/// <summary>Applies a function to each element of the collection, starting from the end, threading an accumulator argument
493493
/// through the computation. If the input function is <c>f</c> and the elements are <c>i0...iN</c> then computes
494494
/// <c>f i0 (...(f iN-1 iN))</c>.</summary>
495-
///
496-
/// <remarks>Raises <c>System.ArgumentException</c> if <c>list</c> is empty</remarks>
497-
/// <param name="reduction">The function to reduce two list elements to a single element.</param>
495+
/// <param name="reduction">A function that takes in the next-to-last element of the list and the
496+
/// current accumulated result to produce the next accumulated result.</param>
498497
/// <param name="list">The input list.</param>
499498
/// <exception cref="System.ArgumentException">Thrown when the list is empty.</exception>
500-
/// <returns>The final reduced value.</returns>
499+
/// <returns>The final result of the reductions.</returns>
501500
[<CompiledName("ReduceBack")>]
502501
val reduceBack: reduction:('T -> 'T -> 'T) -> list:'T list -> 'T
503502

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

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1231,6 +1231,29 @@ namespace Microsoft.FSharp.Collections
12311231
res.Add(e.Current)
12321232
res.ToArray()
12331233

1234+
let foldArraySubRight (f:OptimizedClosures.FSharpFunc<'T,_,_>) (arr: 'T[]) start fin acc =
1235+
let mutable state = acc
1236+
for i = fin downto start do
1237+
state <- f.Invoke(arr.[i], state)
1238+
state
1239+
1240+
[<CompiledName("FoldBack")>]
1241+
let foldBack<'T,'State> f (source : seq<'T>) (x:'State) =
1242+
checkNonNull "source" source
1243+
let f = OptimizedClosures.FSharpFunc<_,_,_>.Adapt(f)
1244+
let arr = toArray source
1245+
let len = arr.Length
1246+
foldArraySubRight f arr 0 (len - 1) x
1247+
1248+
[<CompiledName("ReduceBack")>]
1249+
let reduceBack f (source : seq<'T>) =
1250+
checkNonNull "source" source
1251+
let arr = toArray source
1252+
match arr.Length with
1253+
| 0 -> invalidArg "source" InputSequenceEmptyString
1254+
| len ->
1255+
let f = OptimizedClosures.FSharpFunc<_,_,_>.Adapt(f)
1256+
foldArraySubRight f arr 0 (len - 2) arr.[len - 1]
12341257

12351258
[<CompiledName("Singleton")>]
12361259
let singleton x = mkSeq (fun () -> IEnumerator.Singleton x)

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

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -364,6 +364,17 @@ namespace Microsoft.FSharp.Collections
364364
[<CompiledName("Fold2")>]
365365
val fold2<'T1,'T2,'State> : folder:('State -> 'T1 -> 'T2 -> 'State) -> state:'State -> source1:seq<'T1> -> source2:seq<'T2> -> 'State
366366

367+
/// <summary>Applies a function to each element of the collection, starting from the end, threading an accumulator argument
368+
/// through the computation. If the input function is <c>f</c> and the elements are <c>i0...iN</c>
369+
/// then computes <c>f i0 (... (f iN s)...)</c></summary>
370+
/// <param name="folder">The function to update the state given the input elements.</param>
371+
/// <param name="source">The input sequence.</param>
372+
/// <param name="state">The initial state.</param>
373+
/// <returns>The state object after the folding function is applied to each element of the sequence.</returns>
374+
/// <exception cref="System.ArgumentNullException">Thrown when the input sequence is null.</exception>
375+
[<CompiledName("FoldBack")>]
376+
val foldBack<'T,'State> : folder:('T -> 'State -> 'State) -> source:seq<'T> -> state:'State -> 'State
377+
367378
/// <summary>Tests if all elements of the sequence satisfy the given predicate.</summary>
368379
///
369380
/// <remarks>The predicate is applied to the elements of the input sequence. If any application
@@ -795,6 +806,18 @@ namespace Microsoft.FSharp.Collections
795806
[<CompiledName("Replicate")>]
796807
val replicate: count:int -> initial:'T -> seq<'T>
797808

809+
/// <summary>Applies a function to each element of the sequence, starting from the end, threading an accumulator argument
810+
/// through the computation. If the input function is <c>f</c> and the elements are <c>i0...iN</c>
811+
/// then computes <c>f i0 (...(f iN-1 iN))</c>.</summary>
812+
/// <param name="reduction">A function that takes in the next-to-last element of the sequence and the
813+
/// current accumulated result to produce the next accumulated result.</param>
814+
/// <param name="source">The input sequence.</param>
815+
/// <returns>The final result of the reductions.</returns>
816+
/// <exception cref="System.ArgumentNullException">Thrown when the input sequence is null.</exception>
817+
/// <exception cref="System.ArgumentException">Thrown when the input sequence is empty.</exception>
818+
[<CompiledName("ReduceBack")>]
819+
val reduceBack: reduction:('T -> 'T -> 'T) -> source:seq<'T> -> 'T
820+
798821
/// <summary>Like fold, but computes on-demand and returns the sequence of intermediary and final results.</summary>
799822
///
800823
/// <param name="folder">A function that updates the state with each element from the sequence.</param>

0 commit comments

Comments
 (0)