Haskell is a functional programming language, a programming paradigm that focuses on changing data through expressions that don’t have side effects. These expressions are often called pure functions.
We’ll write a pure function that makes all possible pairs of elements in a given list.
We can solve this problem by breaking it down into two steps:
Below is the Haskell program to make all possible pairs of elements in a list:
-- Pair an element with every member of the input list pairElement:: a -> [a] ->  (a,a) pairElement = \elem -> \list -> case list of  ->  x:xs -> [(elem,x)] ++ pairElement elem xs -- Make all possible pairs of elements in a given list makePairs ::  a ->  (a, a) makePairs = \list -> case list of  ->  x:xs -> pairElement x xs ++ makePairs xs main = print (makePairs [1, 2, 3])
pairElement function implements the first step of the algorithm. It takes an element and pairs it with every element of the list.
pairElement:: a -> [a] ->  (a,a) is the type annotation for our function called
pairElement. Haskell is statically typed, and every function or variable has a type. In this case,
pairElement is a function that takes an element of any type, takes a list of the same type as the element, and returns a list of tuples.
Lines 3 to 4: We use the function definition, which shows that our function takes an element and a list. It also takes a
case expression on the list that implements the recursive formulation of the problem.
Line 5: The first case statement implements the base case. If the input list is empty, then there is nothing to pair with, and hence we return an empty list.
Line 6: The second equation implements the general case.
x:xs is a syntax in Haskell that neatly provides us with the head of the list,
x, and the remainder list
xs. We pair the element
x in a tuple and place it in a list. Now we concatenate this list with the result of the recursive call to
pairElement which receives the remainder of the list
makepairs is our main function, which uses the above function and performs the second step of our algorithm.
The first case statement implements the base case. If there is an empty list, then no pairs can be made, and therefore we return an empty list.
The second case statement implements the general case. We do a recursive call of the
makePairs function on the list
xs. We can assume that our recursive function correctly returns a list with all possible pairs of elements in the list
xs. To solve our original problem, we need to pair the head element
x with the remaining list
xs and add these pairs to the solution of the recursive call. We use our above function
pairElement and concatenate its result with the answer from the recursive to return the final solution.
View all Courses