Saturday, June 22, 2013

Maybe

There are different approaches to the issue of not having a value to return. One idiom to deal with this in C++ is the use of boost::optional<T> or std::pair<bool, T>.
class boost::optional<T> //Discriminated-union wrapper for values.

Maybe is a polymorphic sum type with two constructors : Nothing or Just a.
Here's how Maybe is defined in Haskell.

  {- The Maybe type encapsulates an optional value. A value of type
  Maybe a either contains a value of type a (represented as Just a), or
  it is empty (represented as Nothing). Using Maybe is a good way to
  deal with errors or exceptional cases without resorting to drastic
  measures such as error.

  The Maybe type is also a monad.
  It is a simple kind of error monad, where all errors are
  represented by Nothing. -}

  data Maybe a = Nothing | Just a

  {- The maybe function takes a default value, a function, and a Maybe
  value. If the Maybe value is Nothing, the function returns the default
  value. Otherwise, it applies the function to the value inside the Just
  and returns the result. -}

  maybe :: b -> (a -> b) -> Maybe a -> b
  maybe n _ Nothing  = n
  maybe _ f (Just x) = f x

I haven't tried to compile the following OCaml yet but I think it should be roughly OK.
 type 'a option = None | Some of 'a  ;;

  let maybe n f a =
    match a with
      | None -> n
      | Some x -> f x
      ;;

Here's another variant on the Maybe monad this time in Felix. It is applied to the problem of "safe arithmetic" i.e. the usual integer arithmetic but with guards against under/overflow and division by zero.

  union success[T] =
    | Success of T
    | Failure of string
    ;

  fun str[T] (x:success[T]) =>
    match x with
      | Success ?t => "Success " + str(t)
      | Failure ?s => "Failure " + s
    endmatch
    ;

  typedef fun Fallible (t:TYPE) : TYPE => success[t] ;

  instance Monad[Fallible]
  {
    fun bind[a, b] (x:Fallible a, f: a -> Fallible b) =>
      match x with
        | Success ?a => f a
        | Failure[a] ?s => Failure[b] s
      endmatch
      ;

    fun ret[a](x:a):Fallible a => Success x ;
  }

  //Safe arithmetic.

  const INT_MAX:int requires Cxx_headers::cstdlib ;
  const INT_MIN:int requires Cxx_headers::cstdlib ;

  fun madd (x:int) (y:int) : success[int] =>
    if x > 0 and y > (INT_MAX - x) then
        Failure[int] "overflow"
    else
      Success (y + x)
    endif
    ;

  fun msub (x:int) (y:int) : success[int] =>
    if x > 0 and y < (INT_MIN + x) then
      Failure[int] "underflow"
    else
      Success (y - x)
    endif
    ;

  fun mmul (x:int) (y:int) : success[int] =>
    if x != 0 and y > (INT_MAX / x) then
      Failure[int] "overflow"
    else
      Success (y * x)
    endif
    ;

  fun mdiv (x:int) (y:int) : success[int] =>
      if (x == 0) then
          Failure[int] "attempted division by zero"
      else
        Success (y / x)
      endif
      ;

  //--
  //
  //Test.

  open Monad[Fallible] ;

  //Evalue some simple expressions.

  val zero = ret 0 ;
  val zero_over_one = bind ((Success 0), (mdiv 1)) ;
  val undefined = bind ((Success 1),(mdiv 0)) ;
  val two = bind((ret 1), (madd 1)) ;
  val two_by_one_plus_one = bind (two , (mmul 2)) ;

  println$ "zero = " + str zero ;
  println$ "1 / 0 = " + str undefined ;
  println$ "0 / 1 = " + str zero_over_one ;
  println$ "1 + 1 = " + str two ;
  println$ "2 * (1 + 1) = " + str (bind (bind((ret 1), (madd 1)) , (mmul 2))) ;
  println$ "INT_MAX - 1 = " + str (bind ((ret INT_MAX), (msub 1))) ;
  println$ "INT_MAX + 1 = " + str (bind ((ret INT_MAX), (madd 1))) ;
  println$ "INT_MIN - 1 = " + str (bind ((ret INT_MIN), (msub 1))) ;
  println$ "INT_MIN + 1 = " + str (bind ((ret INT_MIN), (madd 1))) ;

  println$ "--" ;

  //We do it again, this time using the "traditional" rshift-assign
  //syntax.

  syntax monad //Override the right shift assignment operator.
  {
    x[ssetunion_pri] := x[ssetunion_pri] ">>=" x[>ssetunion_pri] =># "`(ast_apply ,_sr (bind (,_1 ,_3)))";
  }
  open syntax monad;

  println$ "zero = " + str (ret 0) ;
  println$ "1 / 0 = " + str (ret 1 >>= mdiv 0) ;
  println$ "0 / 1 = " + str (ret 0 >>= mdiv 1) ;
  println$ "1 + 1 = " + str (ret 1 >>= madd 1) ;
  println$ "2 * (1 + 1) = " + str (ret 1 >>= madd 1 >>= mmul 2) ;
  println$ "INT_MAX = " + str (INT_MAX) ;
  println$ "INT_MAX - 1 = " + str (ret INT_MAX >>= msub 1) ;
  println$ "INT_MAX + 1 = " + str (ret INT_MAX >>= madd 1) ;
  println$ "INT_MIN = " + str (INT_MIN) ;
  println$ "INT_MIN - 1 = " + str (ret INT_MIN >>= msub 1) ;
  println$ "INT_MIN + 1 = " + str (ret INT_MIN >>= madd 1) ;
  println$ "2 * (INT_MAX/2) = " + str (ret INT_MAX >>= mdiv 2 >>= mmul 2 >>= madd 1) ; //The last one since we know INT_MAX is odd and that division will truncate.
  println$ "2 * (INT_MAX/2 + 1) = " + str (ret INT_MAX >>= mdiv 2 >>= madd 1 >>= mmul 2) ;

  //--
That last block using the <<= syntax produces (in part) the following output (the last two print statments have been truncated away -- the very last one produces an expected overflow).