Search⌘ K
AI Features
Home
Courses
Learn Functional Programming in Haskell

Larger Example: Solving Mazes

Explore how to build a complete maze solver in Haskell by applying functional programming principles. Learn to model the maze domain with types, perform depth first search, handle file IO, and output solutions. This lesson helps you combine recursion, pattern matching, and IO operations to solve complex problems.

We'll cover the following...

In this lesson, we will combine all that we have learned in the course to write a larger Haskell program. Our goal is to write a program that solves mazes. To do so, we will first read the maze from an input file, compute the solution, and finally print it to the console.

Problem definition

The program that we will write will solve mazes of this format:

##########
#........#
#.###.##.#
#.#S.....#
#.###.##.#
#.#...##.#
#..##...##
##.####.##
#...E#..##
##########

In such a grid based maze

  • the hash # denotes a wall
  • the dot . denotes a free space
  • the character S denotes the starting position
  • the character E denotes the exit

The task is to find a sequence of moves through the grid that leads from the start to the exit. Only movement along the four cardinal directions is allowed.

For the example maze above, one possible solution is to take

  1. Two steps east
  2. Two steps north
  3. Four steps west
  4. Five steps south
  5. One step east
  6. Two steps south
  7. Two steps east

This is a visualization of the taken path:

##########
#v<<<<...#
#v###^##.#
#v#S>^...#
#v###.##.#
#v#...##.#
#>v##...##
##v####.##
#.>>E#..##
##########

Modeling the problem domain

A good first step in writing functional programs is to start with defining types that express the problem domain. In this case, we are dealing with a 2D grid of fields that can be either walls, free spaces, or the start and exit of the maze.

The grid

Let’s start by defining a data type for fields.

data Field = Start | Free | Wall | Exit deriving (Eq, Show)

We derive Eq and Show so we can easily compare and print the fields. Since the input to our program will be in text ...