list - 如何通过不使用 "list comprehensions"获取列表中元素的索引？

Question

我是haskell编程的新手，我尝试通过/不使用列表推导来解决问题。

问题是在列表中查找元素的索引并返回索引列表(找到列表中的元素的位置。)

我已经通过使用列表推导解决了这个问题，但是现在我在不使用列表推导的情况下解决了一些问题。

在我的递归方式上:

我试图压缩 [0..(length list)] 的列表和它自己的列表。
那么如果元素 a 等于列表中的一个元素 -> 使用压缩 list(my index) 的 Tupel 的第一个元素创建一个新列表然后以递归方式搜索函数，直到列表为[]。

这是我的列表理解(作品):

positions :: Eq a => a -> [a] -> [Int]
positions a list = [x | (x,y) <- zip [0..(length list)] list, a == y]

这是我的递归方式(不工作):

positions' :: Eq a => a -> [a] -> [Int]
positions' _ [] = []
positions' a (x:xs) =
    let ((n,m):ns) = zip [0..(length (x:xs))] (x:xs)
    in if (a == m) then n:(positions' a xs)
       else (positions' a xs) 

*对不起，我不知道如何突出显示单词

但 ghci 说:

*Main> positions' 2 [1,2,3,4,5,6,7,8,8,9,2]
[0,0]

它应该是这样的(我的列表理解):

*Main> positions 2 [1,2,3,4,5,6,7,8,8,9,2]
[1,10]

我的错误在哪里？

Answer 1

您尝试的问题很简单，就是当您说:

let ((n,m):ns) = zip [0..(length (x:xs))] (x:xs)

然后 n将永远是 0 .那是因为你正在匹配 (n,m)反对 zip [0..(length (x:xs))] (x:xs)的第一个元素，它必然总是 (0,x) .

这本身不是问题——但这确实意味着您必须正确处理递归步骤。你现在的样子， positions _ _ ，如果非空，将始终有 0作为它的第一个元素，因为允许它找到匹配项的唯一方法是它是否位于列表的开头，从而导致索引为 0 .这意味着您的结果将始终是正确长度的列表，但包含所有元素 0 - 如你所见。

问题不在于您的递归方案，而是与您没有修改结果以说明您并不总是想要 0 的事实有关。添加到结果列表的前面。由于每个递归调用只是将 1 添加到您要查找的索引，您需要做的就是 map增量函数 (+1)在递归结果上:

positions' :: Eq a => a -> [a] -> [Int]
positions' _ [] = []
positions' a (x:xs) =
    let ((0,m):ns) = zip [0..(length (x:xs))] (x:xs)
    in if (a == m) then 0:(map (+1) (positions' a xs))
       else (map (+1) (positions' a xs))

(请注意，我已将您的 let 更改为明确表示 n 将始终为 0 - 我更喜欢这样明确，但这本身不会改变输出。)因为 m总是绑定(bind)到 x和 ns根本不用，我们可以省略let，内联 m的定义:

positions' :: Eq a => a -> [a] -> [Int]
positions' _ [] = []
positions' a (x:xs) =
    if a == x
    then 0 : map (+1) (positions' a xs)
    else     map (+1) (positions' a xs)

您可以继续排除重复的 map (+1) (positions' a xs)如果你想。

顺便说一句，您不需要显式递归来避免此处的列表理解。一方面，列表推导基本上是对 map 使用的替代。和 filter .我打算明确地写出来，但我看到@WillemVanOnsem 已经给出了这个答案，所以我会简单地将你推荐给他的答案。

另一种方法，虽然如果你被要求自己实现这个可能是 Not Acceptable ，那就是只使用内置的 elemIndices函数，这正是您在此处尝试实现的功能。