Dependent type

Dependent types depend on values, not just types

Dependent types are a unique feature of type theory that allows the definition of types to be influenced by values. This characteristic enables a more precise and rigorous approach to programming, as it can encode logical quantifiers like "for all" and "there exists" directly into the type system.

Example

A function in a dependent type system might take an integer as an argument and return an array whose length is determined by that integer. For example, a function could be defined as `array : Int -> [Int]`, where `array n` returns an array of length `n`.

Remember this

Dependent types reduce bugs by allowing programmers to assign types that further constrain the set of possible implementations, leading to more reliable and maintainable code.

Text adapted from Wikipedia, licensed under CC BY-SA 4.0.

Related concepts

Curry–Howard correspondence

Proofs are programs, types are propositions

Monad (functional programming)

Monads are a type constructor with two operations: return and bind

Product type

Product types combine two types into a single structure

parametric polymorphism does: a function works for any type T without knowing what T is

Parametric polymorphism allows code to work with any type T

Yoneda lemma

The Yoneda lemma embeds a locally small category into a functor category

Greedy vs dynamic programming: greedy makes locally optimal choices, DP considers all subproblems

Greedy: locally optimal choices; DP: considers all subproblems

Swipe through 100 ML concepts daily

Open Pocket Polymath