- New types hierarchy to manage functions.
- New Pipeline-like API for `Iterator` based on functional type.
Signed-off-by: Louis-Vincent Boudreault <lv.boudreault95@gmail.com>
--- /dev/null
+# Nit functional types and Iterator API
+
+This lib provides a common interfaces to represent and call any type of routine.
+This is usefull if you want to build a functional API, where user can pass
+functions. Right now, there's no support for anonymous function or function pointer.
+However, one can build classes that inherit from a functional type to simulate
+a function. Here's an example implementing the famous __map__ function:
+
+~~~
+class MapIntToString
+ super Fun1[Int,String]
+ redef fun call(x) do return x.to_s
+end
+
+redef class Array[E]
+ fun map(mapper: Fun1[E, Object]): Array[Object]
+ do
+ var res = new Array[Object]
+ for ele in self do res.add(mapper.call(ele))
+ return res
+ end
+end
+
+var xs = [1,2,3,4]
+var f = new MapIntToString
+assert xs.map(f) == ["1", "2", "3", "4"]
+~~~
+
+Currently, this style of programming seems tedious, but future update of the langage
+will support function pointer and anonymous function.
+
+Functional API makes it easier to build asynchronous or multithreaded code,
+because representing a pending or future computation using a function requires
+much less code:
+
+~~~nitish
+fun long\_calculation
+do
+ ...
+end
+
+# function pointer
+var thread = new Thread(&long\_calculation)
+thread.start
+thread.wait
+~~~
+
+Finally, this lib provides an entire functional API over the `Iterator` class
+similar to the old `Pipeline` lib.
+
+## Functional Types
+
+There are two fundamental types: `FunX[0..X, RES]` and `ProcX[0..X]`, both inherits
+`Routine`. The `X` represents the arity of the routine, eg :
+
+~~~
+import functional
+
+class A
+
+ # to_s isa `Fun0[String]`.
+ redef fun to_s do return "greeting from A"
+end
+
+# f isa `Fun2[Int,Int,Int]`
+fun f(x: Int, y: Int): Int do return x + y
+
+# g isa `Proc2[Int,Int]`
+fun g(x: Int, y: Int) do print "{x + y}"
+~~~
+
+For a `FunX` type the arity doesn't count the return type.
+
+**Note**: The arity doesn't count the receiver of the current class where the
+method belongs.
+
+## Iterator API
+
+The new `Iterator` API provides all the classical functional style transformation:
+map, for\_each, fold, fold1, flatmap, enumerate, any and all.
+
+Most methods return a new `Iterator`, this allow us to chain them:
+
+~~~nitish
+import functional
+
+fun addone(x: Int): Int do return x + 1
+fun square(x: Int): Int do return x * x
+fun add(x:Int, y: Int): Int do return x + y
+
+var xs = [1,2,3,4,5,6,7,8,9,10]
+
+assert xs.iterator.map(&square).map(&addone).fold(0, &add) == 395
+~~~
+
+Some functions collapse the iterator into one value : `all`, `any`, `fold`,
+`fold1`, `for_each` (void-like).
+
+**Note**: Most of the new methods tries to be lazy. However, `Iterator::order_by`
+consume the entire iterator and `Iterator::filter` might consume the entire iterator.
+
+## Usage
+
+To use the new API you must include in your file `import functional`.
+
+## Notes
+
+- The module `functional::functional_gen` is only used to generate `functional::functional_types`.
--- /dev/null
+# This file is part of NIT ( http://www.nitlanguage.org ).
+#
+# Copyright 2019 Louis-Vincent Boudreault <lv.boudreault95@gmail.com>
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+# Functional types and functional API for `Iterator`
+module functional
+
+import iter_extras
--- /dev/null
+# This file is part of NIT ( http://www.nitlanguage.org ).
+#
+# Copyright 2019 Louis-Vincent Boudreault <lv.boudreault95@gmail.com>
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+# This module is only used to generate `functional_types.nit`
+module functional_gen
+
+# Generates of an array of formal type as strings.
+# The size of the array equals the arity of the class.
+fun gen_generics(nargs: Int): Array[String]
+do
+ var args = new Array[String]
+ for i in [0..nargs[ do
+ args.push("A" + i.to_s)
+ end
+ return args
+end
+
+class RoutineTemplate
+ var classname: String
+ var nb_generics: Int
+ var supers: Array[String]
+ var has_return: Bool
+ var annotation = "is abstract"
+
+ redef fun to_s
+ do
+ var generics = gen_generics(nb_generics)
+ var params = new Array[String]
+ for g in generics do
+ params.push(g.to_lower + ": " + g)
+ end
+ var signature = ""
+ if params.length > 0 then signature = "({params.join(",")})"
+ if has_return then
+ signature += ": RESULT"
+ generics.push("RESULT")
+ end
+ var classparam = ""
+ if generics.length > 0 then
+ classparam = "[{generics.join(",")}]"
+ end
+ var superdecls = new Array[String]
+ for s in supers do superdecls.add("\tsuper {s}")
+ var classdef = new Array[String]
+ classdef.add("class {classname}{classparam}")
+ classdef.add("{superdecls.join("\n")}")
+ classdef.add("\tfun call{signature} {annotation}")
+ classdef.add("end")
+ return classdef.join("\n")
+ end
+end
+
+# Writes all functional types
+fun generate_functypes(n: Int, writer: Writer)
+do
+ writer.write("""
+# This file is part of NIT ( http://www.nitlanguage.org ).
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+# This module provides functional type to represents various function forms.
+# Function types can hold up to 20 arguments. The type `Fun` is for function
+# (input and output) and `Proc` is for procedure (input but no output).
+# This file is automatically generated, do not edit it manually.
+module functional_types
+
+interface Routine
+end
+interface Fun
+ super Routine
+end
+interface Proc
+ super Routine
+end
+""")
+ var templates = new Array[String]
+ for i in [0..n[ do
+ var t1 = new RoutineTemplate("Fun{i}", i, ["Fun"], true)
+ var t2 = new RoutineTemplate("Proc{i}", i, ["Proc"], false)
+ templates.push(t1.to_s)
+ templates.push(t2.to_s)
+ end
+ writer.write(templates.join("\n"))
+end
+
+var fw = new FileWriter.open("functional_types.nit")
+generate_functypes(20, fw)
--- /dev/null
+# This file is part of NIT ( http://www.nitlanguage.org ).
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+# This module provides functional type to represents various function forms.
+# Function types can hold up to 20 arguments. The type `Fun` is for function
+# (input and output) and `Proc` is for procedure (input but no output).
+# This file is automatically generated, do not edit it manually.
+module functional_types
+
+interface Routine
+end
+interface Fun
+ super Routine
+end
+interface Proc
+ super Routine
+end
+class Fun0[RESULT]
+ super Fun
+ fun call: RESULT is abstract
+end
+class Proc0
+ super Proc
+ fun call is abstract
+end
+class Fun1[A0,RESULT]
+ super Fun
+ fun call(a0: A0): RESULT is abstract
+end
+class Proc1[A0]
+ super Proc
+ fun call(a0: A0) is abstract
+end
+class Fun2[A0,A1,RESULT]
+ super Fun
+ fun call(a0: A0,a1: A1): RESULT is abstract
+end
+class Proc2[A0,A1]
+ super Proc
+ fun call(a0: A0,a1: A1) is abstract
+end
+class Fun3[A0,A1,A2,RESULT]
+ super Fun
+ fun call(a0: A0,a1: A1,a2: A2): RESULT is abstract
+end
+class Proc3[A0,A1,A2]
+ super Proc
+ fun call(a0: A0,a1: A1,a2: A2) is abstract
+end
+class Fun4[A0,A1,A2,A3,RESULT]
+ super Fun
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3): RESULT is abstract
+end
+class Proc4[A0,A1,A2,A3]
+ super Proc
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3) is abstract
+end
+class Fun5[A0,A1,A2,A3,A4,RESULT]
+ super Fun
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4): RESULT is abstract
+end
+class Proc5[A0,A1,A2,A3,A4]
+ super Proc
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4) is abstract
+end
+class Fun6[A0,A1,A2,A3,A4,A5,RESULT]
+ super Fun
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5): RESULT is abstract
+end
+class Proc6[A0,A1,A2,A3,A4,A5]
+ super Proc
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5) is abstract
+end
+class Fun7[A0,A1,A2,A3,A4,A5,A6,RESULT]
+ super Fun
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6): RESULT is abstract
+end
+class Proc7[A0,A1,A2,A3,A4,A5,A6]
+ super Proc
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6) is abstract
+end
+class Fun8[A0,A1,A2,A3,A4,A5,A6,A7,RESULT]
+ super Fun
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6,a7: A7): RESULT is abstract
+end
+class Proc8[A0,A1,A2,A3,A4,A5,A6,A7]
+ super Proc
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6,a7: A7) is abstract
+end
+class Fun9[A0,A1,A2,A3,A4,A5,A6,A7,A8,RESULT]
+ super Fun
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6,a7: A7,a8: A8): RESULT is abstract
+end
+class Proc9[A0,A1,A2,A3,A4,A5,A6,A7,A8]
+ super Proc
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6,a7: A7,a8: A8) is abstract
+end
+class Fun10[A0,A1,A2,A3,A4,A5,A6,A7,A8,A9,RESULT]
+ super Fun
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6,a7: A7,a8: A8,a9: A9): RESULT is abstract
+end
+class Proc10[A0,A1,A2,A3,A4,A5,A6,A7,A8,A9]
+ super Proc
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6,a7: A7,a8: A8,a9: A9) is abstract
+end
+class Fun11[A0,A1,A2,A3,A4,A5,A6,A7,A8,A9,A10,RESULT]
+ super Fun
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6,a7: A7,a8: A8,a9: A9,a10: A10): RESULT is abstract
+end
+class Proc11[A0,A1,A2,A3,A4,A5,A6,A7,A8,A9,A10]
+ super Proc
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6,a7: A7,a8: A8,a9: A9,a10: A10) is abstract
+end
+class Fun12[A0,A1,A2,A3,A4,A5,A6,A7,A8,A9,A10,A11,RESULT]
+ super Fun
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6,a7: A7,a8: A8,a9: A9,a10: A10,a11: A11): RESULT is abstract
+end
+class Proc12[A0,A1,A2,A3,A4,A5,A6,A7,A8,A9,A10,A11]
+ super Proc
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6,a7: A7,a8: A8,a9: A9,a10: A10,a11: A11) is abstract
+end
+class Fun13[A0,A1,A2,A3,A4,A5,A6,A7,A8,A9,A10,A11,A12,RESULT]
+ super Fun
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6,a7: A7,a8: A8,a9: A9,a10: A10,a11: A11,a12: A12): RESULT is abstract
+end
+class Proc13[A0,A1,A2,A3,A4,A5,A6,A7,A8,A9,A10,A11,A12]
+ super Proc
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6,a7: A7,a8: A8,a9: A9,a10: A10,a11: A11,a12: A12) is abstract
+end
+class Fun14[A0,A1,A2,A3,A4,A5,A6,A7,A8,A9,A10,A11,A12,A13,RESULT]
+ super Fun
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6,a7: A7,a8: A8,a9: A9,a10: A10,a11: A11,a12: A12,a13: A13): RESULT is abstract
+end
+class Proc14[A0,A1,A2,A3,A4,A5,A6,A7,A8,A9,A10,A11,A12,A13]
+ super Proc
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6,a7: A7,a8: A8,a9: A9,a10: A10,a11: A11,a12: A12,a13: A13) is abstract
+end
+class Fun15[A0,A1,A2,A3,A4,A5,A6,A7,A8,A9,A10,A11,A12,A13,A14,RESULT]
+ super Fun
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6,a7: A7,a8: A8,a9: A9,a10: A10,a11: A11,a12: A12,a13: A13,a14: A14): RESULT is abstract
+end
+class Proc15[A0,A1,A2,A3,A4,A5,A6,A7,A8,A9,A10,A11,A12,A13,A14]
+ super Proc
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6,a7: A7,a8: A8,a9: A9,a10: A10,a11: A11,a12: A12,a13: A13,a14: A14) is abstract
+end
+class Fun16[A0,A1,A2,A3,A4,A5,A6,A7,A8,A9,A10,A11,A12,A13,A14,A15,RESULT]
+ super Fun
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6,a7: A7,a8: A8,a9: A9,a10: A10,a11: A11,a12: A12,a13: A13,a14: A14,a15: A15): RESULT is abstract
+end
+class Proc16[A0,A1,A2,A3,A4,A5,A6,A7,A8,A9,A10,A11,A12,A13,A14,A15]
+ super Proc
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6,a7: A7,a8: A8,a9: A9,a10: A10,a11: A11,a12: A12,a13: A13,a14: A14,a15: A15) is abstract
+end
+class Fun17[A0,A1,A2,A3,A4,A5,A6,A7,A8,A9,A10,A11,A12,A13,A14,A15,A16,RESULT]
+ super Fun
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6,a7: A7,a8: A8,a9: A9,a10: A10,a11: A11,a12: A12,a13: A13,a14: A14,a15: A15,a16: A16): RESULT is abstract
+end
+class Proc17[A0,A1,A2,A3,A4,A5,A6,A7,A8,A9,A10,A11,A12,A13,A14,A15,A16]
+ super Proc
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6,a7: A7,a8: A8,a9: A9,a10: A10,a11: A11,a12: A12,a13: A13,a14: A14,a15: A15,a16: A16) is abstract
+end
+class Fun18[A0,A1,A2,A3,A4,A5,A6,A7,A8,A9,A10,A11,A12,A13,A14,A15,A16,A17,RESULT]
+ super Fun
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6,a7: A7,a8: A8,a9: A9,a10: A10,a11: A11,a12: A12,a13: A13,a14: A14,a15: A15,a16: A16,a17: A17): RESULT is abstract
+end
+class Proc18[A0,A1,A2,A3,A4,A5,A6,A7,A8,A9,A10,A11,A12,A13,A14,A15,A16,A17]
+ super Proc
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6,a7: A7,a8: A8,a9: A9,a10: A10,a11: A11,a12: A12,a13: A13,a14: A14,a15: A15,a16: A16,a17: A17) is abstract
+end
+class Fun19[A0,A1,A2,A3,A4,A5,A6,A7,A8,A9,A10,A11,A12,A13,A14,A15,A16,A17,A18,RESULT]
+ super Fun
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6,a7: A7,a8: A8,a9: A9,a10: A10,a11: A11,a12: A12,a13: A13,a14: A14,a15: A15,a16: A16,a17: A17,a18: A18): RESULT is abstract
+end
+class Proc19[A0,A1,A2,A3,A4,A5,A6,A7,A8,A9,A10,A11,A12,A13,A14,A15,A16,A17,A18]
+ super Proc
+ fun call(a0: A0,a1: A1,a2: A2,a3: A3,a4: A4,a5: A5,a6: A6,a7: A7,a8: A8,a9: A9,a10: A10,a11: A11,a12: A12,a13: A13,a14: A14,a15: A15,a16: A16,a17: A17,a18: A18) is abstract
+end
\ No newline at end of file
--- /dev/null
+# This file is part of NIT ( http://www.nitlanguage.org ).
+#
+# Copyright 2019 Louis-Vincent Boudreault <lv.boudreault95@gmail.com>
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+# This modules provides a new functional interface for `Iterator`.
+module iter_extras
+
+import functional_types
+import cartesian
+
+redef class Array
+
+ # Sorts an array with a function.
+ #
+ # ~~~~nitish
+ # class Person
+ # var name: String
+ # end
+ #
+ # def get_name(p: Person) do return p.name
+ #
+ # var ps = [new Person("Turing"), new Person("Curry"), new Person("Alfredo")]
+ # ps.sort_with(&get_name)
+ # assert ps[0].name == "Alfredo"
+ # assert ps[1].name == "Curry"
+ # assert ps[2].name == "Turing"
+ # ~~~~
+ fun sort_with(f: Fun1[E, Comparable])
+ do
+ var cmp = new ComparatorWith[E](f)
+ if length > 1 then
+ cmp.quick_sort(self, 0, length - 1)
+ end
+ end
+end
+
+redef interface Iterator[E]
+
+ # Applies a function to every elements
+ #
+ # ~~~~nitish
+ # fun add(x: Int): Int do return x + 1
+ #
+ # var f = &add
+ # var xs = [1,2,3,4,5]
+ # var actual = xs.iterator.map(f).to_a
+ # assert actual == [2,3,4,5,6]
+ # ~~~~
+ fun map(f: Fun1[E,Object]): MapIter[E,Object]
+ do
+ return new MapIter[E,Object](self, f)
+ end
+
+ # Iterator that gives the current count and element as a pair
+ fun enumerate: EnumerateIter[E]
+ do
+ return new EnumerateIter[E](self)
+ end
+
+ # Iterator that filters elements by a predicate
+ #
+ # ~~~~nitish
+ # fun lt10(x: Int): Bool do return x < 10
+ #
+ # var pred = <10
+ # var xs = [1..20]
+ # var actual = xs.iterator.filter(pred).to_a
+ # assert actual == [1..9].to_a
+ # ~~~~
+ fun filter(pred: Fun1[E,Bool]): FilterIter[E]
+ do
+ return new FilterIter[E](self,pred)
+ end
+
+ # Checks if at least one element respects a predicate
+ #
+ # ~~~~nitish
+ # fun eq10(x: Int): Bool do return x == 10
+ #
+ # var pred = &eq10
+ # var xs = [1,2,5,7,9,10,44]
+ # assert xs.iterator.any(pred)
+ # var ys = []
+ # assert not ys.iterator.any(pred)
+ # assert not [1,2,44].iterator.any(pred)
+ # ~~~~
+ fun any(pred: Fun1[E,Bool]): Bool
+ do
+ for x in self do
+ if pred.call(x) then
+ return true
+ end
+ end
+ return false
+ end
+
+ # Checks if all elements respect a predicate
+ #
+ # ~~~~nitish
+ # fun lt10(x: Int): Bool do return x < 10
+ #
+ # var pred = <10
+ # var xs = [1..9]
+ # assert xs.iterator.all(pred)
+ # assert [].iterator.all(pred)
+ # assert not [1..10].iterator.all(pred)
+ # ~~~~
+ fun all(pred: Fun1[E,Bool]): Bool
+ do
+ for x in self do
+ if not pred.call(x) then
+ return false
+ end
+ end
+ return true
+ end
+
+ # Folds an iterator from the left
+ #
+ # ~~~~nitish
+ # fun adder(x: Int, y: Int): Int do return x + y
+ #
+ # var xs = [1..10]
+ # assert xs.iterator.fold(0, &adder) == 55
+ # ~~~~
+ fun fold(acc: Object, f: Fun2[Object, E, Object]): Object
+ do
+ for x in self do
+ acc = f.call(acc, x)
+ end
+ return acc
+ end
+
+ # Folds and apply two element at a time
+ #
+ # ~~~~nitish
+ # fun min_int(x: Int, y: Int): Int
+ # do
+ # if x < y then return x
+ # return y
+ # end
+ #
+ # var xs = [100,423,51,1,-19,55,999,-18]
+ # assert xs.iterator.fold1(&min_int) == -19
+ # ~~~~
+ # REQUIRE : length > 1
+ fun fold1(f: Fun2[E,E,E]): E
+ do
+ var a1 = item
+ next
+ var a2 = item
+ next
+ var res = f.call(a1,a2)
+ for x in self do
+ res = f.call(res, x)
+ end
+ return res
+ end
+
+ # Apply a mutation function over all elements
+ #
+ # ~~~~nitish
+ # class Person
+ # var age: Int
+ # def incr_age
+ # do
+ # age += 1
+ # end
+ # end
+ #
+ # var ps = [new Persone(1), new Person(2), new Person(3)]
+ # var ages = ps.iterator.for_each(&Person::incr_age).map(&Person::age).to_a
+ # assert ages == [2,3,4]
+ # ~~~~
+ fun for_each(f: Proc1[E])
+ do
+ for x in self do
+ f.call(x)
+ end
+ end
+
+ # Maps every element to a nested structure then flattens it
+ #
+ # ~~~~nitish
+ # fun chars_fn(s: String): Iterator[Char]
+ # do
+ # return s.chars.iterator
+ # end
+ # var cs = ["aaa","bbb","ccc"]
+ # assert cs.iterator.flat_map(&chars_fn).to_a.join == "aaabbbccc"
+ # ~~~~
+ fun flat_map(f: Fun1[E, Iterator[Object]]): FlatMapIter[E, Object]
+ do
+ return new FlatMapIter[E, Object](self, f)
+ end
+
+ # Generates an `Iterator` whose elements are sorted by the function
+ # passed in argument.
+ #
+ # ~~~~nitish
+ # class Person
+ # var name: String
+ # end
+ #
+ # def get_name(p: Person) do return p.name
+ #
+ # var ps = [new Person("Turing"), new Person("Curry"), new Person("Alfredo")]
+ # var ordered_names = ps.iterator.order_by(&get_name).map(&get_name).to_a
+ # assert ordered_names == ["Alfredo", "Curry", "Turing"]
+ # ~~~~
+ fun order_by(f: Fun1[E, Comparable]): OrderedIter[E]
+ do
+ return new OrderedIter[E](self, f)
+ end
+
+end
+
+# Base class for all iterators using functional types.
+private abstract class FunIter[OLD,NEW]
+ super Iterator[NEW]
+ var my_iter: Iterator[OLD]
+
+ redef fun next
+ do
+ my_iter.next
+ end
+
+ redef fun start
+ do
+ my_iter.start
+ end
+
+ redef fun finish
+ do
+ my_iter.finish
+ end
+
+ redef fun is_ok
+ do
+ return my_iter.is_ok
+ end
+end
+
+# An iterator that maps each item with `f`.
+class MapIter[A,B]
+ super FunIter[A,B]
+ var f: Fun1[A, B]
+
+ redef fun item
+ do
+ return f.call(my_iter.item)
+ end
+
+end
+
+# An iterator that maps each item to a pair containing the item with its
+# current count.
+class EnumerateIter[E]
+ super FunIter[E, Pair[Int,E]]
+
+ redef fun item
+ do
+ return new Pair[Int,E](0, my_iter.item)
+ end
+end
+
+# An tierator that filter its element by a predicate `pred`.
+class FilterIter[E]
+ super FunIter[E,nullable E]
+ var pred: Fun1[E, Bool]
+
+ redef init
+ do
+ if is_ok and not pred.call(my_iter.item) then next
+ end
+
+ redef fun item
+ do
+ assert is_ok
+ return my_iter.item
+ end
+
+ redef fun next
+ do
+ loop
+ my_iter.next
+ if not is_ok then
+ break
+ end
+ var x = my_iter.item
+ if pred.call(x) then
+ break
+ end
+ end
+ end
+end
+
+# An iterator that maps each item to an iterator and yield
+# each item from it.
+class FlatMapIter[A,B]
+ super FunIter[A,B]
+ var f: Fun1[A, Iterator[B]]
+ protected var inner: nullable Iterator[B] = null
+
+ redef init
+ do
+ try_compute_inner
+ end
+
+ redef fun item
+ do
+ return inner.as(not null).item
+ end
+
+ redef fun is_ok
+ do
+ return inner != null
+ end
+
+ redef fun next
+ do
+ inner.next
+ if not inner.is_ok then
+ super
+ try_compute_inner
+ end
+ end
+
+ # Tries to resolve the inner iterator.
+ # Assigns null to `inner` if it fails.
+ protected fun try_compute_inner
+ do
+ inner = null
+ if not my_iter.is_ok then return
+ var res = f.call(my_iter.item)
+ if res.is_ok then inner = res
+ end
+end
+
+# An iterator that yield each item in order
+class OrderedIter[E]
+ super FunIter[E,E]
+ var f: Fun1[E, Comparable]
+
+ private var sorted_iter: Iterator[E] is noinit
+ private var sorted_arr: Array[E] is noinit
+
+ redef init
+ do
+ sorted_arr = my_iter.to_a
+ sorted_arr.sort_with(f)
+ sorted_iter = sorted_arr.iterator
+ end
+
+ redef fun next
+ do
+ sorted_iter.next
+ end
+
+ redef fun item
+ do
+ return sorted_iter.item
+ end
+
+ redef fun is_ok
+ do
+ return sorted_iter.is_ok
+ end
+
+ redef fun finish
+ do
+ sorted_iter.finish
+ end
+
+ redef fun to_a
+ do
+ return sorted_arr
+ end
+end
+
+# Comparator that use a function provided by the user to compare between elements.
+class ComparatorWith[E]
+ super Comparator
+ redef type COMPARED: E
+
+ var f: Fun1[E, Comparable]
+
+ redef fun compare(a,b)
+ do
+ var x = f.call(a)
+ var y = f.call(b)
+ if x < y then return -1
+ if x > y then return 1
+ return 0
+ end
+end
--- /dev/null
+[package]
+name=functional
+tags=functional,types
+maintainer=Louis-Vincent Boudreault <lv.boudreault95@gmail.com>
+license=Apache-2.0
+desc=Functional type hierarchies and Stream-like API
+[upstream]
+browse=https://github.com/nitlang/nit/tree/master/lib/functional/
+git=https://github.com/nitlang/nit.git
+git.directory=lib/functional/
+homepage=http://nitlanguage.org
+issues=https://github.com/nitlang/nit/issues
--- /dev/null
+# This file is part of NIT ( http://www.nitlanguage.org ).
+#
+# Copyright 2019 Louis-Vincent Boudreault <lv.boudreault95@gmail.com>
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+# http://www.apache.org/license/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+module test_iter_extras is test
+
+import iter_extras
+private import test_utils
+
+redef class Ref[E]
+ redef fun ==(other) do
+ if other isa Ref[E] then
+ return self.item == other.item
+ end
+ return false
+ end
+end
+
+# test cases using `iter_extras::Iterator::map`
+class TestMapIter
+ test
+
+ # test case for an empty `Array` of `Int`
+ fun add_one_on_empty_array is test do
+ var xs = new Array[Int]
+ var actual = xs.iterator.map(add_one).to_a
+ assert actual.is_empty
+ end
+
+ # test case for an `Array` containing one `Int`
+ fun add_one_on_singleton_array is test do
+ var xs = [1]
+ var actual = xs.iterator.map(add_one).to_a
+ assert actual[0] == 2
+ end
+
+ # test case for `Range`, adding one to each elements (1 to 10)
+ fun add_one_on_range_1_to_10 is test do
+ var xs = [1..10]
+ var actual = xs.iterator.map(add_one).to_a
+ var expected = [2,3,4,5,6,7,8,9,10,11]
+ assert actual == expected
+ end
+
+ # test multiple application of map of an `Array[String]`.
+ fun snake_and_upper_strings is test do
+ var cs = ["helloWorld", "worldHello", "testCase"]
+ var actual = cs.iterator.map(snake_case_fn).map(upper_fn).to_a
+ var expected = ["HELLO_WORLD", "WORLD_HELLO", "TEST_CASE"]
+ assert actual == expected
+ end
+end
+
+# test cases using `iter_extras::Iterator::for_each`
+class TestForEach
+ test
+
+ fun add_one_to_all is test do
+ var xs = new Array[Ref[Int]]
+ var expected = new Array[Ref[Int]]
+ for i in [1..10] do
+ var r1 = new Ref[Int](i)
+ var r2 = new Ref[Int](i+1)
+ xs.push(r1)
+ expected.push(r2)
+ end
+ xs.iterator.for_each(add_one_proc)
+ assert xs == expected
+ end
+
+ fun for_each_empty_array is test do
+ var xs = new Array[Ref[Int]]
+ xs.iterator.for_each(add_one_proc)
+ assert xs.is_empty
+ end
+
+ fun for_each_on_singleton_array is test do
+ var r1 = new Ref[Int](1)
+ var r2 = new Ref[Int](2)
+ var xs = [r1]
+ xs.iterator.for_each(add_one_proc)
+ assert r1 == r2
+ assert xs == [r2]
+ end
+end
+
+# test cases using `iter_extras::Iterator::filter`
+class TestFilterIter
+ test
+
+ # test case for an empty `Array`
+ fun filter_empty_array is test do
+ var xs = new Array[Int]
+ var lt10 = lower_than_fn(10)
+ var actual = xs.iterator.filter(lt10).to_a
+ assert actual.is_empty
+ end
+
+ # test case for a `Range` whose elements doesn't match the predicate
+ fun filter_nomatch is test do
+ var xs = [1..10]
+ var lt0 = lower_than_fn(0)
+ var actual = xs.iterator.filter(lt0).to_a
+ assert actual.is_empty
+ end
+
+ # test case for a `Range` whose elements match 50% of a given predicate
+ fun filter_half_match_on_range_1_to_10 is test do
+ var xs = [1..10]
+ var lt6 = lower_than_fn(6)
+ var actual = xs.iterator.filter(lt6).to_a
+ var expected = [1,2,3,4,5]
+ assert actual == expected
+ end
+
+ # test case for an `Array` whose last element is the only matching element
+ # for a given predicate
+ fun only_last_element_is_a_letter is test do
+ var xs = "123a"
+ var actual = xs.iterator.filter(is_letter_fn).to_a.join
+ assert actual == "a"
+ end
+
+ # test case for a `String` containing mixed alphanumeric characters
+ fun only_letters is test do
+ var cs = "aaa123b4bb3333c1c32c"
+ assert cs.iterator.filter(is_letter_fn).to_a.join == "aaabbbccc"
+ end
+
+ # test case for a `String` containing only one letter in the middle
+ fun has_any_letter_true is test do
+ var cs = "12345a12345"
+ assert cs.iterator.any(is_letter_fn)
+ end
+
+ # test case for an empty `String` that should not contain any letter
+ fun empty_string_has_no_letter is test do
+ var cs = ""
+ assert not cs.iterator.any(is_letter_fn)
+ end
+
+ # test case for a `String` representing a number, should not have any letter
+ fun numeric_string_has_no_letter is test do
+ var cs = "123456"
+ assert not cs.iterator.any(is_letter_fn)
+ end
+end
+
+# test cases using `iter_extras::Iterator::flat_map`
+class TestFlatMapIter
+ test
+
+ # test case for combining three `String`
+ fun combine_aaa_bbb_ccc_to_aaabbbccc is test do
+ var cs = ["aaa","bbb","ccc"]
+ assert cs.iterator.flat_map(chars_fn).to_a.join == "aaabbbccc"
+ end
+
+ fun combine_empty_strings is test do
+ var cs = ["", ""]
+ assert cs.iterator.flat_map(chars_fn).to_a.join == ""
+ end
+
+ fun flat_map_over_empty_array is test do
+ var cs = new Array[String]
+ assert cs.iterator.flat_map(chars_fn).to_a.join == ""
+ end
+end
+
+# test cases using `iter_extras::Iterator::fold`
+class TestFoldIter
+ test
+
+ fun sum_an_empty_array is test do
+ var xs = new Array[Int]
+ var actual = xs.iterator.fold(0, sum_fn)
+ assert actual == 0
+ end
+
+ fun sum_1_to_10 is test do
+ var xs = [1..10]
+ var actual = xs.iterator.fold(0, sum_fn)
+ assert actual == 55
+ end
+
+ fun fold_one_element is test do
+ var xs = [1]
+ var actual = xs.iterator.fold(0, sum_fn)
+ assert actual == xs[0]
+ end
+end
+
+# test cases using `iter_extras::Iterator::fold1`
+class TestFold1Iter
+ test
+
+ fun find_min_in_mixed_array is test do
+ var xs = [45,424,11,43,7,5,8,9,1,-100]
+ var actual = xs.iterator.fold1(min_int_fn)
+ assert actual == -100
+ end
+
+ fun fold1_with_2_elements is test do
+ var xs = [0,-100]
+ var actual = xs.iterator.fold1(min_int_fn)
+ assert actual == -100
+ end
+end
+
+# test cases using `iter_extras::Iterator::order_by`
+class TestOrderedIter
+ test
+
+ fun order_empty_list_of_numbers is test do
+ var xs = new Array[Int]
+ var actual = xs.iterator.order_by(id_int).to_a
+ assert actual == xs
+ end
+
+ fun order_list_of_ints is test do
+ var xs = [5,4,3,2,1]
+ var actual = xs.iterator.order_by(id_int).to_a
+ var expected = [1,2,3,4,5]
+ assert actual == expected
+ end
+
+ fun order_singleton_list_of_ints is test do
+ var xs = [1]
+ var actual = xs.iterator.order_by(id_int).to_a
+ assert actual == xs
+ end
+
+ fun order_list_of_strings_by_alphabetical_order is test do
+ var xs = ["louis", "florian", "alexis", "jean", "alexandre"]
+ var actual = xs.iterator.order_by(id_str).to_a
+ var expected = ["alexandre", "alexis", "florian", "jean", "louis"]
+ assert actual == expected
+ end
+
+ fun order_list_of_strings_by_length is test do
+ var xs = ["louis", "florian", "alexis", "jean", "alexandre"]
+ var actual = xs.iterator.order_by(str_len).to_a
+ var expected = ["jean", "louis", "alexis", "florian", "alexandre"]
+ assert actual == expected
+ end
+end
--- /dev/null
+# This file is part of NIT ( http://www.nitlanguage.org ).
+#
+# Copyright 2019 Louis-Vincent Boudreault <lv.boudreault95@gmail.com>
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+# This module contains util classes and methods for `test_iter_extras`.
+import functional_types
+
+class SumFn
+ super Fun2[Int,Int,Int]
+
+ redef fun call(x, y)
+ do
+ return x + y
+ end
+end
+
+class MinFn[E: Comparable]
+ super Fun2[E,E,E]
+
+ redef fun call(x, y)
+ do
+ if x < y then
+ return x
+ end
+ return y
+ end
+end
+
+class InitArrayFn[E]
+ super Fun0[Array[E]]
+
+ var initial_val: nullable E
+
+ redef fun call
+ do
+ var xs = new Array[E]
+ if initial_val != null then
+ xs.push(initial_val)
+ end
+ return xs
+ end
+end
+
+class SnakeCaseFn
+ super Fun1[String,String]
+
+ redef fun call(x)
+ do
+ return x.to_snake_case
+ end
+end
+
+class UpperCaseFn
+ super Fun1[String, String]
+
+ redef fun call(x)
+ do
+ return x.to_upper
+ end
+end
+
+class IsLetterFn
+ super Fun1[Char, Bool]
+
+ redef fun call(c)
+ do
+ return c.is_letter
+ end
+end
+
+class AddOneFn
+ super Fun1[Int,Int]
+
+ redef fun call(x)
+ do
+ return x + 1
+ end
+end
+
+class CharsFn
+ super Fun1[String, Iterator[Char]]
+
+ redef fun call(str)
+ do
+ return str.chars.iterator
+ end
+end
+
+class LowerThanFn
+ super Fun1[Int, Bool]
+ var target: Int
+ redef fun call(x)
+ do
+ return x < target
+ end
+end
+
+class IdFn[E]
+ super Fun1[E,E]
+ redef fun call(x)
+ do
+ return x
+ end
+end
+
+class StrLenFn
+ super Fun1[String,Int]
+ redef fun call(x)
+ do
+ return x.length
+ end
+end
+
+class AddOneProc
+ super Proc1[Ref[Int]]
+ redef fun call(x)
+ do
+ x.item += 1
+ end
+end
+
+fun sum_fn: SumFn
+do
+ return new SumFn
+end
+
+fun min_int_fn: MinFn[Int]
+do
+ return new MinFn[Int]
+end
+
+fun new_int_arr(x: nullable Int): InitArrayFn[Int]
+do
+ return new InitArrayFn[Int](x)
+end
+
+fun snake_case_fn: SnakeCaseFn
+do
+ return new SnakeCaseFn
+end
+
+fun upper_fn: UpperCaseFn
+do
+ return new UpperCaseFn
+end
+
+fun is_letter_fn: IsLetterFn
+do
+ return new IsLetterFn
+end
+
+fun add_one: AddOneFn
+do
+ return new AddOneFn
+end
+
+fun add_one_proc: AddOneProc
+do
+ return new AddOneProc
+end
+
+fun chars_fn: CharsFn
+do
+ return new CharsFn
+end
+
+fun lower_than_fn(x: Int): LowerThanFn
+do
+ return new LowerThanFn(x)
+end
+
+fun id_int: IdFn[Int]
+do
+ return new IdFn[Int]
+end
+
+fun id_str: IdFn[String]
+do
+ return new IdFn[String]
+end
+
+fun str_len: StrLenFn
+do
+ return new StrLenFn
+end