Where did Option[T] come from in Scala?

Question

I'm still a noob in Scala development but I have found the Option[T] concept really awesome, specially the pattern matching when used with Some and None. I am even implementing it so some extent in a C# project I'm working on at the moment, but as there is no pattern matching in there is isn't really that awesome.

The real question is, where is the theory behind this object? is it something specific from Scala? Funcional languages? Where can I find more about it?

Bridie

In fairness, you don't need the pattern-matching for most of Option's awesomeness. You just need declaration-site covariance, a bottom type, lambdas and lazy evaluation. Use map+getOrElse instead of pattern match – Lumisterol

Indeed. I use Option all the time in C#, it fits well into LINQ. – Publus

@oxbow_lakes: what does that stuff have to do with Option's awesomeness? lambdas, maybe, to use with map, but what do | and laziness have to do with it? – Pouncey

Answer 1

Most of the time I was thinking that it comes from the Haskell, and has a name of Maybe monad

But after a little research, I've found that there was some references on option types in SML papers, as @ShiDoiSi said. Moreover, it has the same semantics (Some/None) that Scala has. The elderest paper I was able to find is that (circa '89) (see footnote on the 6th page)

Piane

Answer 2

You don't need pattern-matching to use Option. I have written it in C# for you below. Note that the Fold function takes care of anything that would otherwise be pattern-matched.

Pattern-matching is generally discouraged in favour of higher-level combinators. For example, if your particular function can be written using Select you would use it rather than Fold (which is equivalent to pattern-matching). Otherwise, assuming side-effect free code (and therefore, equational reasoning), you would essentially be re-implementing existing code. This holds for all languages, not just Scala or C#.

using System;
using System.Collections;
using System.Collections.Generic;

namespace Example {
  /// <summary>
  /// An immutable list with a maximum length of 1.
  /// </summary>
  /// <typeparam name="A">The element type held by this homogenous structure.</typeparam>
  /// <remarks>This data type is also used in place of a nullable type.</remarks>
  public struct Option<A> : IEnumerable<A> {
    private readonly bool e;
    private readonly A a;

    private Option(bool e, A a) {
      this.e = e;
      this.a = a;
    }

    public bool IsEmpty {
      get {
        return e;
      }
    }

    public bool IsNotEmpty{
      get {
        return !e;
      }
    }

    public X Fold<X>(Func<A, X> some, Func<X> empty) {
      return IsEmpty ? empty() : some(a);
    }

    public void ForEach(Action<A> a) {
      foreach(A x in this) {
        a(x);
      }
    }

    public Option<A> Where(Func<A, bool> p) {
      var t = this;
      return Fold(a => p(a) ? t : Empty, () => Empty);
    }

    public A ValueOr(Func<A> or) {
      return IsEmpty ? or() : a;
    }

    public Option<A> OrElse(Func<Option<A>> o) {
      return IsEmpty ? o() : this;
    }

    public bool All(Func<A, bool> f) {
      return IsEmpty || f(a);
    }

    public bool Any(Func<A, bool> f) {
      return !IsEmpty && f(a);
    }

    private A Value {
      get {
        if(e)
          throw new Exception("Value on empty Option");
        else
          return a;
      }
    }

    private class OptionEnumerator : IEnumerator<A> {
      private bool z = true;
      private readonly Option<A> o;
      private Option<A> a;

      internal OptionEnumerator(Option<A> o) {
        this.o = o;
      }

      public void Dispose() {}

      public void Reset() {
        z = true;
      }

      public bool MoveNext() {
        if(z) {
          a = o;
          z = false;
        } else
          a = Option<A>.Empty;

        return !a.IsEmpty;
      }

      A IEnumerator<A>.Current {
        get {
          return o.Value;
        }
      }

      public object Current {
        get {
          return o.Value;
        }
      }
    }

    private OptionEnumerator Enumerate() {
      return new OptionEnumerator(this);
    }

    IEnumerator<A> IEnumerable<A>.GetEnumerator() {
      return Enumerate();
    }

    IEnumerator IEnumerable.GetEnumerator() {
      return Enumerate();
    }

    public static Option<A> Empty {
      get {
        return new Option<A>(true, default(A));
      }
    }

    public static Option<A> Some(A t) {
      return new Option<A>(false, t);
    }
  }
}

Yellowgreen

"Pattern-matching is generally discouraged in favour of higher-level combinators" - I find this to be generally true with the Scala community, although personally I strongly disagree with this notion. – Pouncey

It is not a controversial statement. – Yellowgreen

And when Tony Morris says something isn't a controversial statement, that means something (albeit not necessarily what he actually said). – Basque

Providing your usual amount of insight and usefulness I see. – Yellowgreen

Answer 3

Wikipedia is your friend: http://en.wikipedia.org/wiki/Option_type

Unfortunately it doesn't give any dates, but I'd bet that it's ML-origin predates Haskell's Maybe.

Selfacting