functional: Added functional lib

- 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>

diff --git a/lib/functional/README.md b/lib/functional/README.md
new file mode 100644 (file)
index 0000000..849a1ae
--- /dev/null
+++ b/lib/functional/README.md
@@ -0,0 +1,108 @@
+# 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`.

diff --git a/lib/functional/functional.nit b/lib/functional/functional.nit
new file mode 100644 (file)
index 0000000..fcf5f54
--- /dev/null
+++ b/lib/functional/functional.nit
@@ -0,0 +1,20 @@
+# 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

diff --git a/lib/functional/functional_gen.nit b/lib/functional/functional_gen.nit
new file mode 100644 (file)
index 0000000..2bfa266
--- /dev/null
+++ b/lib/functional/functional_gen.nit
@@ -0,0 +1,110 @@
+# 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)

diff --git a/lib/functional/functional_types.nit b/lib/functional/functional_types.nit
new file mode 100644 (file)
index 0000000..4724064
--- /dev/null
+++ b/lib/functional/functional_types.nit
@@ -0,0 +1,188 @@
+# 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

diff --git a/lib/functional/iter_extras.nit b/lib/functional/iter_extras.nit
new file mode 100644 (file)
index 0000000..ec5efe4
--- /dev/null
+++ b/lib/functional/iter_extras.nit
@@ -0,0 +1,408 @@
+# 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 = &lt10
+        # 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 = &lt10
+        # 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

diff --git a/lib/functional/package.ini b/lib/functional/package.ini
new file mode 100644 (file)
index 0000000..b1e2311
--- /dev/null
+++ b/lib/functional/package.ini
@@ -0,0 +1,12 @@
+[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

diff --git a/lib/functional/test_iter_extras.nit b/lib/functional/test_iter_extras.nit
new file mode 100644 (file)
index 0000000..c60b896
--- /dev/null
+++ b/lib/functional/test_iter_extras.nit
@@ -0,0 +1,258 @@
+# 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

diff --git a/lib/functional/test_utils.nit b/lib/functional/test_utils.nit
new file mode 100644 (file)
index 0000000..ee11557
--- /dev/null
+++ b/lib/functional/test_utils.nit
@@ -0,0 +1,197 @@
+# 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