-- Binary search is a recursive algorithm that finds an element in a sorted list by
-- repeatedly dividing the list into two halves and comparing the element with the middle value.
-- It returns the index of the element if found, or Nothing otherwise.
-- Precondition: The input list must be sorted in ascending order.
-- Postcondition: The output index must be within the bounds of the list and point to the element, or be Nothing.
-- Invariant: The element, if present, must be in the current sublist.
-- Variant: The length of the current sublist decreases by half at each recursive call.
-- Internal state: The current sublist is defined by two indices: low and high.
binarySearch :: Ord a => [a] -> a -> Maybe Int
binarySearch xs x = go xs x 0 (length xs - 1)
where
-- The go function performs the recursive search on the sublist [low..high].
go :: Ord a => [a] -> a -> Int -> Int -> Maybe Int
go xs x low high
-- Base case 1: The sublist is empty, so the element is not found.
| low > high = Nothing
-- Base case 2: The middle value is equal to the element, so the index is found.
| xs !! mid == x = Just mid
-- Recursive case 1: The element is smaller than the middle value, so search in the left half.
| x < xs !! mid = go xs x low (mid - 1)
-- Recursive case 2: The element is larger than the middle value, so search in the right half.
| otherwise = go xs x (mid + 1) high
where
-- Calculate the middle index using a safer formula to avoid overflow.
mid = low + (high - low) `div` 2
-- A sample list to test the binary search function.
sampleList :: [Int]
sampleList = [1, 3, 5, 7, 9, 11, 13, 15]
-- A sample element to search for in the list.
sampleElement :: Int
sampleElement = 9
-- Print the result of the binary search using putStrLn.
main :: IO ()
main = do
let result = binarySearch sampleList sampleElement
case result of
Nothing -> putStrLn "Element not found."
Just i -> putStrLn $ "Element found at index " ++ show i ++ "." Write, Run & Share Haskell code online using OneCompiler's Haskell online compiler for free. It's one of the robust, feature-rich online compilers for Haskell language, running the latest Haskell version 8.6. Getting started with the OneCompiler's Haskell editor is easy and fast. The editor shows sample boilerplate code when you choose language as Haskell and start coding.
OneCompiler's Haskell online editor supports stdin and users can give inputs to programs using the STDIN textbox under the I/O tab. Following is a sample Haskell program which takes name as input and prints hello message with your name.
main = do
name <- getLine
putStrLn ("Hello " ++ name ++ ", Happy learning!") Haskell is purely a functional programming language which was introduced in 1990's.
| Data-type | Description |
|---|---|
| Numbers | Haskell is intelligent to identify numbers without specifying data type |
| Characters | Haskell is intelligent to identify characters and strings without specifying data type |
| Tuple | To declare multiple values in a single data type. Tuples are represented in single paranthesis. For example (10, 20, 'apple') |
| Boolean | To represent boolean values, true or false |
| List | To declare same type of values in a single data type. Lists are represented in square braces.For example [1, 2, 3] or `['a','b','c','d'] |
When ever you want to perform a set of operations based on a condition or set of conditions, then If-Else/ Nested-If-Else are used.
main = do
let age = 21
if age > 18
then putStrLn "Adult"
else putStrLn "child"Function is a sub-routine which contains set of statements. Usually functions are written when multiple calls are required to same set of statements which increases re-usuability and modularity. Functions play an important role in Haskell, since it is a purely functional language.
multiply :: Integer -> Integer -> Integer --declaration of a function
multiply x1 x2 = x1 * x2 --definition of a function
main = do
putStrLn "Multiplication value is:"
print(multiply 10 5) --calling a function