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 listpairElement:: 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 listmakePairs :: [] a -> [] (a, a)makePairs = \list ->case list of[] -> []x:xs -> pairElement x xs ++ makePairs xsmain = print (makePairs [1, 2, 3])
pairElement functionThe pairElement function implements the first step of the algorithm. It takes an element and pairs it with every element of the list.
Line 2: 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 elem with 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 xs.
makePairs functionmakepairs 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.