2

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])
3
  • 4
    Note that should you succeed, your search will require O(n) bookkeeping on top of the O(log n) comparisons. Lists in Haskell are singly linked lists! If you want to play with binary search, you should probably use Array (Data.Array) or Vector (Data.Vector), or perhaps Seq (Data.Sequence). Commented May 24, 2015 at 20:06
  • Ah, thanks for the tip. Most of the beginning text only teach lists. Commented May 24, 2015 at 20:25
  • Well, you can certainly write balanced search trees, tries, and other such searchable things, or of course use the ones available in various packages. Commented May 25, 2015 at 1:21

1 Answer 1

3

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.

Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.