Missing type of reduce with initial seed in declarative form

[Phryxia]

Bug Report

Consider following scenario.

sample x, y from R^3 (ex: [1, 2, 3], [4, 5, 6])
compute inner product of <x, y>

Currently, with FxTS, it can be done with following pipeline

function dot(a: Iterable<number>, b: Iterable<number>) {
  return pipe(
    zip(a, b),
    map(([a, b]) => a * b),
    reduce((acc, x) => acc + x),
  )
}

But actually, I tried with following approach at first, which has type failure. Interestingly this works if I bypass type check. And it seems to be natural to do so, similar to other FxTS APIs. I think I was wrong at that time for some unknown reasons. It is not supported in current version. (added on 2024-02-17)

function dot2(a: Iterable<number>, b: Iterable<number>) {
  return pipe(
    zip(a, b),
    reduce((acc, [x, y]) => acc + x * y, 0), // <----- no appliable signature
  )
}

🙁 Actual behavior

There is no such type signature for declarative form of reduce with seed in the type definition.

🙂 Expected behavior

Maybe, this might work. If you consider this is valid, tell me so I'll raise for pull request.

function reduce<
  A extends Iterable<unknown> | AsyncIterable<unknown>, 
  B
>(f: (a: B, b: IterableInfer<A>) => B | Promise<B>, seed: B): (iterable: A) => ReturnValueType<A, B>;

---

Version Information

• Operating system: Windows 10
• Typescript: TypeScript 4.8
• Nodejs: v16.16.0

[ppeeou]

Thank you for your interest :)

I think it could be a better expression
I'm not sure if it can be implemented with the signature
If you can implement it, please share it🙏

This is something we discussed previously regarding reduce #130 (comment)

and it would be difficult to change the existing interface because of existing users😭

[Phryxia]

@ppeeou
Well that's wild. I'll inspect such cass more, and report here.

By the way, can you give an actual example of seed being iterable please? I haven't understood the situation of seed being iterable so that curry can be used. (Not the vague cases in #130. I comprehended them)

[Phryxia]

It turns out that there is no way to support both seed and high order reduce in a single function signature.

Terminology

Let's define some terminology for this issue.

• reducer: function parameter of reduce to merge incomming values.
  • reducer have at least two parameters.
  • acc (which is abbreviation of accumulation) is the first parameter of reducer, has merged thing from past.
  • value is the second parameter of reducer, fed by iterable things.
• reduce is homogeneous iff type of acc = type of value
• reduce is heterogeneous iff it's not homogeneous.
• reduce is 2st order returning iff it returns a function.
• reduce is 1st order returning iff it's not 2st order.

Possibilities

We'd like to support following 6 cases of reduce. For simplicity, let T be type fed by programmer, A be type of acc, F be type of reducer, R be type of reduce.

order	homgeneous, no seed	homogeneous, seed	heterogeneous, seed
1st	F = (T × T) → T R = (F × I<T>) → T	F = (T × T) → T R = (F × T × I<T>) → T	F = (A × T) → A R = (F × A × I<T>) → A
2nd	F = (T × T) → T R = F → I<T> → T	F = (T × T) → T R = (F × T) → I<T> → T	F = (A × T) → A R = (F × A) → I<T> → A

3 parameter cases don't matter because they're disjoint and support all possible ways of having seed. 1 parameter case is just unique so let's ignore them.

The major problem is solving confusing cases which have 2 parameters.

• 1st, homogeneous, no seed
• 2nd, homogeneous, seed
• 2nd, heterogeneous, seed

Our goal is making TypeScript distinguish these three cases.

Ambiguity

Complete logic of type inference is not well known (and I don't know either), but one thing is sure: It's imperfect and kind of greedy (I think backtracking may cause exponential inference time). As my guess, following seems to be true.

1. If types in generic are explicitly given, then it judges its parameters.
2. If types in generic are not given, but implicitly inferrable, it'll try to find the best matching declaration.
3. If it fails, it just fallback to first possibilitiy in branch.

So let's discard the first explicit case. Now we assume that user may give imperfect partial type information via parameters.

Theorem 1

If T is not iterable of something, these 3 cases are distinguishable.

Since T never be iterable, if second parameter is inferred as iterable, then it must be 1st, homo, no seed. Otherwise they must be one of 2nd, homo, seed and 2nd, hetero, seed.

Theorem 2

If T is iterable of something, there is a situation where TypeScript can't distinguish them.

When I<T> is known, but T is not known

reduce((acc: any, value: unknown) => unknown, Iterable<number>)

Since the only source to infer T is second parameter Iterable<number>, TypeScript just tries T := number. And there is always such matching, which is 1st, homo, no seed, it always infer as first case. But try this code.

const fn = reduce((acc, value) => [...acc, ...value], [] as Iterable<number>)

Here user might intend T as Iterable<number> with seed []. But value is already infered as number, failure occurs.

When T is known

Sadly it also makes ambiguous case. Following code can be intended as T := number[] for 2nd, homo, seed, it's interpreted as 1st, homo, no seed.

// actual code
reduce((acc, value: number[]) => [...acc, ...value], [])

// user intend
reduce(callback, [] as number[]) // seed

// typescript comprehension
reduce(callback, [] as Iterable<number[]>)

If I even provide I<T> problem isn't resolved.

// actual code
reduce((acc, value: number[]) => [...acc, ...value], [] as number[])

// user intend
reduce(callback, [] as number[]) // seed

// typescript comprehension
reduce(callback, [] as Iterable<number>)

For your interest, here a typescript playground

Conclusion

There is no way to support both iterable seed and high order function form.

The only dirty alternative is adding new function signature for 2nd order returning case. And actually its implementation is same as original one.

declare function reduceLazy<T>(f: (acc: T, value: T) => T): (it: Iterable<T>) => T
declare function reduceLazy<T>(f: (acc: T, value: T) => T, seed: T): (it: Iterable<T>) => T
declare function reduceLazy<T, A>(f: (acc: A, value: T) => A, seed: A): (it: Iterable<T>) => A

It doesn't break compatibility, and it doesn't introduce any ambiguity. It's really dirty but, the only way to preserve previous usages. If you have more better idea or function name please let me know.

[Phryxia]

@ppeeou

Any further discussion? I think adding reduceLazy is the best option for current status.

[ppeeou]

@Phryxia Sorry for the late reply.

I also studied what you wrote.

By adding the necessary expressions without breaking the existing usage,
Adding reduceLazy doesn't seem like a bad idea.

[Phryxia]

By adding the necessary expressions without breaking the existing usage,
Adding reduceLazy doesn't seem like a bad idea.

Thank you for your response. I'll work this on this weekend.

[ppeeou]

It's released 🎉
https://fxts.dev/docs/reduceLazy