Haskell - 基本尾递归

Question

我有一个具有参数的函数

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

我返回内部[a]的索引,从0开始,或者如果找不到则返回-1.这就是我写的

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

显然,我在这里没有正确增加索引.知道为什么这不起作用吗？另外,我无法更改参数.

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

这是一些基本的输入/输出

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

Answer 1

1+whatIndex p as将通过所有剩余的列表并计算它们,它不会给你索引.只需使用这样的迭代递归辅助函数......

您可以使用本地功能或提升版本,这是我在这里.

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"

这是一个非尾递归版本:

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

尾递归是指一类递归函数,其中递归函数中的"last"或"final"函数调用是函数本身.这意味着该函数不会+在"尾部位置"(函数调用发生的最后位置)中调用其他函数(如).您可以清楚地看到在第一个版本中调用的最终函数whatIndex是,whatIndex而在第二个版本中调用的最终函数(调用whatIndex作为参数)是+.

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

编辑:这是一个与您的规范更紧密对应的版本,虽然它有点复杂和低效.

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