I was inspired to make this as a resource for gathering helpful tools and explanations for describing an interesting way to write software. By utilizing concepts coming from a combination of abstract algebra and lambda calculus, I believe it is possible to construct abstractions and data types that can lead to software that is easy to maintain, easy to modify, and easy for new talent to reason about.
This youtube video was great to get things going. It introduces concepts of abstract algebra and the presenter's application to writing animation library in Swift.
This playlist is an awesome introduction for beginners who are not familiar with abstract algebra to get familiar with concepts such as groups, rings, and isomorphism.
This textbook goes into examples of applied abstract algebra, most importantly abstract data types and their implications on software design.
This ebook which was the first material I read regarding the subject but found it too difficult as an introduction into the subject. All the earlier listed material were very helpful in helping me connect the dots for this book.
This book "Algebra of of Programming" by Richard Bird and Oege de Moor online book
A great introduction course that I personally completed in a week as an experienced developer
Haskell book list (Haskell is very pure in its approach to functional programming):
If/Switch/Pattern-Matching Statements
List as a fundamental data structure to solve problems along with list operations
Anonymous Functions/Functors
High Order Functions
Function Composition
Recursion
Mapping
Algebraric datataypes are types that combine other types either as records ('products') data Pair = Pair Int Double
or as variants ('sums') data Bool = False | True
Function currying Lambda Calculus has captured 2 aspects of a function:
- A mathematical object (set ordered pairs from domain and range)(map from independent variable to dependent variable)
- An abstract black box machine that takes an input and produces an output
Lambda Calculus Conversion rules:
- Computing in lambda calculus is performed using 3 conversion rules (alpha, beta, eta)
- The conversion allows you to replace an expression another "equal" one
- Some conversions simplify an expression, these are called reduction
The 3 conversion rules:
- alpha conversion: Changing name of function parameters consistently
(\x -> x + 1)==alpha conversion==>(\y -> y + 1) - Beta conversion: Replace bound variables with instance of argument
(\x -> 2 * x + g x) 42==beta conversion==>(\x -> 2 * 42 + g 42) - Eta conversion: A function is equivalent to lambda expression that takes argument and apply function to argument
(\x -> f x)(\x -> (*3) x) 50==eta conversion==>(*3) 50
Monads (">>=") means "binds to" 3 monad laws:
- Right unit law: m >>= return = m
- Left unit law: return x >>= f = f x
- Associativity law: (m >>= f) >>= g = m >>= (\x -> f x >>= g)
- A monad is a mechanism for combining computations. It is a typeclass providing bind and return operations
- To be a monadic type, the implementation of bind and return must conform to the three monad laws
I think a good place to start is to imagine that you intend to write a library for a specific purpose or domain. You want to first identify a data type in there and establish a rule. Put yourself in the shoes of a domain expert. We want to be able to encapsulate a domain expert into machine code. To be able to give a machine clear instructions, an expert would start to imagine how to give a little child with infinite pen and paper how to think about the domain (Church-Turing thesis). When trying to explain to a child a domain, an expert will naturally mentally think about mental domain models/data and rules/laws of the domain. Code can interface with systems that don't behave the same way all the time, the act of interfacing can be callled "actions." Code that is made to calculate a value or determine a decision can be called "calculations." Actions and calculations should use domain models and rules to in way to benefit the intended user. A person should be able to read domain models and rules and be able to figure out the domain. A person should be able to read actions and calculations code and tests of a domain to understand how it is intended for a user to use the domain.