Pseudo pattern-matching / total fold

[Mauricio Scheffer]

Hi Sandro,

There doesn't seem to be a built-in function to decompose Option/Either/etc . I can write my own as a trivial extension method, e.g.:

        public static R Switch<T, R>(this Option<T> v, Func<T, R> some, Func<R> none)
        {
            T value;
            if (v.TryGetValue(out value))
                return some(value);
            return none();
        }

But when type inference fails I need to give two type arguments, as opposed to one if this was defined as part of the Option type, which is a bit annoying.
I think we had this conversation before, but I can't remember precisely. Is it a design decision not to have such a method in Sasa?

Cheers,
Mauricio

[naasking]

Hey Mauricio,

I used to support such pattern-matching-like method, but it's much too expensive in practice, which simply discourages the use of option/either types. As your example shows, deconstruction via TryGetValue is already total and efficient, albiet a little less syntactically convenient.

I think we did have this discussion before, just not on the Sasa forums. If you can think of a compelling use-case that isn't covered, I could be convinced to add it back. The only situation where TryGetValue is forbidden but lambdas are permitted are in Linq Expressions. But Option itself provides a Linq query interface, so you could just use that.

The Either type has IsFirst and supports access properties, so you could simply use that in Linq expressions, ie.

from x in EitherFooBar
select x.IsFirst ? WithFoo(x.First.Value) : WithBar(x.Second.Value)

Not quite as safe as a pattern-matching method, but more concise and efficient.

Sandro

[Mauricio Scheffer]

The main problem I see with TryGetValue is that for side effects (i.e. in a void method) it doesn't force you to consider all cases, i.e. it's analogous to a non-exhaustive pattern match.

For functions it's mostly ok as the language forces you to return something so it is exhaustive, but it doesn't create a scope for the None case and it doesn't prevent you from using the uninitialized output variable.

The other problem is probably just mostly an annoyance: since TryGetValue is imperative and not an expression, so you can't use it directly e.g. in a collection initializer, and of course the larger or more nested the collection you're building the more annoying this is.

Cheers,
Mauricio

[naasking]

For Option, TryGetValue does force you to consider all cases since it's a binary Some|None case. I agree the scoping is less than ideal, but it seems the best I can do without the overhead of delegates for matching. I had considered keeping that matching function and then adding an inlining pass to ilrewrite, but I just don't have the time. That would be the ideal approach, so if you feel like delving into Mono.Cecil, I happily accept contributions! :-)

Either has more cases, so I agree it's less safe as there's no exhaustiveness guarantee with TryFirst+TrySecond. If you have other suggestions, I'm open. I don't think a native switch on an enum is exhaustively checked either. I had considered something like this though:

public enum Either3 { First, Second, Third }
...
T0 x0; T1 x1; T2 x;
switch(either.TryGetValue(out x0, out x1, out x2))
{
    case Either3.First:  // use x0
    case Either3.Second: // use x1
    case Either3.Third:  // use x2
    default: throw new InvalidOperationException("Impossible!");
}

This is exhaustive, but it doesn't force you to use the right local for the given case. At least with a chained set of if-statements, you can't accidentally reference improper locals around half the time:

T0 x0;
if (either.TryFirst(out x0))  // use x0, can't use x1, x2
T1 x1;
if (either.TrySecond(out x1)) // use x0, x1, can't use x2
T2 x2;
if (either.TryThird(out x2))  // use x0, x1, x2
throw new InvalidOperationException("Impossible!");

Re:TryGetValue can't be used in an initializer, that's why Option has HasValue+Value properties, and Either has IsFirst+First|IsSecond+Second properties. So the API is complete, it's just not quite as safe as it could be due to lack of exhaustiveness checking, and I don't see a way of achieving the safety without sacrificing a lot of performance.

Then again, perhaps I'm overestimating the cost of the delegate API. If you want to run a benchmark I'd abide by the results. If runtime and memory usage of a representative benchmark maintains a cost within 20% of the current API, I think that's reasonable enough to support pattern matching via delegates given the additional safety benefits.

[Mauricio Scheffer]

Right, the difference is I'm willing to pay the price for the delegate overhead without even checking what the overhead is as I'm not writing any high-performance code.
But I'll try to come back with a benchmark to make a proper decision.

Cheers,
Mauricio