Polymorphism

fble-0.5 (2025-07-13,fble-0.4-212-ga8f8ad0f)

This tutorial does a deep dive into polymorphism in fble. By the end of this tutorial, you'll be fully versed in section 7 of the fble language spec on polymorphism.

Basics

Many statically typed languages have support of one form or another for defining data types that work with different types. For example, you want to have a generic list type that can be made to work for lists of integers, lists of characters, lists of strings, and so on. C++ has templates for this purpose, Java has generics and Haskell has type parameters.

The fble language has something called a polymorphic value, or poly for short. Polys are a class of types in fble in addition to structs, unions, and functions which you already know about. A poly is an fble value parameterized by a type.

As an example, consider the Maybe@ type.

The Maybe Type

In languages like Java and C, which have pointers, it's common to use NULL as a special value to distinguish between valid pointers and invalid pointers. Some languages have an option type for describing a value that may be invalid. In Haskell and fble, that type is called "Maybe".

For example, here is how we could define an integer value that may be invalid: 

@ MaybeInt@ = +(Int@ just, Unit@ nothing);

MaybeInt@ NothingInt = MaybeInt@(nothing: Unit);

(Int@) { MaybeInt@; } JustInt = (Int@ x) {
  MaybeInt@(just: x);
};

For example, you could implement a div function that returns the result of division, or NothingInt in case of divide by zero. Or you could implement a function to parse an integer from a string that returns NothingInt if the string doesn't have the required syntax.

The same structure is useful for other data types. For example, we may want to distinguish between valid and invalid strings: 

@ MaybeString@ = +(String@ just, Unit@ nothing);

MaybeString@ NothingString = MaybeString@(nothing: Unit);

(String@) { MaybeString@; } JustString = (String@ x) {
  MaybeString@(just: x);
};

Now we could write a GetLine function, for example, that gets the next line in a file or NothingString if the end of the file has been reached.

The definitions for MaybeInt@ and MaybeString@ are identical aside from replacing "Int" with "String" everywhere. With polymorphism, we can define a single Maybe@ type that can be reused to distinguish between valid and invalid values of any other type.

The Polymorphic Maybe@ Type

Here's how we can define a polymorphic Maybe@ type: 

<@>@ Maybe@ = <@ T@> { +(T@ just, Unit@ nothing); };

Maybe@ Nothing = <@ T@> {
  Maybe@<T@>(nothing: Unit);
};

<@ T@>(T@) { Maybe@<T@>; } Just = <@ T@>(T@ x) {
  Maybe@<T@>(just: x);
};

A poly value is described using the syntax <@ T@> { ... }. Here, T@ is a type variable. For ... you put any kind of fble value, and that value is allowed to depend on the abstract type T@.

There is only one operation you can perform on a poly value: You can provide a concrete type, resulting in the value of the poly with the type variable T@ replaced with its concrete type.

For example, the first poly value we see in the definition of Maybe@, which is a poly of a type value: 

<@ T@> { +(T@ just, Unit@ nothing); }

If we write Maybe@<Int@>, we'll get back the type value: 

+(Int@ just, Unit@ nothing);

If we write Maybe@<String@>, we'll get back the type value: 

+(String@ just, Unit@ nothing);

And so on.

The next place we see a poly value is in the definition of Nothing, which is a poly of a union value: 

<@ T@> {
  Maybe@<T@>(nothing: Unit);
};

If we write Nothing<Int@>, we get back the union value: 

Maybe@<Int@>(nothing: Unit)

If we write Nothing<String@>, we get back the union value: 

Maybe@<String@>(nothing: Unit)

Finally, Just is a poly of a function value. If we write Just<Int@>, we get back the function value: 

(Int@ x) {
  Maybe@<Int@>(just: x);
};

The Type of a Poly Value

As with other kinds of values, poly values have types. The type of a poly is the poly of the type.

Take Nothing for example. The poly is: 

<@ T@> {
  Maybe@<T@>(nothing: Unit);
};

This is a poly of a union value. The type of this poly is a poly of a union type. More specifically, the type is: 

<@ T@> { Maybe@<T@>; }

Which is the same as Maybe@.

In general: 

@<<@ T@> { ... }> = <@ T@> { @<...> };

The Kind of a Poly

So far we have been introduced to two kinds of values. Normal values, including struct values, union values, and function values, have the kind %. Type values have the kind @.

A polymorphic value has what is called a polymorphic kind, which includes the kind of the type parameter and the kind of the value. For example, the kind of Nothing is <@>%, which means it has a type parameter of kind @ and produces a value of kind %. The kind of Maybe@ is <@>@, because it has a type parameter of kind @ and produces a type value of kind @.

The following shows how you might import different kinds of values: 

% True = /Core/Bool%.True;
@ Char@ = /Core/Char%.Char@;
<@>@ List@ = /Core/List%.List@;
<@>% Concat = /Core/List%.Concat;

The kind of True is % because it is a normal value. The kind of Char@ is @ because it is a type. The type of List@ is <@>@ because it a polymoprhic type value, and the type of Concat is <@>%, because it is a polymorphic normal value.

Recursive Polymorphic Types

You can define recursive polymorphic types in fble using recursive variable declarations, but with a special caveat. In order to keep the type system reasonable, you cannot do a polymorphic application of a type you are defining in its own definition. For example, the following natural way to write a recursive polymorphic list type is not allowed: 

# Not allowed!
<@>@ List@ = <@ T@> { +(*(T@ head, List@<T@> tail) cons, Unit@ nil); };

The compiler will give you an error saying List@ isn't polymorphic. When specifying the kind of a variable instead of the type of the variable in the variable definition, the variable is treated as non-polymorphic in its own definition. To work around this, you need to define the list type in a slightly different way: 

<@>@ List@ = <@ T@> {
  @ L@ = +(*(T@ head, L@ tail) cons, Unit@ nil);
  L@;
};

This describes the same type, but the recursive part is done inside the body of the poly. A way to think about it is that recursive polymorphic types can be implemented in fble by writing them as polymorphic recursive types.

Recursive polymorphic Functions

You can implement recursive polymorphic functions just fine, but you have to provide an explicit type in the definition of the function. You can't specify a kind and have the type inferred. So, for example, the following works to define a function Last that returns the last element in a list: 

<@ T@>(List@<T@>) { T@; } Last = <@ T@>(List@<T@> list) {
  list.cons.tail.?(nil: list.cons.head);
  Last<T@>(list.cons.tail);
};

If you tried to write that without an explicit function type, you would get an error: 

<@>% Last = <@ T@>(List@<T@> list) {
  list.cons.tail.?(nil: list.cons.head);
  # Error: Can't do Last<T@> in definition of Last.
  Last<T@>(list.cons.tail);
};

Mutually Recursive Polymorphic Types

You can define mutually recursive polymorphic types. It's slightly awkward, but doable. For example, if you wanted to define two types, List@ for lists and ListP@ for non-empty lists in terms of each other, you can either duplicate the definition, or share them.

Here's how duplicated definitions would look: 

<@>@ List@ = <@ T@> {
  @ L@ = +(P@ cons, Unit@ nil),
  @ P@ = *(T@ head, L@ tail);
  L@;
};

<@>@ ListP@ = <@ T@> {
  @ L@ = +(P@ cons, Unit@ nil),
  @ P@ = *(T@ head, L@ tail);
  P@;
};

Here's how you could reuse the definitions instead of duplicating them: 

<@>% Types = <@ T@> {
  @ L@ = +(P@ cons, Unit@ nil),
  @ P@ = *(T@ head, L@ tail);
  @(L@, P@);
};

<@>@ List@ = <@ T@> { Types<T@>.L@; };
<@>@ ListP@ = <@ T@> { Types<T@>.P@; };

Interfaces

Some languages have the concept of an interface. You can write a function that operates on any type, as long as that type implements a particular interface. An interface can be implemented in fble as a polymorphic collection of functions parameterized by some type T@.

For example, in another language you might define an Eq interface that types implement if values of those types can be compared. You could write a list Contains function that operates on objects with the Eq interface to do the equality comparison.

In fble, you pass the right implementation of Eq directly as an argument to Contains. It would look something like this: 

<@>@ Eq@ = <@ T@>(T@, T@) { Bool@ };

<@ T@>(Eq@<T@>, List@<T@>, T@) { Bool@; }
Contains = <@ T@>(Eq@<T@> eq, List@<T@> l, T@ x) {
  l.?(nil: False);
  eq(l.cons.head, x).?(true: True);
  Contains<T@>(eq, l.cons.tail, x);
};

In this case, Eq@ is like an interface for the type T@ that the Contains function requires to work. The caller is responsible for providing the implementation of Eq@.

Poly of a Poly

It's possible for the body of a polymorphic value to itself be a polymorphic value. This is useful if you want to have multiple type parameters. For example, imagine you want to define a generic Pair@ type that has a different type for the first and second field: 

<@><@>@ Pair@ = <@ A@> { <@ B@> { *(A@ first, B@ second); }; };

<@ A@> { <@ B@> { (Pair@<A@><B@>) { A@; }; }; }
First = <@ A@> { <@ B@> { (Pair@<A@><B@> pair) { pair.first; }; }; }

Here's an example of how to make use of the Pair@ type: 

Pair@<Int@><Bool@> x = Pair@<Int@><Bool@>(42, True);
Int@ value = First<Int@><Bool@>(x);

In fble, nested polymorphic values like this are equivalent to multi-argument polymorphic values, and you can use more compact syntax to express the same thing: 

<@, @>@ Pair@ = <@ A@, @ B@> { *(A@ first, B@ second); };

<@ A@, @ B@>(Pair@<A@, B@>) { A@; };
First = <@ A@, @ B@>(Pair@<A@, B@> pair) { pair.first; };

Pair@<Int@, Bool@> x = Pair@<Int@, Bool@>(42, True);
Int@ value = First<Int@, Bool@>(x);

In this case the kind of Pair@ can be written either as <@><@>@ or as <@,@>@. And the kind of First can be written either as <@><@>% or as <@, @>%, indicating that it takes two type arguments.

This means you can do partial application of multi-argument poly values. For example, you could write Pair@<Int@> to refer to the polymorphic type <@ A@> { Pair@<Int@, A@>; }.

Higher Order Polys

So far we've only shown type parameters of kind @. It's not legal in fble to use a type parameter of kind %, because that % doesn't represent a type. But you could specify a type parameter of kind <@>@ if you want. This would be a higher order polymorphic value.

The classic example of a higher order polynomial value is the Monad@ type, which describes an interface that container types such as List@ can support: 

<<@>@>@ Monad@ = <<@>@ M@> {
  *(
    <@ A@>(A@) { M@<A@>; } return,
    <@ A@>(M@<A@>)<@ B@>((A@) { M@<B@>; }) { M@<B@>; } do
  );
};

In this case the type parameter M@ has kind <@>@, so we can say things like M@<A@> and M@<B@> in the body of the poly. Even though we don't know what type value will be passed for M@, the compiler will make sure it is only called with a polymorphic type value of kind <@>@.

We'll talk more about monads in the next tutorial. For now, the important takeaway is that you specify the kind of the type variable in a polymorphic value. You can make use of this in the body of the polymorphic value, and the compiler will make sure you only instantiate the polymorphic value with an argument of appropriate kind.

For example, this would be okay: 

Monad@<List@> ListMonad = ...;

But this would give you a type error: 

Monad@<Int@> IntMonad = ...;

Because Int@ has kind @ when <@>@ is required.

Polys are Values

Polymorphic values are values. That means you can use them wherever you could use any other value in fble. You can have variables of polymorphic values, you can pass polymorphic values to and from functions, and you can have fields of structs and unions that are polymorphic values.

This is a bit subtle. You can pass around a polymorphic value in a struct. Whoever has access to that struct can instantiate that polymorphic value multiple times with multiple different type arguments.

Another example: in theory you could have a polymorphic function value that returns a polymorphic function. This isn't as far fetched as you might think at first. The syntax for defining poly values and function values can be interleaved to make this easy to write. For example, here's the type of a map lookup function: 

<@ K@>((K@, K@) { Bool@; })<@ V@>(Map@<K@, V@>, K@) { Maybe@<V@>; } Lookup = ...

To use the Lookup function, you provide the type K@ of key elements in the map, a comparison operator of type (K@, K@) { Bool@; } used to define the element ordering, the type V@ of value you want to look up, the map of type Map@<K@, V@> to do the lookup in, and the value of the key to look up.

If you write the Lookup function this way, it's convenient to define different variations of Lookup depending on your key type, your comparison operator, and your value type. For example: 

<@>% LookupByName = Lookup<String@>(StringCompare);

Map@<String@, Int@> ids = ...;
Map@<String@, Grade@> grades = ...;

(Map@<String@, Int@>, String@) { Int@; } LookupId = LookupByName<Int@>;
(Map@<String@, Grade@>, String@) { Grade@; } LookupGrade = LookupByName<Grade@>;

Int@ my_id = LookupId(ids, Str|Richard);
Grade@ my_grade = LookupGrade(grades, Str|Richard);

Type Inference

It's fairly common to define and use polymorphic functions. For example, we defined the Just function earlier to define a valid Maybe value. The normal way to use a polymorphic function is to supply the type argument to get the function value and then apply the arguments to the function value: 

Maybe@<Int@> my_int = Just<Int@>(Int|42);

In many situations, the fble compiler can automatically infer the value of the type parameter to use with the poly. In this case, the compiler knows the type of Int|42 is Int@ and that Just is a polymorphic function with type parameter T@ and argument of type T@. Given that information, the compiler can infer that the only value for T@ that makes sense here is Int@. If the compiler can infer the type parameters of a polymorphic function when you do a function application, you can leave out the explicit value for the type parameter; the compiler will insert it for you automatically: 

Maybe@<Int@> my_int = Just(Int|42);

The fble type system is based around the idea that you can determine the type of an expression solely based on the types of variables in scope and the expression itself. The type of an expression cannot depend on how that expression is used. Because of this, the compiler is not able to infer the type parameter to Nothing@, because it would have to know how the expression is being used to know what type to pass.

For the most part type inference is just a convenience. Where type inference becomes crucially important is when using function bind for monadic computations. We'll discuss function bind and monadic computations in the next tutorial.

Where Type Inference Happens

There are a few specific instances where the compiler will try to automatically infer and apply type arguments to polys.

When Type Inference Fails

Type inference will not always succeed. This can happen because there is not enough information for the compiler to infer the type, or because the compiler isn't smart enough yet to be able to infer the types.

For example: 

List@<Int@> empty = List[];   # Cannot infer type!

In this case the compiler cannot tell that List[] should produce an integer list as opposed to any other kind of list. In this case you should get an error message from the compiler indicating that it couldn't tell what type to use for T@ in the list expression.

In some cases the compiler is simply not smart enough to infer the type. When in doubt, you can always provide an explicit type parameter if the compiler is having trouble with type inference.

Type Inference of Nested Polys

Consider a polymorphic function with two type parameters, such as a Map lookup function where you need to provide a key type and a value type.

You may be tempted to write this with both type parameters in front: 

<@ K@, @ V@>((K@, K@) { Bool@; }, Map@<K@, V@>, K@) { Maybe@<V@>; } Lookup = ...

The problem with this approach is it doesn't lend well to type inference of the second type parameter V@. Multi-argument functions are treated as single argument functions that return functions and type inference only takes effect one argument at a time. That means type inference cannot infer the type of V@ when calling the Lookup function; V@ doesn't appear anywhere in the first argument of Lookup.

A better way to define the Lookup function is to move the V@ type parameter to just before the argument where it is first used: 

<@ K@>((K@, K@) { Bool@; })<@ V@>(Map@<K@, V@>, K@) { Maybe@<V@>; } Lookup = ...

The type of the Lookup function is slightly more awkward to write this way, but it provides better flexibility for users and means that type inference can infer the types of K@ and V@ no problem. For example: 

Maybe@<String@> result = Lookup(IntLt, map, Int|4);

The sequence of steps to do type inference on this, starting with viewing it using single argument functions, is: 

Lookup(IntLt) (map) (Int|4)
Lookup<Int@>(IntLt) (map) (Int|4)
Lookup<Int@>(IntLt) <String@>(map) (Int|4);

Polymorphism in the Language Specification

You now know everything there is to know about polymorphism in fble. To reinforce this, read over section 6 of the fble language specification. Everything there should be familiar to you now.

Next Steps

Head over to the Bind tutorial to learn about function bind syntax and monadic computations.