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

Commit366777f

Browse files
PatrickMcDonaldlatkin
authored andcommitted
Implement Seq.foldBack, Seq.reduceBack
commit b80eba279fa2f948674b466211c356868af83275Author: latkin <latkin@microsoft.com>Date: Tue Oct 21 13:26:29 2014 -0700 Add a couple test cases for length-1 seqscommit e8080990fb9571bdbd0f93ce9afa6419da42772cAuthor: latkin <latkin@microsoft.com>Date: Tue Oct 21 13:19:59 2014 -0700 Normalizing doc comments across array, list, seqcommit 5a51ef31350aec0b679bd4981827919b8c285699Merge: 1b31d64 58b2330Author: latkin <latkin@microsoft.com>Date: Tue Oct 21 12:30:18 2014 -0700 Merge branch 'foldBack' ofhttps://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.fsicommit 58b233045a597a5078d8695fdf8d8ce4d771d690Author: Patrick McDonald <paddymcdonald@gmail.com>Date: Sat Aug 16 23:32:32 2014 +0100 Implement Seq.foldBack and Seq.reduceBack
1 parent627c016 commit366777f

File tree

8 files changed

+129
-14
lines changed

8 files changed

+129
-14
lines changed

‎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 funcInt0(seq[1]) nullSeq|> ignore)
703703
()
704704

705+
[<Test>]
706+
memberthis.FoldBack()=
707+
// int Seq
708+
letfuncInt x y= x-y
709+
letIntSeq=seq{1..4}
710+
letfoldInt= Seq.foldBack funcInt IntSeq6
711+
Assert.AreEqual((1-(2-(3-(4-6)))), foldInt)
712+
713+
// string Seq
714+
letfuncStr(x:string)(y:string)= y.Remove(0,x.Length)
715+
letstrSeq= seq["A";"B";"C";"D"]
716+
letfoldStr= Seq.foldBack funcStr strSeq"ABCDE"
717+
Assert.AreEqual("E", foldStr)
718+
719+
// single element
720+
letfuncStr2 elem acc= sprintf"%s%s" elem acc
721+
letstrSeq2= seq["A"]
722+
letfoldStr2= Seq.foldBack funcStr2 strSeq2"X"
723+
Assert.AreEqual("AX", foldStr2)
724+
725+
// Empty Seq
726+
letemptySeq= Seq.empty
727+
letfoldEmpty= Seq.foldBack funcInt emptySeq1
728+
Assert.AreEqual(1, foldEmpty)
729+
730+
// null Seq
731+
letnullSeq:seq<'a>=null
732+
CheckThrowsArgumentNullException(fun()-> Seq.foldBack funcInt nullSeq1|> ignore)
733+
734+
// Validate that foldBack with the cons operator and the empty list returns a copy of the sequence
735+
letcons x y= x:: y
736+
letidentityFoldr= Seq.foldBack cons IntSeq[]
737+
Assert.AreEqual([1;2;3;4], identityFoldr)
738+
739+
()
740+
705741
[<Test>]
706742
memberthis.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+
memberthis.ReduceBack()=
923+
// int Seq
924+
letfuncInt x y= x- y
925+
letIntSeq=seq{1..4}
926+
letreduceInt= Seq.reduceBack funcInt IntSeq
927+
Assert.AreEqual((1-(2-(3-4))), reduceInt)
928+
929+
// string Seq
930+
letfuncStr(x:string)(y:string)= y.Remove(0,x.Length)
931+
letstrSeq= seq["A";"B";"C";"D";"ABCDE"]
932+
letreduceStr= Seq.reduceBack funcStr strSeq
933+
Assert.AreEqual("E", reduceStr)
934+
935+
// string Seq
936+
letfuncStr2 elem acc= sprintf"%s%s" elem acc
937+
letstrSeq2= seq["A"]
938+
letreduceStr2= 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+
letnullSeq:seq<'a>=null
946+
CheckThrowsArgumentNullException(fun()-> Seq.reduceBack funcInt nullSeq|> ignore)
947+
948+
()
949+
922950
[<Test>]
923951
memberthis.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 ifthearray has size zero.</summary>
576-
///<param name="reduction">The function toreduce 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 inthenext-to-last element of the list and the
577+
///current accumulated result toproduce 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>Thefinalstatevalue.</returns>
224+
///<returns>The stateobject 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 finalreduced value.</returns>
499+
///<returns>The finalresult 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+
letfoldArraySubRight(f:OptimizedClosures.FSharpFunc<'T,_,_>)(arr:'T[])start fin acc=
1235+
let mutablestate= acc
1236+
for i= findownto startdo
1237+
state<- f.Invoke(arr.[i], state)
1238+
state
1239+
1240+
[<CompiledName("FoldBack")>]
1241+
letfoldBack<'T,'State>f(source:seq<'T>)(x:'State)=
1242+
checkNonNull"source" source
1243+
letf= OptimizedClosures.FSharpFunc<_,_,_>.Adapt(f)
1244+
letarr= toArray source
1245+
letlen= arr.Length
1246+
foldArraySubRight f arr0(len-1) x
1247+
1248+
[<CompiledName("ReduceBack")>]
1249+
letreduceBack f(source:seq<'T>)=
1250+
checkNonNull"source" source
1251+
letarr= toArray source
1252+
match arr.Lengthwith
1253+
|0-> invalidArg"source" InputSequenceEmptyString
1254+
| len->
1255+
letf= OptimizedClosures.FSharpFunc<_,_,_>.Adapt(f)
1256+
foldArraySubRight f arr0(len-2) arr.[len-1]
12341257

12351258
[<CompiledName("Singleton")>]
12361259
letsingleton 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)
[8]ページ先頭
©2009-2025 Movatter.jp