Implementation of simple datastructures using SK(I) Combinator Calculus

This repo contains simple datastructures implementation using SK(I) Combinator Calculus. All the implementations are done in Python 3.7+

SK(I) Combinators

S Combinator

S := \f g x. f x (g x)

K Combinator

K := \x y. x

I Combinator (Can be defined in terms of S & K)

I := \x. x
  := \x. K x K
  := \x. K x (K K x)
  := \x. S K (K K) x
  := S K (K K)

References

1. (Book) Purely Functional Data Structures - Okasaki

2. (Youtube) A Flock of Functions: Lambda Calculus and Combinatory Logic in JavaScript | Gabriel Lebec @ DevTalks

License & Copyright

Licensed under @MIT