What are some examples of inductive data types? How do inductive types differ from their non-inductive counterparts? What can they do that is impossible otherwise? When should they not be used?
Code snippets in any language would be greatly appreciated.
An inductive data-type is simply one that is defined in terms of itself. A simple example would be a list, which we can define as:
type List<'a> =
| Empty
| List of 'a * List<'a>
So, a list is either Empty, or it has a head node and a tail, which is itself a list. This allows us to define a list in a very simple way without having any other built-in data structures (except the tuple type, but we could do it without that, it just simplifies the example).
We can then create a simple function to add to the list, such as:
let add item = function
| Empty -> List (item, Empty)
| List (head, tail) -> List (item, (List (head, tail)))
This takes an item and a list as input, and returns a new list. If the input list is empty, it returns a list with the item as the head and the Empty list as the tail. If the list is not empty, it returns a new list with the item as the head, and the original list as the tail.
We can use this function to build up a list of any type. For integers, this would look something like:
Empty
|> add 1
|> add 2
|> add 3
Where |> is an operator that takes the preceding value and passes it as the last parameter to the next function. This gives us the list:
List<int> = List (3,List (2,List (1,Empty)))
As for when they should not be used, there are some scenarios where a recursively defined data structure can incur a performance or memory penalty relative to, for example, an array of mutable state. This is often due to the underlying system implementation being based on structures that are more closely mirrored by arrays. However, depending on the use case, maintaining an array of mutable state may incur other penalties, such as lock-management in a concurrent application. If you're interested in a more detailed analysis, I highly recommend the book Purely Functional Data Structures.