林子篆
Posted on December 12, 2019
At infinite type I mention a way(recursive abstract data type) to make we use Option[T]
just like T
. However, such modeling is not enough. Consider the following example(with the same pseudo syntax takes from infinite type):
class Foo {
bar(): Bar;
}
Now we want to use Option[Foo]
as Foo
. In a normal use case, we have:
foo: Foo = Foo();
bar: Bar = foo.bar();
Once we put Foo
into the box, it became:
foo: Option[Foo] = Some(Foo());
// we say use Option[Foo] as Foo, so foo.bar should be supported just like it's existed under Option[Foo]
bar: Bar = foo.bar();
It seems easy at first look, but consider this case:
foo: Option[Foo] = None;
bar: Bar = foo.bar();
What should we do? Terminate program is definitely not what we want, our purpose is reducing the unneeded check(let's say before we surely use the data to show something to UI is not need to check), not create a fragile software. And if we want foo.bar()
crash the program at here we even don't have to model Option
, just introduce bottom type just like the language that allows null object. So what is our purpose? Is to make foo.bar()
automatically returns Option[Bar]
.
Now, let's think about how to make it. Consider this:
class Foo {
bar(): Bar;
}
class Option[Foo] <: Foo {
bar(): Bar {
// implementation
}
}
This model is bad, first, it cannot let Bar
became Option[Bar]
; second, it causes an interesting problem: Option[Foo]
is a subtype of Foo
which means the following code is valid:
foo: Foo = Some(Foo());
However, how do we sure Foo
is Option[Foo]
or Foo
now? In fact, now we make an infinite definition of the type which has a size(such type takes real memory to store), which means we cannot make this kind of type. This is the reason why we have a function called fmap
in Haskell!
Take a look at the type of fmap
:
fmap :: (a -> b) -> f a -> fb
For the Maybe
type, we create:
fmap :: (a -> b) -> Maybe a -> Maybe b
fmap f (Just a) = Just (f a)
-- We can do nothing with Nothing
fmap _ Nothing = Nothing
For List: [a]
we create:
fmap :: (a -> b) -> [a] -> [b]
-- yep, for list, fmap is map
fmap = map
Ok, so we create such a program for all the box type(such type provide common wrapping for others type)? No!
In Haskell, it actually defines a class
(Haskell class
is very different with Java one) for this situation, called Functor
:
class Functor f where
fmap :: (a -> b) -> f a -> f b
instance Functor [] where
fmap = map
instance Functor Maybe where
fmap f (Just a) = Just (f a)
fmap _ Nothing = Nothing
We also can create instance Functor (a, b)
, like:
-- `(,) a b` is `(a, b)`, you can find Haskell treats binary operator as a function takes two parameters everywhere(if I'm wrong, tell me)
instance Functor ((,) a) where
fmap f (x, y) = (x, f y)
fmap (+1) (2, 5)
-- (2, 6)
fmap (+1) (3, 5)
-- (3, 6)
fmap (+2) (3, 5)
-- (3, 7)
In this case, f a
<=> f
is (,) a
, a
is b
.
Now, let's make a mind blow up. I say that binary operator in Haskell is all modeling like a function, so a -> b
is (->) a b
, in fact, I thought people who familiar with Lisp would not feel it weird.
According to (a -> b) -> f a -> f b
, first, to make symbol would not conflict, we use: (b -> c) -> f b -> f c
. Then use (->) a
to replace f
: (b -> c) -> ((->) a b) -> ((->) a c)
, then normalize it: (b -> c) -> (a -> b) -> (a -> c)
. Those knows Haskell now should jump and say: Compose! Yes, let's see the definition:
instance Functor ((->) a) where
fmap f fa = f . fa
I hope you have enough fun with Functor X).
Let's back to the problem: How to use Option[Foo]
as Foo
?
trait Functor[a] {
// let's assuming we have a syntax like this which would require `self` is a type that takes one type parameter and export the type binding to `f` and `a`(and `a` would cause a unification here, since `Functor` have one also, so `a` already bound, `self` has to satisfy it).
f[a] = self;
fmap[b](self, (a): b): f[b];
}
class Option[T] <: Functor[T] {
fmap[b](self: Option[T], func: (T): b): Option[b] {
match self {
Some(v) => {
return func(v);
}
None => {
return None;
}
}
}
}
To use it, we cannot keep the totally same code anymore:
foo: Option[Foo] = Some(Foo());
bar: Option[Bar] = foo.fmap[Bar](foo.bar);
Now we make an object-syntax-oriented version's Functor. You can see the definition is a little bit... ok, very hard to read. But if we really want such extendability(unify box types), then probably is worth it. I haven't mentioned category theory, Applicative(finally!) and other things in Haskell or other languages. Hopefully, I can complete them in the future, and in the end thanks for your read.
Posted on December 12, 2019
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.