I'm trying to learn haskell and implement some basic algorithms in haskell. I'm getting this type message that I don't completely understand. For the code below, the function takes a value and a list and returns an index for a matching value in the list:
#!/usr/bin/env runghc
import Data.Maybe (isNothing, fromJust)
binarySearch :: (Ord a) => a -> [a] -> Maybe Int
binarySearch x [] = Nothing
binarySearch x [y]
| x == y = Just 0
| otherwise = Nothing
binarySearch x ys
| x < centerValue = binarySearch x (fst splitted)
| x >= centerValue = let recurse = binarySearch x (snd splitted)
in if (isNothing recurse) then Nothing else (Just (centerValue + (fromJust recurse)))
where split :: (Ord a) => [a] -> ([a], [a])
split [] = ([],[])
split [x] = ([x], [])
split x = ((take halfIndex x), (take rhalfIndex (reverse x)))
where myLength = length x
halfIndex = myLength `div` 2
rhalfIndex = myLength - halfIndex
splitted = split ys
centerValue = head (snd splitted)
main :: IO()
main = print(binarySearch 5 [1,2,3,4,5])
I get the error message:
binarySearch.hs:12:77:
Couldn't match expected type ‘Int’ with actual type ‘a’
‘a’ is a rigid type variable bound by
the type signature for
binarySearch :: Ord a => a -> [a] -> Maybe Int
at binarySearch.hs:4:17
Relevant bindings include
centerValue :: a (bound at binarySearch.hs:21:11)
splitted :: ([a], [a]) (bound at binarySearch.hs:20:11)
ys :: [a] (bound at binarySearch.hs:9:16)
x :: a (bound at binarySearch.hs:9:14)
binarySearch :: a -> [a] -> Maybe Int
(bound at binarySearch.hs:5:1)
In the first argument of ‘(+)’, namely ‘centerValue’
In the first argument of ‘Just’, namely
‘(centerValue + (fromJust recurse))’
Not sure what's going on. Does anyone know the correction I should make and why?
Edit, the corrected code is below:
#!/usr/bin/env runghc
import Data.Maybe (isNothing, fromJust)
split :: (Ord a) => [a] -> ([a], [a])
split [] = ([],[])
split [x] = ([x], [])
split x = ((take halfIndex x), (drop halfIndex x))
where myLength = length x
halfIndex = myLength `div` 2
binarySearch :: (Ord a) => a -> [a] -> Maybe Int
binarySearch x [] = Nothing
binarySearch x [y]
| x == y = Just 1
| otherwise = Nothing
binarySearch x ys
| x < centerValue = binarySearch x (fst splitted)
| x >= centerValue = let recurse = binarySearch x (snd splitted)
in if (isNothing recurse)
then Nothing
else (Just (centerValueIndex + (fromJust recurse)))
where splitted = split ys
centerValue = head (snd splitted)
centerValueIndex = (length ys) `div` 2
main :: IO()
main = print(binarySearch 8 [1,2,3,4,5,8])
Array(Data.Array) orVector(Data.Vector), or perhapsSeq(Data.Sequence).