Stream: beginners

Topic: is * top or bottom type?

Ron Panduwana (Feb 09 2023 at 07:17):

hello

so, the type of [] is List * means * denotes bottom type

Ron Panduwana (Feb 09 2023 at 07:19):

but also

isEmpty : List * -> Bool

The * is a wildcard type; a type that's compatible with any other type. List * is compatible with any type of List like List Str, List Bool, and so on.

Ron Panduwana (Feb 09 2023 at 07:19):

so that means * is also the top type?

Folkert de Vries (Feb 09 2023 at 12:02):

let's see.

• a top type would be a terminal object, so it has arrows from any object (type) into it. Usually we'd pick the empty record {} for this type
• a bottom type is an initial object; for any object (type), there is an arrow from the bottom type to that type. This type is variously called Void (haskell) or Never (elm, rust). In roc it is written as the empty tag union []

Folkert de Vries (Feb 09 2023 at 12:02):

the * is a forall-quantified type variable. The signature is really isEmpty : forall a. List a -> Bool

Folkert de Vries (Feb 09 2023 at 12:03):

within the implementation of isEmpty, that means you have no concrete information about what type of elements are in the list (and to implement that function, you don't care)

Ron Panduwana (Feb 09 2023 at 12:05):

then the type of [] should be List [], not List *, no?

Folkert de Vries (Feb 09 2023 at 12:05):

but certainly, we cannot construct (within the body) a function forall b. b -> a. We don't have any value of type a that we can make out of thin air

Folkert de Vries (Feb 09 2023 at 12:06):

likewise, we cannot create forall b. a -> b, because we can also not create a value of any type b out of thin air

Folkert de Vries (Feb 09 2023 at 12:06):

hence a forall-quantified variable is neither top nor bottom

Folkert de Vries (Feb 09 2023 at 12:06):

well, that is valid, but not very helpful in practice

Folkert de Vries (Feb 09 2023 at 12:07):

say I want to do List.append [] 42

Folkert de Vries (Feb 09 2023 at 12:07):

then if the empty list had type List [], we'd get a type error here

Folkert de Vries (Feb 09 2023 at 12:07):

because 42 does not have type []

Folkert de Vries (Feb 09 2023 at 12:08):

so in type inference, the type of the list is left variable

Folkert de Vries (Feb 09 2023 at 12:08):

however, when we go to monomorphize, we have to pick an actual concrete type in that position

Folkert de Vries (Feb 09 2023 at 12:08):

and there our choice is free. Any type will do, that is what the signature says!

Folkert de Vries (Feb 09 2023 at 12:09):

in practice picking {} is usually the most convenient choice

Ron Panduwana (Feb 09 2023 at 12:10):

can it work with List.append 42 []?

Folkert de Vries (Feb 09 2023 at 12:11):

can what work with List.append [] 42 (in roc, the data structure is usually the first argument)?

Ron Panduwana (Feb 09 2023 at 12:13):

ah I see, ok

Ron Panduwana (Feb 09 2023 at 12:17):

I guess, that the * has different meaning on the left vs. on the right, is what makes it confusing here.

if we are to e.g. make * to Anything on the left, and Nothing on the right, it would be much clearer.

Ron Panduwana (Feb 09 2023 at 12:18):

the confusion is even in the tutorial

so we might think the type of List.reverse would be reverse : List * -> List *. However, remember that we also saw that the type of the empty list is List *? List * -> List * is actually the type of a function that always returns empty lists! That's not what we want.

Ron Panduwana (Feb 09 2023 at 12:19):

e.g. imagine if it's List Anything -> List Nothing, much clearer

Ayaz Hafiz (Feb 09 2023 at 14:14):

Probably that section in the tutorial should be reworded. List * -> List * is a function that accepts lists of any type (easy) and produces a list of any type you want (impossible to satisfy, except by producing the empty list).

Roc doesn’t have a hierarchy of types, so there aren’t really top/bottom types - maybe we can find a way to make thinking about them in that way more meaningful though.

Richard Feldman (Feb 09 2023 at 22:14):

if it helps, List * -> List * is syntax sugar for List a -> List b

Richard Feldman (Feb 09 2023 at 22:14):

because in the general case, * is syntax sugar for "a type variable whose name appears nowhere else in this type annotation"

Kevin Gillette (Feb 16 2023 at 02:26):

Richard Feldman said:

because in the general case, * is syntax sugar for "a type variable whose name appears nowhere else in this type annotation"

That'd be useful wording to have in tutorials

Luke Boswell (Feb 16 2023 at 05:42):

Thanks for pointing that out @Kevin Gillette I'll make an issue and add in my next go at the tutorial.

Last updated: Jul 06 2025 at 12:14 UTC