CODEWITHSUNDEEP
haskellrecursiontail-recursion
Soulzityr
Soulzityr

Reputation: 456

Haskell - Basic Tail Recursion

I have a function that has parameters

whatIndex ::  (Eq a) => a -> [a] -> Integer

where I return the index of a inside [a], starting at 0, or return -1 if it's not found. This is what I wrote

module WhatIndex where

whatIndex ::  (Eq a) => a -> [a] -> Integer

whatIndex p [] = -1

whatIndex p (a:as) 
    | p==a = index
    | otherwise = whatIndex p as
    where index = 1+whatIndex p as

Obviously, I'm not correctly increasing index here. Any idea why this isn't working? Also, I cannot change parameters.

========================

Here is some basic input/output

whatIndex 3 [] = -1
whatIndex 2 [1,2,3,2,1]=1
whatIndex 1 [1,2,3,2,1]=0
whatIndex 'b' ['a' .. 'z']=1

Upvotes: 0

Views: 796

Answers (2)

user903589
user903589

Reputation:

1+whatIndex p as will go through all of the remaining list and count them, it won't give you the index. Just use an iterative recursive helper function like this...

You can use either a local function, or the lifted version, which is what I have here.

whatIndex' ::  (Eq a) => Integer -> a -> [a] -> Integer

whatIndex' _ _ [] = -1

whatIndex' i p (x:xs) 
    | p == x = i
    | otherwise = whatIndex' (i+1) p xs

whatIndex p xs = whatIndex' 0 p xs

main = print $ whatIndex 'a' "bbbbaccc"

Here's a non tail-recursive version:

whatIndex p (x:xs)
    | p == x = 0
    | otherwise = 1 + whatIndex p xs

Tail recursion refers to a class of recursive functions where the "last" or "final" function call in a recursive function is to the function itself. So that means that the function is not calling some other function (like +) in the "tail position" (the last place where a function call takes place). You can clearly see that the final function that is called in the first version of whatIndex is whatIndex whereas the final function that is called in the second version (with a call to whatIndex as a parameter) is +.

http://en.wikipedia.org/wiki/Tail_call

Edit: here's a version that corresponds more closely with your specification, although it's a bit convoluted and inefficient.

whatIndex p xs 
    | not (any (==p) xs) = -1
    | otherwise = whatIndex' p xs where
        whatIndex' p (x:xs)
            | p == x = 0
            | otherwise = 1 + whatIndex' p xs

Upvotes: 5

Pubby
Pubby

Reputation: 53017

Try using an accumulator parameter if you want tail recursion:

whatIndex :: (Eq a) => a -> [a] -> Integer
whatIndex =
  let whatIndex' count p [] = -1
      whatIndex' count p (a:as)
        | p==a = count
        | otherwise = whatIndex' (count + 1) p as
  in whatIndex' 0

Upvotes: 3

Related Questions