jq as a Stream Calculus and Tree Algebra
A Deep Semantic and Operational Mini-Book This is not documentation. This is not a tutorial. This is a semantic excavation. We will treat jq as: A stream calculus A purely functional reduction algebra A tree traversal and rewrite system A scoped evaluation engine with explicit rebinding Note To run a jq file do that: Copy Copy $ jq -f test.jq file.json And also some sections will implicitly reference these files file1 file2 1. The Execution Model: Streams, Not Values Every jq filter is: Copy Filter : Value → Stream<Value> Even if it emits one value, it is still a stream. Even if it emits zero values, it is still a stream. Composition: Copy a | b means: Copy for each v in a(input): emit b(v) This is critical: | is…
functional-programmingThe Knight’s Tour in Haskell — From Brute Force to Warnsdorff’s Heuristic
One of the most fascinating and ancient problems in recreational mathematics is the Knight’s Tour — the challenge of moving a chess knight so that it visits every square of an N×N chessboard exactly once. It’s not just a puzzle: it’s a deep exploration of backtracking, graph traversal, and even heuristic search. In this post, I’ll show how I implemented the Knight’s Tour in Haskell — first using a basic DFS (Depth-First Search), and then improved it with Warnsdorff’s rule, a clever heuristic that dramatically improves performance. The Problem The knight’s movement pattern is unique: it moves two squares in one direction and one in the perpendicular direction. In coordinates, from position (x, y), it can move to: Copy (x ± 2, y ± 1) or (x ± 1, y…
functional-programmingChecking Graph Bipartiteness in Haskell
One of the most elegant problems in graph theory is determining whether a given graph is bipartite. A bipartite graph is one whose nodes can be divided into two disjoint sets such that no two nodes within the same set are connected by an edge. This concept appears everywhere — from scheduling and matching problems to network flow and coloring algorithms. In this project, I wrote a full Haskell implementation to determine whether any graph is bipartite, even if it’s disconnected. 1. The key idea If a graph has multiple connected components (subgraphs that are not connected to each other), we can test each subgraph independently. A disconnected graph is bipartite if and only if all its subgraphs are bipartite. So the problem splits naturally into two steps: Find all…
functional-programmingSolving the Eight Queens Problem in Haskell
The Eight Queens Problem is one of the most famous challenges in computer science and mathematics. The goal is simple to state yet surprisingly rich in structure: Place eight queens on a chessboard so that no two queens threaten each other. In practice, that means ensuring that no two queens share the same row, column, or diagonal. It’s a classical example of a constraint satisfaction problem — and an elegant one to tackle using Haskell’s declarative and recursive strengths. 1. The problem restated We must place 8 queens on an 8×8 chessboard so that: No two queens share the same column. No two queens share the same row. No two queens share the same diagonal (both ascending and descending). We’ll represent each solution as a list of 8 integers, where…
functional-programmingExploring Reachability in Directed Graphs with Haskell
Exploring Reachability in Directed Graphs with Haskell Graphs are a natural way to represent systems of connections — from flight networks to dependencies in code or social networks. In directed graphs, edges have a direction, and not all nodes may be reachable from one another. This brings up a fascinating question: From which nodes can we reach all others? To explore this, I wrote a Haskell function that recursively discovers all directed paths in a graph, and identifies the nodes that can reach every other node. 1. The problem Given a directed graph represented as a pair ([nodes], [(from, to)]), we want to: Find all traversal paths starting from every node. Keep only the nodes that can reach all others. The function should therefore output a list of path groups…
functional-programmingHow Do They Display Trees — Three Layout Algorithms in Haskell
When you visualize data structures in a GUI — such as decision trees, syntax trees, or even neural networks — one key algorithmic problem hides behind the scenes: How do you determine where to draw each node? Many libraries in higher-level languages (like Python’s data science tools or visualization frameworks) rely on carefully designed tree layout algorithms to assign 2D coordinates to nodes. Problems 64 to 66 from the 99 Haskell Problems explore exactly that: how to compute node coordinates for different layout styles. In this article, we’ll go through three classic methods of visualizing trees — each one balancing symmetry, spacing, and readability differently. 1. Layout Algorithm #1 — Inorder Positioning (Problem 64) The first method assigns each node’s position based on two simple rules: x(v) equals the position…
functional-programmingConstructing All Spanning Trees in Haskell (Problem 83)
In graph theory, a spanning tree of a connected graph is a subgraph that includes all the nodes of the original graph, connected with the minimum number of edges (exactly n − 1 for n nodes) and without any cycles. I discovered this concept through Problem 83 of the 99 Haskell Problems series. The goal is to construct, by backtracking, all spanning trees of a given graph, and then use that logic to check if a graph is a tree or if it’s connected. 1. The problem Write a function spanningTree that constructs (by backtracking) all spanning trees of a given graph. Once we have that, we can easily define two related functions: is_tree(Graph) — determines if a graph is a tree. is_connected(Graph) — determines if a graph is connected.…
functional-programmingGraph Isomorphism in Haskell (Problem 85)
Graph isomorphism is one of the classic challenges in graph theory and computer science. It involves determining whether two graphs have the same structure — that is, whether one can be transformed into the other simply by relabeling its nodes. I first encountered this problem through the 99 Haskell Problems, specifically Problem 85. It’s an elegant exercise that brings together recursion, list manipulation, and combinatorics. 1. The problem Two graphs G₁(N₁,E₁) and G₂(N₂,E₂) are isomorphic if there exists a bijection f : N₁ → N₂ such that for any nodes X, Y ∈ N₁, X and Y are adjacent if and only if f(X) and f(Y) are adjacent. In other words, two graphs are isomorphic if they are structurally identical, regardless of how their nodes are labeled. Example Copy λ>…
functional-programmingIntroduction to Graph Theory in Haskell
Graph theory is one of the most fascinating areas of computer science and mathematics, forming the foundation for countless real-world applications: from social networks and routing systems to dependency trees in compilers. When learning Haskell, I was first introduced to graph theory through the 99 Haskell Problems — a collection of exercises that gradually expose you to elegant and expressive functional patterns. Problem 81, in particular, focuses on finding all acyclic paths between two nodes in a directed graph. 1. The challenge The problem is simple to state: Given two nodes a and b in a directed graph, return all possible acyclic paths from a to b. For example: Copy λ> paths 1 4 [(1,2),(2,3),(1,3),(3,4),(4,2),(5,6)] [[1,2,3,4],[1,3,4]] λ> paths 2 6 [(1,2),(2,3),(1,3),(3,4),(4,2),(5,6)] [] 2. Representing a graph in Haskell Before diving…
functional-programmingImplementing Huffman Encoding in Haskell
Huffman encoding is one of the foundational algorithms in data compression — elegant, efficient, and entirely based on simple mathematical principles. It converts symbols and their frequencies into binary codes where the most frequent symbols receive shorter codes. The algorithm is used in many compression systems, including ZIP and JPEG, and fits naturally into functional programming thanks to its recursive and tree-based nature. In this project, I implemented Huffman coding in Haskell from scratch. The goal was to explore tree construction, recursion, and symbol encoding rather than optimize for absolute performance. Interestingly, depending on input characteristics, my approach sometimes generates a code table that uses slightly fewer bits than a classic implementation — but that is highly input-dependent. 1. The problem setup Given a set of symbols and their frequencies:…
functional-programmingUnderstanding Recursion Through Combinations, Permutations, and Trees in Haskell
Recursion often feels like a mysterious concept when you first encounter it — until you realize that it’s not about doing something repeatedly, but about breaking a problem into smaller, self-similar parts. In this post, we’ll explore how recursion allows us to generate combinations, random permutations, and even manipulate trees and graphs elegantly in Haskell. To begin, here’s how I once described it: “So when my program makes its first recursive call, what does it actually do? Does it launch another recursive call with a different input?” The answer is yes — it destructures the input string, taking its first element, say “a”. If we follow only that first recursive call, it will generate “abc”. But notice that when it took “a”, it also made another recursive call — this…
functional-programmingFinding the Optimal Path in Haskell: A Recursive Exploration
I will explain from my point of view the solution to the following problem here, we explore a recursive approach to solving an optimal path problem — where at each step, multiple paths are possible, and we must decide which route minimizes the total cost. The idea is to think of the problem as a sequence of blocks — each representing a segment of possible movements. Between these blocks, we must choose how to transition optimally while keeping track of cumulative costs along each possible path. 1. The block model and mental picture We can think of the system as three tracks: A, B, and C. Each block of the path has three values representing the cost of traveling along each of these tracks (or switching between them). We define…
functional-programmingUnderstanding the Haskell Type System: From Typeclasses to Data Structures
In this tutorial — inspired by my video “Structure de données et système de types en Haskell” — we dive into the heart of what makes Haskell so expressive: its type system. This article targets an intermediate audience: you already know what a function or a list is, but now you want to understand why types in Haskell feel so different — and powerful — compared to other languages. 1. Why types matter in Haskell In Haskell, types are not just annotations — they are first-class citizens that define how values behave and interact. The compiler (GHC) uses types to enforce correctness, optimize performance, and even help you reason about your program. Every value in Haskell has a type, and Haskell’s compiler infers those types automatically. But you can (and…
functional-programmingUnderstanding Parenthesis Tokenization in Haskell
Context Before building a full arithmetic calculator in Haskell, there was one key challenge I needed to solve first: understanding and tokenizing parentheses. Parenthesis tokenization may sound like a small detail, but it’s actually a necessary step for building my own calculator interpreter — the engine that later evaluates nested expressions like (3+(2*(5-1))) correctly, respecting operator precedence and nesting depth. 1. Why tokenization matters In an arithmetic expression, parentheses determine the order in which subexpressions are evaluated. To process them properly, a calculator must: Recognize where every ( and ) occurs Track how deeply nested each one is Know which pairs of parentheses match together Once we have this information, we can safely evaluate the innermost expressions first and work our way out — exactly how human math logic works.…
functional-programmingBuilding a Tiny Reverse Polish Notation (RPN) Calculator in Haskell
In this project, we’ll build a small expression evaluator using Reverse Polish Notation (RPN) — also called postfix notation. The idea is simple: instead of writing 3 + 4, you write 3 4 +. This lets you evaluate expressions without worrying about parentheses or operator precedence. The project is a fun and compact way to learn about: Recursion Pattern matching List manipulation with foldl Function composition 1. The goal We want a function that can take a string like "3 4 +" and return 7.0. Or more complex ones like "2 3 4 + *" → 14.0. We’ll also add support for basic arithmetic, powers, exponentials, logs, and even a factorial! 2. The full code Copy primitiveSolver :: String -> Double primitiveSolver expr = head . foldl funcNPI [] .…
functional-programmingLearning Haskell with Weird Goals
Sometimes, the best way to learn a language is by using a simple, even slightly “weird” goal as an excuse to explore its core concepts. Here, the goal is to extract the sides (apart from the hypotenuse) from a list of Pythagorean triples—but really, it’s just a reason to learn how pattern matching, recursion, and let blocks work in Haskell. 1. A simple pattern-matching refresher In Haskell, you can deconstruct tuples directly in function arguments. It’s an elegant and expressive way to “take apart” data structures. Let’s define three simple functions to get each element from a 3-tuple: Copy myFst :: (Int, Int, Int) -> Int myFst (x, _, _) = x mySnd :: (Int, Int, Int) -> Int mySnd (_, x, _) = x myThrd :: (Int, Int, Int)…
functional-programmingBrute-forcing Pythagorean Triples with Haskell List Comprehensions (up to 100)
We want all integer solutions (a,b,c) to the equation a^2 = b^2 + c^2 with 0 < a < 100. This is a great place to use Haskell’s list comprehensions: they’re concise, readable, and—when bounded carefully—surprisingly efficient. The goal (and a small symmetry trick) We’re after triples (a,b,c) that satisfy: a^2 = b^2 + c^2 0 < a < 100 to avoid duplicates from swapping legs, we enforce ordering: c < b < a That last line is key: every valid solution has one leg greater or equal to the other, so we arbitrarily choose b to be the larger leg and enforce c < b. This removes mirrored duplicates. Important list comprehension fact In a Haskell list comprehension, a variable can be used only if it’s defined earlier in…
functional-programmingHow Haskell (and the Functional Mindset) Rewired the Way I Think About Code
I didn’t set out to “become a functional programmer.” I stumbled into Haskell after years of imperative and OOP work, mostly focused on getting features out the door. I knew about lambdas and “map/filter,” but those were just utilities, not a worldview. My real journey started with the excellent online book Learn You a Haskell for Great Good!. Its playful style made functional programming approachable, and soon I realized Haskell wasn’t just another language—it was a different way to think about programs: where state is explicit, effects are controlled, and types carry meaning. Why Haskell Was Created Haskell wasn’t born out of industry needs but out of academic curiosity and a desire for clarity. In the 1980s, researchers had designed many lazy functional languages, but the landscape was fragmented. To…
