From Infinite Type to Functor

dannypsnl

林子篆

Posted on December 12, 2019

From Infinite Type to Functor

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;
}
Enter fullscreen mode Exit fullscreen mode

Now we want to use Option[Foo] as Foo. In a normal use case, we have:

foo: Foo = Foo();
bar: Bar = foo.bar();
Enter fullscreen mode Exit fullscreen mode

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();
Enter fullscreen mode Exit fullscreen mode

It seems easy at first look, but consider this case:

foo: Option[Foo] = None;
bar: Bar = foo.bar();
Enter fullscreen mode Exit fullscreen mode

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
  }
}
Enter fullscreen mode Exit fullscreen mode

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());
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

For List: [a] we create:

fmap :: (a -> b) -> [a] -> [b]
-- yep, for list, fmap is map
fmap = map
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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)
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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;
      }
    }
  }
}
Enter fullscreen mode Exit fullscreen mode

To use it, we cannot keep the totally same code anymore:

foo: Option[Foo] = Some(Foo());
bar: Option[Bar] = foo.fmap[Bar](foo.bar);
Enter fullscreen mode Exit fullscreen mode

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.

💖 💪 🙅 🚩
dannypsnl
林子篆

Posted on December 12, 2019

Join Our Newsletter. No Spam, Only the good stuff.

Sign up to receive the latest update from our blog.

Related

From Infinite Type to Functor
plt From Infinite Type to Functor

December 12, 2019