Algebraic Data Type
In this blog, we will talk about Algebraic Data Type
in Scala and try to find out why we need it.
Question
Say we have a function like this
We know it’s not a pure function, because it throw exception when y equals 0.
To use Functional Programming in our program, we need to make it to be pure.
How should we do?
Solution
According to the definition of pure function, to make a function to be pure, we need to eliminate the Side-Effect
.
But we don’t want to lose the effect given by the exception, So we need to make the effect of exception returned by the return-expression
.
Then the function should look like this
def div(x: Double, y: Double): Double = {
if(y == 0)
new Exception("/ by zero")
else
x/y
}
Unfortunately, this code can’t be compiled, because the type of return-expression
is Any
which can’t be assigned to the expected type Double
.
We definitely can change the return type to be Any
def div(x: Double, y: Double): Any = {
if(y == 0)
new Exception("/ by zero")
else
x/y
}
it can be compiled, but the type checking is too weak, compiler can’t help us if we make mistake like this
def div(x: Double, y: Double): Any = {
if(y == 0)
new Exception("/ by zero")
else
(x/y).toString
}
All the existing consumers of div
use its result as Double
, but we return String
here and it can be compiled, then we can only find the bug in running time.
So we have two requirements here
- The function should be able to return two different effects which have different types.
- Keep the type checking strong.
To achieve them, we need to find out the nearest parent type of these effects and set it to be the return type of function.
Both Exception
and Double
are primitive types, their common parent type is Any
, which make the type checking weak then can’t be used.
What should we do now?
Now that we can’t use the primitive type, how about use another custom type to wrap them? then we can give the custom types an common parent type. Let’s try.
Firstly, wrap all the effects we want to return with custom type
case class DivResult(v: Double)
case class ExceptionResult(e: Exception)
And give them a parent type
trait Result
case class DivResult(v: Double) extends Result
case class ExceptionResult(e: Exception) extends Result
Then the div
function can be refactored like this
def div(x: Double, y: Double): Result = {
if(y == 0)
ExceptionResult(new Exception("/ by zero"))
else
DivResult(x/y)
}
It works! we can return Exception
and Double
together and use the custom type to make the type checking still strong.
And if we want to return more information for one effect, we can just modify the corresponding custom type.
For example, if we want to return the input parameter together with Exception
, we can refine the custom types like this
trait Result
case class DivResult(v: Double) extends Result
case class ExceptionResult(e: Exception, parameter: (Double, Double)) extends Result
def div(x: Double, y: Double): Result = {
if(y == 0)
ExceptionResult(new Exception("/ by zero"), (x, y))
else
DivResult(x/y)
}
Refactor
We know we can return more information for given effect by refining the custom type, but how do you know what’s the future requirements?
Is there what we can do to make the custom type more generic?
Now that we don’t know what information should be returned for given effect and we definitely know which effect should be returned for given scenario, how about we just leave the information of effect to be generic?
Let’s see if we can make it
trait Result[E, A]
case class DivResult[E, A](v: A) extends Result[E, A]
case class ExceptionResult[E, A](e: E) extends Result[E, A]
Then we can refactor the div
function more flexiable
def div(x: Double, y: Double): Result[Exception, Double] = {
if(y == 0)
ExceptionResult[Exception, Double](new Exception("/ by zero"))
else
DivResult[Exception, Double](x/y)
}
def div(x: Double, y: Double): Result[(Exception, (Double, Double)), Double] = {
if(y == 0)
ExceptionResult[(Exception, (Double, Double)), Double]((new Exception("/ by zero"), (x, y)))
else
DivResult[(Exception, (Double, Double)), Double](x/y)
}
We know sqrt
have the same type of effects with div
, then we can also refine it
def sqrt(x: Double): Result[Exception, Double] = {
if(x < 0)
ExceptionResult[Exception, Double](new Exception("sqrt by negative"))
else
DivResult[Exception, Double](Math.sqrt(x))
}
Hmm, it can be compiled, but our function is sqrt
, the return type is DivResult
, it doesn’t make sense.
We need to make the name of custom type more generic. Now that we only return one effect at the same time and each effect only use one type parameter, let’s refine the custom type like this
trait Either[E, A]
case class Right[E, A](v: A) extends Either[E, A]
case class Left[E, A](e: E) extends Either[E, A]
Then we can refine div
and sqrt
like this
def div(x: Double, y: Double): Either[Exception, Double] = {
if(y == 0)
Left[Exception, Double](new Exception("/ by zero"))
else
Right[Exception, Double](x/y)
}
def sqrt(x: Double): Either[Exception, Double] = {
if(x < 0)
Left[Exception, Double](new Exception("sqrt by negative"))
else
Right[Exception, Double](Math.sqrt(x))
}
Bingo! This is Either
monad, we will talk about it more in the future.
Summary
-
To make all the effects of function retuned by
return-expression
and make the type checking strong, we create custom type to wrap primitive typestrait Result case class DivResult(v: Double) extends Result case class ExceptionResult(e: Exception) extends Result
-
To make the custom type more generic, we use type parameter to refine it
trait Result[E, A] case class DivResult[E, A](v: A) extends Result[E, A] case class ExceptionResult[E, A](e: E) extends Result[E, A]
-
To let the name of custom type make more sense, we refine its name
trait Either[E, A] case class Right[E, A](v: A) extends Either[E, A] case class Left[E, A](e: E) extends Either[E, A]
Ok, this is Algebraic Data Type
- For the signle effect
Right
orLeft
, we call it asProduct Type
which contains the detailed information of effect. - For
Either
Right
andLeft
, we call the inheritance relationship between them asSum Type
which can be used to unify the type of effect. - We call
Product Type
andSum Type
together asAlgebraic Data Type
Let’s recall how to make a function to be pure
- Find out what effect the function send to outside
- The result of division when y is not zero
- Exception when y is zero
-
For each effect, create a corresponding
Product Type
for itcase class DivResult(v: Double) case class ExceptionResult(e: Exception)
-
To unify the type of differnt effects, create
Sum Type
to give the effects a common parent typetrait Result case class DivResult(v: Double) extends Result case class ExceptionResult(e: Exception) extends Result
-
Refactor the function to use the
Algebraic Data Type
as return typedef div(x: Double, y: Double): Result = { if(y == 0) ExceptionResult(new Exception("/ by zero")) else DivResult(x/y) }
Using this procedure, we can get lots of generic Algebraic Data Type
, such as Option, Either, IO, Reader, Writer, State etc.
We will talk about which type of function can use them to be pure laterly.
Comments