Power extreme: Algebraic data types and pattern matching

Computer programs may be simplistically viewed as an interplay between objects of given types based on operations defined on the types, and conforming to the laws on those types. The types may be as fundamental as an integer or as complex as an abstract syntax tree in a compiler. Compound types are defined using other types, or recursively too, using an algebra. Hence the name algebraic data types

The two major operations when working with algebraic data type are construction and deconstruction. Construction is achieved simply through constructors! Deconstruction is achieved by what is generally referred to as pattern matching - a powerful technique that may be applied for all kinds of processing of an object of an algebraic type. A talk on algebraic types is incomplete without dealing with the concept pattern matching.

This session proposes to take the audience through the implementation of a simple LISP interpreter in Swift to help appreciate the theory around Algebraic Data Types (ADTs) and pattern matching - both of which are language features in Swift. In Swift parlance, ADTs are referred to as tuples (product types) and enums (sum types).

The session is targeted to enable the audience completely appreciate the Wikipedia definition of an ADT: "A general algebraic data type is  possibly a recursive sum type of product types". The objective is to show that thinking in terms of algebraic types is a crucial part of the larger paradigm of functional thinking.


Outline/Structure of the Talk

Introduction to the algebra of types, sum types, product types - 5 min

Algebraic types in Swift - enums - 5 min

Lisp interpreter example: The encapsulating enum and its construction - 10 min

Pattern matching - general and Swifty introduction - 5 min

Lisp interpreter example: Processing/interpreting the abstracted syntax using pattern matching - 10 min

 Algebraic types and pattern matching as a part of Functional Thinking - 5 min

Q&A - 5 min

Learning Outcome

1. Learn about algebraic types - from the math definition to their application in everyday FP

2. Appreciate the power of algebraic types in general, Swift enums in particular

3. Appreciate the power of pattern matching - in general and in the context of Swift

4. Understand why algebraic types and pattern matching are an important part of functional thinking


Target Audience

Beginner Functional Programmers in any language, Swift programmers

Prerequisites for Attendees




schedule Submitted 5 years ago