---
title: "Lazier Binary Decision Diagrams (BDDs) for set-theoretic types"
url: https://daily.dev/posts/lazier-binary-decision-diagrams-bdds-for-set-theoretic-types-wycdb5gsa
source_url: http://elixir-lang.org/blog/2025/12/02/lazier-bdds-for-set-theoretic-types/
type: article
source: "Elixir"
published: 2025-12-02T11:47:23.467Z
updated: 2025-12-08T02:16:21.945Z
tags: ["compiler", "data-structures", "elixir", "performance", "type-systems"]
reading_time: 16
upvotes: 4
comments: 1
language: en
---

> ## Documentation Index
> Fetch the complete documentation index at: https://daily.dev/llms.txt
> Use this file to discover all available pages before exploring further.

# Lazier Binary Decision Diagrams (BDDs) for set-theoretic types

**[Elixir](https://daily.dev/sources/elixir)** · 16 min read · 4 upvotes · 1 comments

## Summary

The Elixir team optimized their set-theoretic type system by evolving from Disjunctive Normal Forms (DNFs) to Binary Decision Diagrams (BDDs), and ultimately to "lazier BDDs" with improved union handling. The original DNF implementation suffered from exponential blow-up during intersections, which became problematic when Elixir v1.19 introduced type inference for anonymous functions requiring negations. While standard BDDs addressed intersection performance, they introduced slowdowns with unions. The team developed enhanced formulas that preserve union nodes during intersections and differences, eliminating redundant computations and achieving faster type checking than previous versions.

## Full article

daily.dev links to this article rather than hosting it. Read it at the original source: <http://elixir-lang.org/blog/2025/12/02/lazier-bdds-for-set-theoretic-types/>

## Community discussion

Top comments from developers on daily.dev.

**@skeptiq** · 0 upvotes

> I'm an Elixir programmer but this description sounds to me like Chinese. (Or rather AI slop ?)

## Similar posts on daily.dev

- [Lazy BDDs with eager literal differences](https://daily.dev/posts/lazy-bdds-with-eager-literal-differences-utpsbskcr) · Elixir · 18 upvotes · 0 comments
- [Lazy BDDs with eager literal intersections](https://daily.dev/posts/lazy-bdds-with-eager-literal-intersections-jrqly4sxw) · Elixir · 24 upvotes · 0 comments

---

Tags: [#compiler](https://daily.dev/tags/compiler), [#data-structures](https://daily.dev/tags/data-structures), [#elixir](https://daily.dev/tags/elixir), [#performance](https://daily.dev/tags/performance), [#type-systems](https://daily.dev/tags/type-systems)

[View this post on daily.dev](https://daily.dev/posts/lazier-binary-decision-diagrams-bdds-for-set-theoretic-types-wycdb5gsa)