Add transducers support

[sobolevn]

https://medium.com/javascript-scene/transducers-efficient-data-processing-pipelines-in-javascript-7985330fe73d
https://dev.to/romanliutikov/understanding-transducers-in-javascript-4pdg

Currently we use very straight-to-action helpers. Sometimes we might need more efficient ones.
Here why we need transducers.

[thepabloaguilar]

https://ramdajs.com/docs/#expand

[thepabloaguilar]

https://github.com/cognitect-labs/transducers-python

[thepabloaguilar]

We can implement based in the link above, it was inspired by Clojure implementation that has some cool features like early termination using Reduced sentinel!

In fact almost everything there can be translated to returns using typing, specially the transducers parts!
I've written the transducers for map and filter:

def mapping(
    function: Callable[[_T], _T],
) -> Callable[
    [Callable[[List[_T], _T], List[_T]]],
    Callable[[List[_T], _T], List[_T]],
]:
    def reducer(
        reducing: Callable[[List[_T], _T], List[_T]],
    ) -> Callable[[List[_T], _T], List[_T]]:
        def map_(
            collection: List[_T],
            item: _T,
        ) -> List[_T]:
            return reducing(collection, function(item))
        return map_
    return reducer

def filtering(
    predicate: Callable[[_T], bool],
) -> Callable[
    [Callable[[List[_T], _T], List[_T]]],
    Callable[[List[_T], _T], List[_T]],
]:
    def reducer(
        reducing: Callable[[List[_T], _T], List[_T]],
    ) -> Callable[[List[_T], _T], List[_T]]:
        def filter_(
            collection: List[_T],
            item: _T
        ) -> List[_T]:
            if predicate(item):
                return reducing(collection, item)
            return collection
        return filter_
    return reducer

P.S.: The types in my code are wrong yet 'cause transducers should work with any kind of input and there I'm fixing List[_T]

[sobolevn]

Great stuff!

[thepabloaguilar]

Maybe is because I'm so tired now after many hours in front of a computer, but I can't figure out how to solve the problem I'm getting.

Transducer map implementation:

_ValueType = TypeVar('_ValueType')
_NewValueType = TypeVar('_NewValueType')

_AccType = TypeVar('_AccType')
_NewAccType = TypeVar('_NewAccType')


def tmap(
    function: Callable[[_ValueType], _NewValueType],
) -> Callable[
    [Callable[[_AccType, _NewValueType], _AccType]],
    Callable[[_AccType, _ValueType], _AccType],
]:
    def reducer(
        reducing: Callable[[_AccType, _NewValueType], _AccType],
    ) -> Callable[[_AccType, _ValueType], _AccType]:
        def map_(acc: _AccType, value: _ValueType) -> _AccType:
            return reducing(acc, function(value))
        return map_
    return reducer

Every type seems correct:

• function should be the function we normally pass to a map, like, lambda item: str(item)
  • Callable[[_ValueType], _NewValueType]
• reducing is the function to reduce/next step, like, lambda acc, value: acc + value
  • Callable[[_AccType, _NewValueType], _AccType]
• The others are basic types, should be correct as well

But when I try to make a composition I got a error, but it should work!

Test case:

from typing import List
from returns.transducers import tmap

def to_str(number: int) -> str:
    ...

f_step = tmap(to_str)
second_step = f_step(tmap(to_str))

Test output:

E   Actual:
E     main:14: error: Argument 1 has incompatible type "Callable[[Callable[[_AccType, Any], _AccType]], Callable[[_AccType, Any], _AccType]]"; expected "Callable[[Any, str], Any]" (diff)
E     main:14: error: Cannot infer function type argument (diff)

Like, Any shouldn't be there.

---

Other test cases works fine:

from returns.transducers import tmap

def to_str(number: int) -> str:
    ...

reveal_type(tmap(to_str))  # N: Revealed type is 'def [_AccType] (def (_AccType`-3, builtins.str*) -> _AccType`-3) -> def (_AccType`-3, builtins.int*) -> _AccType`-3'

from typing import List
from returns.transducers import tmap

def to_str(number: int) -> str:
    ...

def append(collection: List[str], item: str) -> List[str]:
    ...

reveal_type(tmap(to_str)(append))  # N: Revealed type is 'def (builtins.list*[builtins.str], builtins.int) -> builtins.list*[builtins.str]'

from typing import List
from returns.transducers import tmap

def to_str(number: int) -> str:
    ...

def append(collection: List[str], item: str) -> List[str]:
    ...

my_list: List[str]
reveal_type(tmap(to_str)(append)(my_list, 2))  # N: Revealed type is 'builtins.list*[builtins.str]'

[thepabloaguilar]

I'd love to know if you have any tips @sobolevn!!

[thepabloaguilar]

Btw, the actual implementation is working normally:

>>> def append(a, v):
...     a.append(v)
...     return a

>>> tmap(str)(tmap(int)(append))([], 1)
[1]

[thepabloaguilar]

Ok, I think the composition I've made is wrong! I'll see tomorow

[thepabloaguilar]

@sobolevn I remember a discussion from #451, what will be a great name for this feature?

Options:

• Transducers (no change the name)
• Transform
• Reducees (from Elixir, tks @bruno-delfino1995 for the link)
• (Other options you can suggest)

[thepabloaguilar]

Ok, I think the composition I've made is wrong! I'll see tomorow

Well, my composition was wrong and my thought too hahaha

The types are working correctly with the composition:

>>> from returns.transducers import tmap
>>> append = lambda a, v: a.append(v) or a
>>> tmap(int)(tmap(str)(append))([], '1')
['1']

[thepabloaguilar]

@sobolevn You can see the progress in this draft PR (yet) or in a very preview documentation here

[thepabloaguilar]

I have a suggestion, in the actual implementation way the user need to build "everything" by hand like:

xform = compose(
    tmap(func),
    tfilter(func),
)

result = transduce(
    xform,
    reducing_func,
    initial,
    data_to_process,
)

My ideia is to incapsulate in a class:

t = (
    Transformation
        .map(func)
        .filter(func)
)

result = t(
    reducing_func,
    initial,
    data_to_process,
)

Using a class makes clear to the users that they are receiving a transformation instead of a random function!

[sobolevn]

Yeah, why not!