Exploring Parametric polymorphism

Help
1

Parametric polymorphism, commonly referred to as “generics”, allow the user to create a procedure or data that can be written generically so it can handle values in the same manner.

Let’s do a little exercise trying to implement filter and map for slices. These are already implemented in the core at slice.filter and slice.mapper.

The following code is just an example of parametric polymorphism. A better implementation is available with slice.filter and slice.mapper.

The idea is to have a type definition with $ that can be used instead of a specific type like string. Normally is defined as $T, but can be named anything like $MyGenericType. Once is defined it can be used for any other param or declaration in the procedure scope. You can reuse a type in multiple places as a way of saying that they’re the same.

filter

Filters the enumerable, i.e. returns only those elements for which proc returns a truthy value.

filter :: proc(enumerable: []$T, callback: proc(element: T) -> bool) -> [dynamic]T {
	results : [dynamic]T
	for item in enumerable {
		if (callback(item)) {
			append(&results, item)
		}
	}
	return results
}

Usage

string slice

items := []string{"one", "two"}

filtered := filter(items, proc (element: string) -> bool {
    return element == "two"
})
// ["two"]
fmt.println(filtered)

int slice

filtered_int := filter([]int{1, 2, 3}, proc (element: int) -> bool {
		return element == 2
})

// [2]
fmt.println(filtered)

map (mapper)

Returns a slice where each element is the result of invoking proc on each corresponding element of enumerable.

mapper :: proc(enumerable: []$T, callback: proc(element: T) -> T) -> [dynamic]T {
	results : [dynamic]T
	for item in enumerable {
		append(&results, callback(item))
	}
	return results
}

Usage

string slice

items := []string{"one", "two"}

mapped := mapper(items, proc(element: string) -> string {
   if element == "one" {
      return "three"
   }

   return "four"
})

// ["three", "four"]
fmt.println(mapped)

int slice

items := []int{1, 2, 3}

mapped_int := mapper(items, proc(element: int) -> int {
   if element == 1 {
      return 2
   }

   return 4
})

// [2, 4, 4]
fmt.println(mapped_int)

Final Thoughts

  1. It is OK to make stuff just for the sake of it, to explore how stuff works. Just be careful not to overcomplicate things.

  2. Notice how we can pass proc as parameters. It’s the full declaration, but without its implementation.

callback: proc(element: T) -> bool

Thanks to @Barinzaya, @Tetralux and @Jesse for the guidance and corrections.

3 Likes
2

Corollary

Parametric polymorphism will disable require more steps to use automatic type inference in Odin for the procedure that use it.

// We have to pass the type in an explicit way
filtered := filter([]string{"one", "two"}, proc (element: string) -> bool {
    return element == "two"
})

// We can also store it in a typed variable
items := []string{"one", "two"}
filtered := filter(items, proc (element: string) -> bool {
    return element == "two"
})

// This way can be ambiguos using Parapoly
filtered := filter({"one", "two"}, proc (element: string) -> bool {
    return element == "two"
})

Another option is using Procedure Overloading to accept different param types in our procedures.

Example

package Project

import "core:fmt"

import "core:slice"
import "base:runtime"

filter_int :: proc(items : []int, callback: proc(element : int) -> bool, allocator:= context.allocator) -> (res: []int, err: runtime.Allocator_Error) #optional_allocator_error {
    return slice.filter(items, callback, allocator)
}

filter_string :: proc(items : []string, callback: proc(element : string) -> bool, allocator:= context.allocator) -> (res: []string, err: runtime.Allocator_Error) #optional_allocator_error {
    return slice.filter(items, callback, allocator)
}

filter :: proc {
    filter_int,
    filter_string,
    slice.filter,
}

main :: proc() {
    fmt.println(filter([]int{1, 2, 3}, proc( element: int) -> bool {
        return element == 2
    }))
}

When we have a procedure where multiple types can be assigned to a param in the same position in the signature. Ambiguos situations can arise and we have to resort to directly pass the type.

3

I wouldn’t say it disables inference, it’s just that inference in Odin is minimalistic.

Should you move []string{"one", "two"} into a variable and pass that instead of the literal it would know. The issue with the untyped version is that it is ambiguous, string literals are untyped, they can be either string or cstring and you specified neither.

Furthermore, {"one","two"} could be a slice, or a 2 element array… Your example is basically not well typed for inference to work.

1 Like
4

Thanks.
Now I understand better that type inference works best when there is just one possible type. For example in the procedure strings.concatenate it only accepts a string slice as first param.

When using parapoly you are dealing with multiple possibilities and that needs proper types in the params to reduce ambiguity.

5

Just semantics, but better thinking about it as “concrete type” rather than “possible type”. Here’s a tiny example without any parapoly:

	Point :: struct {
		x, y: f32,
	}
	p0: Point
	p0 = {1, 1}      // type of p0 is concrete, literal is infered
	p1 := Point{1,1} // type of p1 is infered, literel is concrete
	p2 := {1,1}      // type of p2 is infered, literal is infered --> type error

So, some notes on literals:

  • integer literals like 42 will default to int
  • floating point literals like 42.0 will default to f64
  • string literals like "hellope" will default to string
  • all other compound literals have to specify somewhere what type it’s supposed to be (procedure definition, variable declaration, or at the begining of the compound literal)
1 Like