0

我正在尝试编写一个函数来使用尾递归查找给定元素的索引。假设列表包含1通过的数字10，并且我正在搜索5，那么输出应该是4。我遇到的问题是使用尾递归“计数”。但是，我什至不确定在这种情况下是否需要手动“计算”递归调用的数量。我尝试使用!!which 没有帮助，因为它返回特定位置的元素。我需要该函数来返回特定元素的位置（正好相反）。

我一直试图弄清楚这个已经一个小时了。

代码：

  whatIndex a [] = error "cannot search empty list"
  whatIndex a (x:xs) = foo a as
    where
       foo m [] = error "empty list"
       foo m (y:ys) = if m==y then --get index of y
                         else foo m ys

注意：我试图在不使用库函数的情况下实现这一点

4

2 回答 2

5

您的辅助函数需要额外的计数参数。

whatIndex a as = foo as 0
  where
    foo [] _ = error "empty list"
    foo (y:ys) c
        | a == y    = c
        | otherwise = foo ys (c+1)

顺便说一句，给这个函数一个Maybe返回类型而不是使用错误是更好的形式。这elemIndex也是有充分理由的。这看起来像

whatIndex a as = foo as 0
  where
    foo [] _ = Nothing
    foo (y:ys) c
        | a == y    = Just c
        | otherwise = foo ys (c+1)
于 2013-02-13T00:20:15.570 回答
3

注意：我试图在不使用库函数的情况下实现这一点

一般来说，这不是一个好主意。一个更好的练习是这样的：

  1. 弄清楚如何使用库函数来实现它。
  2. 弄清楚如何自己实现您在步骤 1 中使用的任何库函数。

通过这种方式，您将学习三个关键技能：

  • 什么是标准库函数，以及它们何时有用的示例。
  • 如何将问题分解成更小的部分
  • 如何编写库中的基本功能。

但是，在这种情况下，您的函数与中whatIndex的函数或多或少相同，因此您的问题归结为编写您自己的此库函数版本。elemIndexData.List

这里的诀窍是你想在递归列表时增加一个计数器。编写尾递归函数有一种标准技术，称为累积参数。它是这样工作的：

  1. 你编写了一个辅助函数，与“前端”函数相比，它需要一个额外的参数（或更多）来跟踪额外的信息。
  2. 然后，您将“真实”函数定义为对辅助函数的调用。

因此对于elemIndex，辅助函数将是这样的（i作为当前元素索引的累积参数）：

-- I'll leave the blanks for you to fill.
elemIndex' i x []      = ...
elemIndex' i x (x':xs) = ...

那么“驱动程序”函数是这样的：

elemIndex x xs = elemIndex 0 x xs

但是这里我必须提到一个严重的问题：让这个函数在 Haskell 中表现良好是很棘手的。尾递归在严格（非惰性）函数式语言中是一个有用的技巧，但在 Haskell 中则不然，因为：

  1. Haskell 中的尾递归函数仍然可以破坏堆栈，
  2. 非尾递归函数可以在恒定空间中运行。

我的这个较旧的答案显示了第二点的一个例子。

因此，在您的情况下，非尾递归解决方案可能是您可以提供的最简单的解决方案，它将在恒定空间中运行（即，不要在长列表中破坏堆栈）：

elemIndex x xs = elemIndex' x (zip xs [0..])

elemIndex' x pairs = snd (find (\(x', i) -> x == x') pairs)

-- | Combine two lists by pairing together their first elements, their second 
-- elements, etc., until one of the lists runs out.
--
-- EXERCISE: write this function on your own!
zip :: [a] -> [b] -> [(a, b)]
zip xs ys = ...

-- | Return the first element x of xs such that pred x == True.  Returns Nothing if
-- there isn't one, Just x if there is one.
--
-- EXERCISE: write this function on your own!
find :: (a -> Bool) -> [a] -> Maybe a
find pred xs = ...
于 2013-02-13T00:43:54.340 回答