Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

haskell
communitycreator

How to make all possible pairs of elements in a list in Haskell

Abdul Monum

Overview

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.

Algorithm

We can solve this problem by breaking it down into two steps:

  • First, we write a function that takes an element and a list and pairs that element with every list member.
  • Then, to make all possible pairs from a given list, we can pair the head element with all the remaining elements in the list. We then remove the head element and repeat the above process of the remaining list. This will cover all possible pair combinations.

Program

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])
Making all possible pairs from a given list

Explanation

pairElement function

The 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 function

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.

RELATED TAGS

haskell
communitycreator
RELATED COURSES

View all Courses

Keep Exploring