Write a function to determine if a list is a sublist of another list.
Write a function that given two lists determines if the first list is contained within the second list, if the second list is contained within the first list, if both lists are contained within each other or if none of these are true.
Specifically, a list A is a sublist of list B if by dropping 0 or more elements from the front of B and 0 or more elements from the back of B you get a list that’s completely equal to A.
\begin{align*}
[1, 2, 3] &\subseteq [1, 2, 3, 4, 5]
[3, 4, 5] &\subseteq [1, 2, 3, 4, 5] \
[3, 4] &\subseteq [1, 2, 3, 4, 5] \
[1, 2, 3] &≡ [1, 2, 3] \
[1, 2, 3, 4, 5] &\supseteq [2, 3, 4] \
[1, 2, 4] &¬= [1, 2, 3, 4, 5]
\end{align*}
For the sake of convenience I imported isInfixOf
from Data.List
.
import Data.List
Then I set up the Sublist
data type.
data Sublist
-- | The two lists are equal.
= Equal
-- | The first list is a fully contained, in order, in the second list.
| Sublist
-- | The first list fully contains, in order, the second list.
| Superlist
-- | Neither list fully contains the other.
| Unequal
deriving (Show, Eq)
Which is used as the return type for sublist
.
sublist :: Eq a = [a] -> [a] -> Sublist
With isInfixOf
, the implementation of sublist
is trivial.
sublist a b
| a == b = Equal
| a `isInfixOf` b = Sublist
| b `isInfixOf` a = Superlist
| otherwise = Unequal
runhaskell sublist_test.hs
Cases: 18 Tried: 18 Errors: 0 Failures: 0