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?

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)

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);
    }
  }
}

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.