From: Louis-Vincent Boudreault Date: Fri, 5 Jul 2019 14:02:18 +0000 (-0400) Subject: functional: Added functional lib X-Git-Url: http://nitlanguage.org 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 --- diff --git a/lib/functional/README.md b/lib/functional/README.md new file mode 100644 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 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 +# +# 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 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 +# +# 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 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 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 +# +# 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 diff --git a/lib/functional/package.ini b/lib/functional/package.ini new file mode 100644 index 0000000..b1e2311 --- /dev/null +++ b/lib/functional/package.ini @@ -0,0 +1,12 @@ +[package] +name=functional +tags=functional,types +maintainer=Louis-Vincent Boudreault +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 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 +# +# 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 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 +# +# 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