CODEWITHSUNDEEP
haskell
Brian Yeh
Brian Yeh

Reputation: 3267

Beginner haskell code is totally incorrect

I'm really new to haskell. Tried to implement something really simple with recursion. A function that returns the index of the first matching value in a list. The code below won't work, not sure why, does anyone know How I could correct this code? 

linear_search :: (Eq a) => a -> [a] -> a
linear_search b w = linear_search_tail 0 b w
  where linear_search_tail :: (Eq a) => a -> a -> [a] -> a
        linear_search_tail x y [] = -1
        linear_search_tail x y (z:zs)
          | y == z = x
          | otherwise = linear_search_tail (x+1) y zs

main :: IO ()
main = print (linear_search 1 [2,5,4,3,7,3,1,2,3,4,5,7,8])

EDIT: Got it working. this is the correct code:

#!/usr/bin/env runghc

linear_search :: (Eq a) => a -> [a] -> Int
linear_search b w = linear_search_tail 0 b w
  where linear_search_tail :: (Eq a) => Int -> a -> [a] -> Int 
        linear_search_tail x y [] = -1
        linear_search_tail x y (z:zs)
              | y == z = x
              | otherwise = linear_search_tail (x+1) y zs

main :: IO ()
main = print (linear_search 1 [2,5,4,3,7,3,1,2,3,4,5,7,8])

Upvotes: 0

Views: 150

Answers (2)

chi
chi

Reputation: 116174

Let me add some comments on the corrected code:

linear_search :: (Eq a) => a -> [a] -> Int
linear_search b w = linear_search_tail 0 b w
  where linear_search_tail :: (Eq a) => Int -> a -> [a] -> Int 
        linear_search_tail x y [] = -1
        linear_search_tail x y (z:zs)
              | y == z = x
              | otherwise = linear_search_tail (x+1) y zs

In the auxiliary function, the second parameter y is passed around unchanged, so it's always equal to b. You can remove the parameter and directly use that:

linear_search :: (Eq a) => a -> [a] -> Int
linear_search b w = linear_search_tail 0 w
  where -- linear_search_tail :: (Eq a) => Int -> [a] -> Int 
        linear_search_tail x [] = -1
        linear_search_tail x (z:zs)
              | b == z    = x
              | otherwise = linear_search_tail (x+1) zs

(Here I had to remove/comment the inner type signature since Haskell interprets the inner a type variable to be independent from the outer a -- you can state that these are the same by enabling an extension, but let's keep it simple and just omit the signature.)

The above function returns -1 on error. This is not idiomatic in Haskell, where it is more common to return a Maybe Int, which is a type containing values representing integers Just 0, Just 1, Just 2, ... plus a distinct value Nothing that can be interpreted as "no result". If we use that we get:

linear_search :: (Eq a) => a -> [a] -> Maybe Int
linear_search b w = linear_search_tail 0 w
  where linear_search_tail x [] = Nothing
        linear_search_tail x (z:zs)
              | b == z    = Just x
              | otherwise = linear_search_tail (x+1) zs

Note that this will make life less convenient for the caller, which now gets its index wrapped in a Just box, or Nothing. This is actually a good thing, since now the caller can not easily forget to check for the "not found" case and use a plain integer pretending it's not -1. The caller is now forced to use something like

case linear_search 1 [2,3,4,5] of
   Just x  -> "Found at position " ++ x
   Nothing -> "Not found!"

Finally, note that the first line

linear_search b w = linear_search_tail 0 w

can also be written as

linear_search b = linear_search_tail 0

That is, you can omit the same variable(s) in the trailing position of a definition. This is called eta-reduction, and does not necessarily make your code look better. In this case, it's not helping much. I just mention it since you may see some code like this in the future.

After you learn some more Haskell, you might want to know how to exploit library functions for this. For instance, the elemIndex library function from Data.List performs the linear search you are trying to write. Alternatively,

linear_search :: (Eq a) => a -> [a] -> Maybe Int
linear_search x xs = case filter ((x ==) . snd) $ zip [0..] xs of
                     []       -> Nothing
                     (i, _):_ -> Just i

You probably find this unreadable right now, but you can go on with your learning and get back at this later on when you are more familiar with Haskell. In the meantime, writing recursive functions as you did is the right approach.

Upvotes: 3

zw324
zw324

Reputation: 27210

The code is searching for the index of a number, which means is should return an Int:

linear_search :: (Eq a) => a -> [a] -> Int

There's also a similar problem, see if you can find out!

linear_search_tail :: (Eq a) => Int -> a -> [a] -> Int

Upvotes: 3

Related Questions