FP Replica Papers

Analysis of Past Papers

Recurring Themes / Topics

FP Replica Past Paper 1

Question 1: Types and Functions

(a) Give the type of f1, explain what the type means, and give the value of test_f1, where the definitions are:

f1 :: (Num a, Eq a) => a -> [a] -> [a]
f1 k xs = [x+k | x <- xs, x /= k]
test_f1 = f1 3 [2, 3, 4, -1, 5, 3]

Answer

f1 :: (Num a, Eq a) => a -> [a] -> [a]

The type means that the function takes two arguments: a value of type a and a list whose elements have type a; a can be any type provided that it is in both the Num class (so arithmetic operations can be performed) and the Eq class (so equality comparisons can be done). The function returns a list of the same type.

Value of test_f1: [5, 7, 2, 8]

(b) Give the type of f2 and the value of test_f2:

f2 f g h x = f (g (h x))
test_f2 = f2 (*2) (+3) (^2) 4

Answer

f2 :: (c -> d) -> (b -> c) -> (a -> b) -> a -> d

Value of test_f2: 2 * (3 + (4^2)) = 2 * (3 + 16) = 2 * 19 = 38

(c) Explain why head and tail are considered unsafe functions. Define safer total versions safeHead :: [a] -> Maybe a and safeTail :: [a] -> Maybe [a] using the Maybe monad.

Answer: head and tail are considered unsafe because they are partial functions - they’re undefined when applied to an empty list. If either is called with an empty list, it results in a runtime error.

safeHead :: [a] -> Maybe a
safeHead [] = Nothing
safeHead (x:_) = Just x
 
safeTail :: [a] -> Maybe [a]
safeTail [] = Nothing
safeTail (_:xs) = Just xs

(d) Consider a list fibSeq :: [Integer] with value [1, 1, 2, 3, 5, 8, 13, ...] which is infinitely long. Write a definition of fibSeq and explain how lazy evaluation makes this possible.

Answer:

fibSeq :: [Integer]
fibSeq = 1 : 1 : zipWith (+) fibSeq (tail fibSeq)

Lazy evaluation makes this possible because expressions are only evaluated when their values are needed. The definition is recursive, but Haskell only computes as many elements as required when the list is used. Without lazy evaluation, the program would attempt to compute an infinite list eagerly, resulting in non-termination or memory exhaustion.

(e) Write a function allPairs :: [a] -> [b] -> [(a,b)] that computes the Cartesian product of two lists. For instance, allPairs "hi" [1,2,3] should evaluate to [('h',1), ('h',2), ('h',3), ('i',1), ('i',2), ('i',3)]

Answer:

allPairs :: [a] -> [b] -> [(a,b)]
allPairs xs ys = [(x,y) | x <- xs, y <- ys]
 
-- Alternative implementation:
-- allPairs xs ys = concatMap (\x -> map (\y -> (x,y)) ys) xs

Question 2: Monads and Algebraic Data Types

(a) Define an algebraic data type called Shape. A Shape value can be either a Circle with a radius, a Rectangle with width and height, or a Triangle with three side lengths. All dimensions should be of type Double.

Answer:

data Shape = Circle Double
         | Rectangle Double Double
         | Triangle Double Double Double
         deriving (Show, Eq)

(b) Write a function area :: Shape -> Double that calculates the area of a given Shape.

Answer:

area :: Shape -> Double
area (Circle r) = pi * r * r
area (Rectangle w h) = w * h
area (Triangle a b c) = 
   let s = (a + b + c) / 2  -- semi-perimeter
   in sqrt (s * (s-a) * (s-b) * (s-c))  -- Heron's formula

(c) Write a smart constructor mkTriangle :: Double → Double → Double → Maybe Shape that ensures the three sides can form a valid triangle (each side must be positive and the sum of any two sides must be greater than the third side).

Answer:

mkTriangle :: Double -> Double -> Double -> Maybe Shape
mkTriangle a b c
   | a <= 0 || b <= 0 || c <= 0 = Nothing
   | a + b <= c || a + c <= b || b + c <= a = Nothing
   | otherwise = Just (Triangle a b c)

(d) Consider the Maybe monad. Give the type signature and implementation of the >>= (bind) operator for this monad, and explain how it handles failure propagation.

Answer:

(>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
Nothing >>= _ = Nothing
(Just x) >>= f = f x

The >>= operator for Maybe handles failure propagation by short-circuiting computation when a Nothing is encountered. If the left argument is Nothing, the result is immediately Nothing without evaluating the function f. If the left argument is Just x, the function f is applied to x. This allows a series of computations that might fail to be chained together, with failure at any step immediately propagating to the final result.

(e) Rewrite the following code using do notation:

validateAndProcess :: Int -> Maybe String
validateAndProcess x =
   checkPositive x >>= \y ->
   checkEven y >>= \z ->
   return (show (z * 2))
 
checkPositive :: Int -> Maybe Int
checkPositive x = if x > 0 then Just x else Nothing
 
checkEven :: Int -> Maybe Int
checkEven x = if even x then Just x else Nothing

Answer

validateAndProcess :: Int -> Maybe String
validateAndProcess x = do
   y <- checkPositive x
   z <- checkEven y
   return (show (z * 2))

Question 3: Equational Reasoning and Functional Composition

(a) Prove that map f (filter p xs) = filter p (map f xs) is false in general by providing a counterexample.

Answer: The equation map f (filter p xs) = filter p (map f xs) is false in general. A counterexample:

Let’s use f = (*2) and p = (>3) and xs = [1,2,3]

Left side: map f (filter p xs) = map (*2) (filter (>3) [1,2,3]) = map (*2) [] = []

Right side: filter p (map f xs) = filter (>3) (map (*2) [1,2,3]) = filter (>3) [2,4,6] = [4,6]

Since [] ≠ [4,6], the equation does not hold in general.

(b) Assume that the list xs has a finite (but unbounded) number of elements. Prove that sum (map (2*) xs) = 2 * sum xs using the following definition of sum:

sum :: Num a => [a] -> a
sum [] = 0
sum (x:xs) = x + sum xs

Answer

Proof by induction over xs.

Base case: xs = [] sum (map (2*) []) = sum [] = 0 = 2*0 = 2 * sum []

Induction case: Assume sum (map (2*) xs) = 2 * sum xs holds for some xs.

Consider x:xs: sum (map (2*) (x:xs)) = sum ((2_x) : map (2_) xs) = (2_x) + sum (map (2_) xs) = (2*x) + 2 * sum xs (by induction hypothesis) = 2 * (x + sum xs) (by distributivity) = 2 * sum (x:xs) (by definition of sum)

Therefore, sum (map (2*) xs) = 2 * sum xs for all finite lists xs.

(c) Recall that the monadic bind operator for the IO monad has type (>>=) :: IO a -> (a -> IO b) -> IO b. Explain what this type signature means in terms of sequencing IO operations.

Answer: The bind operator for the IO monad allows sequencing of IO operations where the result of one operation is used to determine the next operation.

The type signature (>>=) :: IO a → (a → IO b) → IO b indicates that:

1. We start with an IO action that, when performed, will produce a value of type a
2. We provide a function that, given a value of type a, determines the next IO action to perform
3. The result is a composite IO action that first performs the initial action, then uses its result to determine and perform the next action

This allows operations to be sequenced in a way that respects their dependencies, and it ensures that side effects occur in a well-defined order, which is crucial for I/O operations.

(d) Simplify the following lambda expression. Show each step in the reduction, and for each step show which conversion rule you are using.

(\a -> (\b -> a (b b))) (\x -> x) (\y -> y+1) 2

Answer

(\a -> (\b -> a (b b))) (\x -> x) (\y -> y+1) 2 > beta [substitute a = (\x → x)] (\b → (\x → x) (b b)) (\y → y+1) 2 > beta [substitute b = (\y → y+1)] (\x → x) ((\y → y+1) (\y → y+1)) 2 > beta [apply inner function] (\x → x) ((\y → y+1) + 1) 2 > beta [apply increment] (\x → x) (2 + 1) 2 > arithmetic (\x → x) 3 2 > beta [substitute x = 3] 3 2 ~> type error (cannot apply 3 to 2)`

Note: There’s actually a type error in this expression. The result of (\y -> y+1) (\y -> y+1) doesn’t make sense because we’re trying to apply a function that expects a number to another function.

Question 4: Domain Specific Languages and Parsers

(a) Define the term embedded domain specific language (EDSL). Give three examples of Haskell features that are useful for implementing EDSLs, and explain why they are useful.

Answer: An embedded domain specific language (EDSL) is a language designed for a specific application domain that is implemented by embedding it within a general-purpose host language (like Haskell). Instead of building a separate compiler or interpreter, an EDSL leverages the host language’s infrastructure and tools.

Three Haskell features useful for implementing EDSLs:

1. Algebraic data types: Enable the definition of custom data structures that model domain-specific concepts precisely and type-safely.

2. Type classes: Allow customization of standard operations for domain-specific types, making the EDSL syntax more natural. They enable operator overloading and polymorphism.

3. Higher-order functions: Facilitate the creation of combinators that compose smaller domain-specific operations into larger ones, allowing for a declarative programming style.

Other valuable features include lazy evaluation (for defining potentially infinite structures), monads (for building custom control flow), and custom operators (for domain-specific notation).

(b) Consider a type Color defined as follows:

data Color = Red | Green | Blue | Yellow | Purple | Custom Int Int Int

Write a function blend :: Color → Color → Color that blends two colors according to these rules:

• Blending primary colors (Red, Green, Blue) creates secondary colors (Yellow, Purple, Cyan)
• Blending a primary color with itself returns the same color
• Blending Custom colors averages their RGB components
• Other combinations result in a suitable Custom color

Answer

blend :: Color -> Color -> Color
blend Red Green = Yellow
blend Green Red = Yellow
blend Red Blue = Purple
blend Blue Red = Purple
blend Green Blue = Cyan
blend Blue Green = Cyan
blend Red Red = Red
blend Green Green = Green
blend Blue Blue = Blue
blend (Custom r1 g1 b1) (Custom r2 g2 b2) = 
   Custom ((r1 + r2) `div` 2) ((g1 + g2) `div` 2) ((b1 + b2) `div` 2)
blend c1 c2 = 
   let (r1, g1, b1) = toRGB c1
       (r2, g2, b2) = toRGB c2
   in Custom ((r1 + r2) `div` 2) ((g1 + g2) `div` 2) ((b1 + b2) `div` 2)
 
toRGB :: Color -> (Int, Int, Int)
toRGB Red = (255, 0, 0)
toRGB Green = (0, 255, 0)
toRGB Blue = (0, 0, 255)
toRGB Yellow = (255, 255, 0)
toRGB Purple = (255, 0, 255)
toRGB Cyan = (0, 255, 255)
toRGB (Custom r g b) = (r, g, b)

(c) Using the Parsec library, write a parser for a simple language of arithmetic expressions that supports addition, subtraction, multiplication, division, and parentheses. The parser should return an abstract syntax tree represented by the following data type:

data Expr = Num Int
         | Add Expr Expr
         | Sub Expr Expr
         | Mul Expr Expr
         | Div Expr Expr
         deriving (Show)

Answer

import Text.Parsec
import Text.Parsec.String
import Text.Parsec.Expr
import Text.Parsec.Token
import Text.Parsec.Language
 
expr :: Parser Expr
expr = buildExpressionParser table term
 
term :: Parser Expr
term = parens expr <|> fmap Num number
 
table = [ [binary "*" Mul AssocLeft, binary "/" Div AssocLeft]
       , [binary "+" Add AssocLeft, binary "-" Sub AssocLeft]
       ]
 
binary name fun assoc = 
 Infix (do{ reservedOp name; return fun }) assoc
 
TokenParser { parens = parens
           , reservedOp = reservedOp
           , number = number
           , whiteSpace = whiteSpace
           } = makeTokenParser emptyDef
 
parseExpr :: String -> Either ParseError Expr
parseExpr = parse (whiteSpace >> expr) ""

(d) Write an evaluator for the expression language defined in part (c). The evaluator should handle division by zero by returning a Maybe type.

Answer:

eval :: Expr -> Maybe Int
eval (Num n) = Just n
eval (Add e1 e2) = do
   v1 <- eval e1
   v2 <- eval e2
   return (v1 + v2)
eval (Sub e1 e2) = do
   v1 <- eval e1
   v2 <- eval e2
   return (v1 - v2)
eval (Mul e1 e2) = do
   v1 <- eval e1
   v2 <- eval e2
   return (v1 * v2)
eval (Div e1 e2) = do
   v1 <- eval e1
   v2 <- eval e2
   if v2 == 0 
      then Nothing
      else Just (v1 `div` v2)

Link to original

FP Replica Past Paper 2

Question 1: Higher-Order Functions and Type Classes

(a) What are higher-order functions and why are they so common in Haskell?

Answer: Higher-order functions are functions that take other functions as parameters and/or return functions as results. They’re common in Haskell because:

1. Functions are first-class citizens in Haskell, meaning they can be treated like any other value
2. They enable powerful abstractions and code reuse
3. They facilitate composable program design
4. They’re a natural consequence of the functional programming paradigm
5. They help express algorithms in a clear, concise manner

Higher-order functions like map, filter, and fold are fundamental to Haskell programming as they capture common patterns of computation over data structures.

(b) Define a function twice :: (a -> a) -> a -> a which applies the function (supplied as first parameter) two times to the subsequent parameter value. For instance, twice (+1) 0 would evaluate to 2.

Answer:

twice :: (a -> a) -> a -> a
twice f x = f (f x)

(c) Now consider how to generalize the function twice to a function ntimes, which repeatedly applies a function (supplied as a parameter) multiple times. The type signature is: ntimes :: (a -> a) -> Int -> a -> a. For example, ntimes (+2) 5 0 evaluates to 10 and ntimes tail 3 [1..10] evaluates to [4,5,6,7,8,9,10]. Write a Haskell definition for this ntimes function. You may assume the supplied integer value is non-negative. If the integer value is 0 then the behavior is the same as the identity function.

Answer:

ntimes :: (a -> a) -> Int -> a -> a
ntimes _ 0 x = x
ntimes f n x = ntimes f (n-1) (f x)

(d) Recall that the Functor typeclass is defined as follows:

class Functor f where
   fmap :: (a -> b) -> f a -> f b

Write a Functor instance for the following binary tree data type:

data Tree a = Leaf | Node a (Tree a) (Tree a)

Answer

instance Functor Tree where
   fmap _ Leaf = Leaf
   fmap f (Node x left right) = Node (f x) (fmap f left) (fmap f right)

(e) Write a Functor instance for the following data type:

data Either' a b = Left' a | Right' b

Is this a valid Functor instance? Explain why or why not.

Answer

instance Functor (Either' a) where
   fmap _ (Left' x) = Left' x
   fmap f (Right' y) = Right' (f y)

This is a valid Functor instance for Either' a (not for Either' directly). Note that the instance is for the type constructor Either' a which has kind * -> * as required for Functor instances. The function fmap only transforms the value in the Right’ constructor, leaving Left’ values unchanged.

The instance satisfies the functor laws:

6. Identity: fmap id = id
7. Composition: fmap (f . g) = fmap f . fmap g

Question 2: Algebraic Data Types and Pattern Matching

(a) Given the following type and expression:

data Tree a = Leaf a | Branch (Tree a) (Tree a)
 
tree1 :: Tree Int
tree1 = Branch (Branch (Leaf 1) (Leaf 2)) (Leaf 3)

Write a function countLeaves :: Tree a → Int that returns the number of Leaf nodes in a tree. For instance, countLeaves tree1 should evaluate to 3.

Answer

countLeaves :: Tree a -> Int
countLeaves (Leaf _) = 1
countLeaves (Branch left right) = countLeaves left + countLeaves right

(b) Write a function mirror :: Tree a -> Tree a that returns the mirror image of a binary tree. For example, if tree1 is Branch (Branch (Leaf 1) (Leaf 2)) (Leaf 3), then mirror tree1 would be Branch (Leaf 3) (Branch (Leaf 2) (Leaf 1)).

Answer:

mirror :: Tree a -> Tree a
mirror (Leaf x) = Leaf x
mirror (Branch left right) = Branch (mirror right) (mirror left)

(c) Write a function foldTree :: (a -> b) -> (b -> b -> b) -> Tree a -> b that generalizes operations over a Tree. The first argument is applied to leaf values, and the second argument combines results from branches.

Answer:

foldTree :: (a -> b) -> (b -> b -> b) -> Tree a -> b
foldTree f _ (Leaf x) = f x
foldTree f g (Branch left right) = g (foldTree f g left) (foldTree f g right)

(d) Reimplement countLeaves and mirror using foldTree.

Answer:

countLeaves' :: Tree a -> Int
countLeaves' = foldTree (const 1) (+)
 
mirror' :: Tree a -> Tree a
mirror' = foldTree Leaf (\left right -> Branch right left)

(e) Consider a binary search tree (BST) implemented with the following data type:

data BST a = Empty | Node a (BST a) (BST a)

Write a function insert :: Ord a => a -> BST a -> BST a that inserts a value into a BST, maintaining the binary search tree property.

Answer

insert :: Ord a => a -> BST a -> BST a
insert x Empty = Node x Empty Empty
insert x (Node y left right)
   | x < y     = Node y (insert x left) right
   | x > y     = Node y left (insert x right)
   | otherwise = Node x left right  -- Replace existing value

Question 3: Monads and Effects

(a) The State monad allows for stateful computations while maintaining referential transparency. It is defined as follows:

newtype State s a = State { runState :: s -> (a, s) }
 
instance Monad (State s) where
   return x = State $ \s -> (x, s)
   m >>= f = State $ \s -> 
               let (a, s') = runState m s
               in runState (f a) s'

Define the following helper functions for the State monad:

get :: State s s            -- Retrieves the current state
put :: s -> State s ()      -- Replaces the state
modify :: (s -> s) -> State s ()  -- Applies a function to the state

Answer

get :: State s s
get = State $ \s -> (s, s)
 
put :: s -> State s ()
put s = State $ \_ -> ((), s)
 
modify :: (s -> s) -> State s ()
modify f = State $ \s -> ((), f s)

(b) Use the State monad to implement a function evalRPN that evaluates a Reverse Polish Notation expression. RPN expressions are represented as lists of tokens, where a token can be either a number or an operator (+, -, _, /). For example, evalRPN [5, 3, "+", 2, "_"] should evaluate to 16.

data Token = Number Int | Plus | Minus | Times | Divide
 
evalRPN :: [Token] -> Maybe Int

Answer

import Control.Monad.State
 
data Token = Number Int | Plus | Minus | Times | Divide
   deriving (Show, Eq)
 
type Stack = [Int]
 
evalRPN :: [Token] -> Maybe Int
evalRPN tokens = 
   case evalState (processTokens tokens) [] of
       [result] -> Just result
       _        -> Nothing
 
processTokens :: [Token] -> State Stack Stack
processTokens [] = get
processTokens (token:rest) = do
   modify (processToken token)
   processTokens rest
 
processToken :: Token -> Stack -> Stack
processToken (Number n) stack = n : stack
processToken Plus (b:a:rest) = (a + b) : rest
processToken Minus (b:a:rest) = (a - b) : rest
processToken Times (b:a:rest) = (a * b) : rest
processToken Divide (b:a:rest) = (a `div` b) : rest
processToken _ stack = stack  -- Error case, should never happen with valid input

(c) Consider a simple game where a player moves on a grid. The player’s state consists of their position (x, y) and their score. Implement the following functions using the State monad:

type PlayerState = ((Int, Int), Int)  -- ((x, y), score)
 
moveUp :: State PlayerState ()
moveDown :: State PlayerState ()
moveLeft :: State PlayerState ()
moveRight :: State PlayerState ()
addPoints :: Int -> State PlayerState ()

Answer:

type PlayerState = ((Int, Int), Int)  -- ((x, y), score)
 
moveUp :: State PlayerState ()
moveUp = modify (\((x, y), score) -> ((x, y+1), score))
 
moveDown :: State PlayerState ()
moveDown = modify (\((x, y), score) -> ((x, y-1), score))
 
moveLeft :: State PlayerState ()
moveLeft = modify (\((x, y), score) -> ((x-1, y), score))
 
moveRight :: State PlayerState ()
moveRight = modify (\((x, y), score) -> ((x+1, y), score))
 
addPoints :: Int -> State PlayerState ()
addPoints pts = modify (\(pos, score) -> (pos, score + pts))

(d) Consider a function getElement :: [a] → Int → Maybe a that safely accesses an element in a list at a given index. Using the Maybe monad, write a function getElementsSum that takes a list of integers and a list of indexes, and returns the sum of the elements at those indexes. If any index is out of bounds, the function should return Nothing.

Answer:

getElement :: [a] -> Int -> Maybe a
getElement xs i
   | i >= 0 && i < length xs = Just (xs !! i)
   | otherwise = Nothing
 
getElementsSum :: [Int] -> [Int] -> Maybe Int
getElementsSum xs indices = do
   elements <- mapM (getElement xs) indices
   return (sum elements)

Alternatively:

getElementsSum :: [Int] -> [Int] -> Maybe Int
getElementsSum xs indices = fmap sum $ sequence $ map (getElement xs) indices

Question 4: Lazy Evaluation and Infinite Data Structures

(a) Explain the concept of lazy evaluation in Haskell and how it differs from eager evaluation.

Answer: Lazy evaluation is a strategy where expressions are evaluated only when their values are needed. In Haskell, this means:

1. Expressions are not evaluated when they are bound to variables, but only when their results are required
2. Function arguments are not evaluated before the function is called
3. Data structures are constructed on-demand - only the parts that are accessed are computed

This differs from eager evaluation (used in most programming languages) where:

4. Expressions are evaluated immediately when they are bound
5. Function arguments are fully evaluated before the function is called
6. Data structures are completely constructed at definition time

Benefits of lazy evaluation include:

• Ability to work with infinite data structures
• Potential performance improvements by avoiding unnecessary computation
• More modular code through separation of data structure generation and consumption
• Natural implementation of control structures as functions

Challenges include:

• Less predictable space usage due to unevaluated expressions (thunks)
• Harder to reason about performance

representing the Fibonacci sequence [0, 1, 1, 2, 3, 5, 8, ...] using lazy evaluation.

Answer:

fibs :: [Integer]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

I’ll continue with the rest of the Replica Past Paper 2.

that returns an infinite list of prime numbers using the Sieve of Eratosthenes algorithm.

Answer:

primes :: [Integer]
primes = sieve [2..]
 where
   sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]

(d) Consider the following definition of an infinite binary tree:

data InfTree a = Node a (InfTree a) (InfTree a)
 
-- Creates an infinite tree where each node contains its path
-- represented as a list of Bools (False = left, True = right)
pathTree :: InfTree [Bool]
pathTree = buildTree []
 where
   buildTree path = Node path 
                      (buildTree (path ++ [False])) 
                      (buildTree (path ++ [True]))

Write a function getPath :: [Bool] → InfTree [Bool] → [Bool] that retrieves the node value at the path specified by the first argument. For example, getPath [False, True] pathTree should return [False, True].

Answer

getPath :: [Bool] -> InfTree [Bool] -> [Bool]
getPath [] (Node val _ _) = val
getPath (False:ps) (Node _ left _) = getPath ps left
getPath (True:ps) (Node _ _ right) = getPath ps right

(e) Write a function takeLevel :: Int -> InfTree a -> [a] that returns all values at a specific depth in the tree, from left to right. For example, takeLevel 0 pathTree should return [[]], and takeLevel 1 pathTree should return [[False], [True]].

Answer:

takeLevel :: Int -> InfTree a -> [a]
takeLevel 0 (Node val _ _) = [val]
takeLevel n (Node _ left right) = takeLevel (n-1) left ++ takeLevel (n-1) right

(f) Consider the following infinite data structure representing a game tree for tic-tac-toe:

data Player = X | O deriving (Show, Eq)
type Board = [[Maybe Player]]  -- 3x3 grid
data GameTree = GameTree Board Player [GameTree]

Explain how lazy evaluation makes it possible to define such a tree, and how pruning strategies can be implemented to explore only parts of the tree.

Answer

Lazy evaluation allows us to define the complete game tree for tic-tac-toe without requiring it to be fully computed in memory at once. The tree can potentially contain all possible game states, but only the paths that are actually explored will be computed.

When we define the game tree, we’re actually defining a recipe for how to generate each node when needed, not the entire tree structure in memory. The nodes and branches are only calculated when we attempt to access them.

Pruning strategies can be implemented by defining functions that traverse the tree but only follow certain branches based on evaluation criteria:

1. Alpha-beta pruning can avoid exploring branches that won’t affect the final decision
2. We can implement a depth-limited search that only explores the tree to a certain depth
3. Heuristic evaluations can help decide which branches are worth exploring

For example, a minimax algorithm with alpha-beta pruning would avoid evaluating branches that can’t possibly affect the final decision. Since the tree is lazily evaluated, branches that are never accessed are never computed, saving both time and memory.

This combination of lazy evaluation and pruning strategies allows us to work with a conceptually infinite game tree while only computing the relevant portions of it.

Link to original