Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Reduce<T> returns T instead of Option<T> #583

Closed
bender2k14 opened this issue Apr 20, 2019 · 11 comments

Comments

@bender2k14
Copy link
Contributor

commented Apr 20, 2019

Consider this reduce method:

public static T reduce<T>(IEnumerable<T> list, Func<T, T, T> reducer) =>
    match(headOrNone(list),
        Some: x => fold(tail(list), x, reducer),
        None: () => failwith<T>("Input list was empty")
    );

I was surprised to see that it throws an exception when list is empty.

Wouldn't the functional approach be to have the return type be Option<T> and return None when list is empty?

@louthy

This comment has been minimized.

Copy link
Owner

commented Apr 24, 2019

The expectation is that the first item in the list is used as the initial value of the fold operation, and therefore it's exceptional if there are no items in the list. So, this is reasonable. The argument is invalid.

@louthy

This comment has been minimized.

Copy link
Owner

commented Apr 24, 2019

Although this looks like it could be updated to be more efficient now that Seq exists:

public static T reduce<T>(IEnumerable<T> list, Func<T, T, T> reducer) =>
    list.Match(
        ()      => failwith<T>("Input list was empty"),
        (x, xs) => fold(xs, x, reducer));
@bender2k14

This comment has been minimized.

Copy link
Contributor Author

commented Apr 24, 2019

The expectation is that the first item in the list is used as the initial value of the fold operation, and therefore it's exceptional if there are no items in the list. So, this is reasonable. The argument is invalid.

Sure, the arguments are invalid. But isn't one of the design goals in functional programming to make invalid possibilities unrepresentable?

And isn't another goal to write pure functions? Enrico Buonanno on page 32 of Functional Programming in C# defines pure functions in part by forbidding them from throwing exceptions. By his definition, this function in impure.

It seems to me that we could change the types involved to more accurately convey what this function does...that is, to make this function pure.

  1. The suggestion I gave above is to return Option<T> instead of throwing an exception.
  2. If you want to stick with the idea of an exception, we could return Try<T> instead.
  3. Or if we really only want this function to use a nonempty sequence, then we can create a type that represents a nonempty sequence so that all inputs would be valid.

My preference is still for option 1.

@louthy

This comment has been minimized.

Copy link
Owner

commented Apr 24, 2019

Here is the equivalent in Haskell:

http://hackage.haskell.org/package/base-4.12.0.0/docs/src/Data.Foldable.html#foldl1

Here is the equivalent in F#:

https://msdn.microsoft.com/en-us/visualfsharpdocs/conceptual/list.reduce%5B%27t%5D-function-%5Bfsharp%5D

Both throw exceptions.

Changing this function to change the return type will break users' code. I am not against a reduceOrNone function that returns an Option, but I have no plans for changing this function. Exceptions are not intrinsically bad when the input arguments are invalid. Your argument invites every function (that could have input variables out-of-range) to return Option .

@bender2k14

This comment has been minimized.

Copy link
Contributor Author

commented Apr 24, 2019

I like using and writing honest functions as Enrico defined them in section 3.2.3:

  • An honest function is simply one that does what it says on the tin; it honors its signature—always.
  • An honest function does exactly what the signature says.
  • A dishonest function can have an outcome that isn’t accounted for in the signature.
    ...
    That means this function is "dishonest"—what it really should say is "Give me an int, and I may return a Risk, or I may throw an exception instead." Sometimes there are legitimate reasons why a computation can fail, but in this example, constraining the function input so that the function always returns a valid value, is a much cleaner solution.
    In summary, a function is honest if its behavior can be predicted by its signature: it returns a value of the declared type; no throwing exceptions, and no null return values. Note that these requirements are less stringent than function purity—"honesty" is an informal term, less technical and less rigorously defined than purity, but still useful.

I don't see why other languages choosing to include impure/dishonest functions means that your library must do the same. In fact, my impression is that Language Ext is designed to do the opposite. Where C#/.Net provides int int.Parse(string) that could throw an exception or bool int.TryParse(string, out int) with its awful out parameter, Language Ext provides the honest and pure function Option<int> parseInt(string).

Certainly this would be a breaking change; there is no doubt about that.

Your argument invites every function (that could have input variables out-of-range) to return Option.

Sure, one way to change an impure/dishonest function to one that is pure/honest is to weaken its output type. This is discussed by Enrico in section 3.4.5. However, this is not the only way. Another possibility is to strengthen the input types. Enrico discusses this in section 3.2.2. An example of this is the third change possibility that I listed above. Typically, I prefer to strengthen the input types, but in this situation with Reduce, I prefer to weaken the output type.

@louthy

This comment has been minimized.

Copy link
Owner

commented Apr 24, 2019

We don't have dependent types, so it's not convenient to do this for every function. There always has to be a balance between ease of use and honesty. Just, like the head function, the reduce function is explicitly for working with collections of 1 or more as stated in the documentation, and it follows the same approach as other languages that have this function - I think the balance is correct here.

@louthy

This comment has been minimized.

Copy link
Owner

commented Apr 24, 2019

Actually, another aspect of this is the function really isn't as dishonest as you think. The signature clearly shows that it needs to return an A. And, if you don't provide an A as an argument (and empty collection), where can it get it from? The only option is to throw or return default(A). The first option must be the obvious choice, especially based on the documentation.

@louthy

This comment has been minimized.

Copy link
Owner

commented Apr 24, 2019

I have added reduceOrNone and reduceBackOrNone

@bender2k14

This comment has been minimized.

Copy link
Contributor Author

commented Apr 24, 2019

Sure, sometimes we need less safe options for pragmatic reasons.

Another design goal I see in functional programming relates to the names involved when there is a safe and an unsafe way to do something. I think the idea is that the shorter name, i.e. the one that is easier to read and write, is given to the safer approach.

For example, in F# records are immutable by default, so merely writing

type ComplexNumber = { real: float; imaginary: float }

specifies the safer approach. To specify the less safe approach, additional words are required, namely

type ComplexNumber = { mutable real: float; mutable imaginary: float }

If we added the function Option<T> reduceOrNone(IEnumerable<T>, Func<T, T, T>), then it would be safer than reduce but would have the less privileged name.

What do you think about modifying the names so that the signatures would be like this?

Option<T> reduce(IEnumerable<T>, Func<T, T, T>)
T reduceOrException(IEnumerable<T>, Func<T, T, T>)
@louthy

This comment has been minimized.

Copy link
Owner

commented Apr 24, 2019

I think it's a bad idea, sorry.

@StefanBertels

This comment has been minimized.

Copy link
Contributor

commented May 9, 2019

Just my two cents: I had this question myself. But I don't have a solution therefore agree with Paul, for now.

I agree with @bender2k14 that this function doesn't feel pure. It's not about the fact that some inputs might throw an exception (like overflow in something like int multiply(int, int)) but because the natural identity of most inputs (Monoids) will throw, e.g. default(Lst<int>). This makes it error-prone.

Side note: Currently we cannot get full/dogmatic purism anyway because this is valid code, too: List(1, 2, 3).Reduce(null). (Hmm, thinking whether reducer argument should be a struct ...)

Besides breaking changes I don't think Option or Try are a good fit here because then reduce would do two things in one: assure that the input isn't empty (match) and reduce. Therefore the third option (only allow containers with at least one element) would be the cleanest approach. But I don't see a practical solution. We would need to kind of "subclass" any list/sequence type.

One could build a workaround by having another type like:

class NonEmpty<T> where T is a list type

Then we could throw on var nonEmpty = nonempty(myList) -- this would fail early.
calling (specific) reduce on this type would never fail.

We could make this a bit more general adding Deconstruct to this type resulting in (x, xs) (Seq / Cons semantics. Maybe this could be an option for existing types? Think about:

            var y = List(1, 2);
            (int x, Lst<int> xs) = y;   // or Seq?

Obviously there is no big advantage calling this deconstructor (or some other operator like nonempty) in the same function.

We could also support some (x, xs).Reduce(reducer) or reduce(x, xs, reducer) to make this (fail-safe) variant more accessible.

Thinking in this direction this issue is related to #275 and the general question how to express non-empty sequences.

As said before: I don't see a practical general solution here -- even if we drop the compatibility aspect.

Regarding breaking code / compatibility: I personally would gladly accept the cost of changing my code if the new concept is definitely better, still easy to use and if I can be sure that old code wouldn't compile.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
3 participants
You can’t perform that action at this time.