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])1 Answer
From what I understand about your binary search implementation, you want to get the index of a particular element in a list. Because the type signature of binarySearch returns Maybe Int where I assume Int should be the index.
If that's the case, I believe in the line of code:
in if (isNothing recurse) then Nothing else (Just (centerValue + (fromJust recurse)))You are trying to calculate the correct index. But you are using centerValue, the content which is of type a, instead of the index, which should be of type Int. You probably need to define a centerValueIndex in addition to centerValue. This should solve your compilation error.
However, I also noticed another problem in your implementation, I don't want to spoil the fun for yourself to find it, but just as a hint, the problem is in the split implementation.
I myself only know very little Haskell, but hope this could help.
