如何从Haskell列表中选择多个元素

发布于 2025-02-12 16:48:54 字数 292 浏览 0 评论 0原文

在Haskell中，我知道如何从索引列表中从列表中选择一个元素：

head (drop idx myList)

但是我有一个索引myIndices（例如[1,3,5]），并希望在myIndices中的索引位置返回myList中的元素列表。

在一种非功能性语言中，我将通过循环构建列表，但是如何在Haskell中“构建”新列表？我可以使用过滤器吗？

原文

In Haskell I know how I can pick one element from a list by index :

head (drop idx myList)

But I have a list of indices myIndices (like [1,3,5]) and want to return a list of the elements in myList at the index positions in myIndices.

In a non-functional language I would build up the list over a loop, but how do I "build" the new list in Haskell? Can I use a filter?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

习ぎ惯性依靠 2025-02-19 16:48:54

首先，让我添加我的标准说明，如果您发现自己在列表中考虑索引，则应重新考虑整个方法。最好将列表视为值的 streams ，在这些列表中，您从不真正关心绝对位置，而只关心价值观，可能是它们的相对顺序。如果您确实需要索引，则可能应该使用vector s而不是列表。

但是好。如果您以命令式语言使用循环进行某些任务，那么明显的方法始终是在功能语言中使用递归。通常，这不是最简洁，可靠或高效的选择，但这是始终可能的，您当然应该练习如何做。

基本上，您可以编写一个具有i参数的go函数，该函数对每个递归调用都“递增”，就像 loop中的中的计数器变量一样，结果只是一个列表，当i位于索引列表中时，纯准备元素就可以构建。确实将其作为练习。

但是，是的，您也可以改用过滤器。诀窍是，您只需将该信息添加到列表中，而不是手动维护计数器变量。实际上，即使在

for i,x in enumerate(myList):
    ...

Haskell的Python中，这通常是这样做的，这要归功于懒惰的评估，枚举不需要任何特殊的魔术，但可以作为简单的列表zip表示：实际上，上面的Python Loop可以用io monad写成，

forM_ (zip [0..] myList) $ \(i,x) -> do
    ...

但是在这里，您实际上并不想在列表上 loop ，但实际上是在列表上过滤。即，您要保留所有索引属于请求索引列表的元素：

  [ x | (i,x) <- zip [0..] myList, i`elem`myIndices ]

请注意，elem的性能不佳：它将通过 all> ALL 请求的索引对于myList中的所有元素，而如果对MyIndices进行排序，则仅检查HEAD元素就足够了。这就是您在递归解决方案中可以做得更好的，或者通过使用state monad弹出使用的索引。

但是一种更好的方法是从索引列表中创建一个“掩码”列表true] 。这可以通过手动递归或这样的技巧再次完成：

indicesAsMask :: [Int]  -- Must be strictly sorted
              -> [Bool]
indicesAsMask ixs@(0:_) = True : do
   (il, ir) <- zip ixs $ tail ixs
   replicate (ir - il - 1) False ++ [True]
indicesAsMask ixs = False : tail (indicesAsMask $ 0:ixs)

然后，您可以简单地将列表与掩码一起扎在一起，然后滤除掩码值为true的元素。

First let me add my standard remark that if you find yourself thinking about indices in a list you should reconsider your entire approach. It's better to think of lists as streams of values, where you never really care about absolute position but only about the values and possibly their relative order. If you really need indices, you should probably be using Vectors instead of lists.

But ok. If you would use a loop for some task in an imperative language, the obvious approach is always to use recursion in a functional language. Often it's not the most concise, reliable or efficient option, but it's what is always possible and you should certainly practice how to do it.

Basically you write a go function that has an i argument which is “incremented” for each recursive call much like the counter variable in a for loop, and the result is just a list which is build by purely prepending elements when i is in the indices list. Do implement this as an exercise.

But, yes, you could also use filter instead. The trick is that instead of manually maintaining a counter variable, you just add that information to the list as it were. In fact that's something often done even in Python

for i,x in enumerate(myList):
    ...

In Haskell, thanks to lazy evaluation, enumerate doesn't need any special iterable magic but can be expressed as a simple list zip: in fact the above Python loop could be written in e.g. the IO monad as

forM_ (zip [0..] myList) $ \(i,x) -> do
    ...

But here you don't really want to loop over the list, only, indeed, filter on it. Namely, you want to retain all the elements whose index is in the list of requested indices:

  [ x | (i,x) <- zip [0..] myList, i`elem`myIndices ]

Note that elem has bad performance though: it'll go through all the requested indices for all elements in myList, whereas if myIndices is sorted it would be enough to check only the head element. That's what you could do better in a recursive solution, or alternatively by using the State monad to pop the used indices.

But a rather nicer approach is to create a “masking” list from the list of indices, i.e. turning [1,3,5] into [False, True, False, True, False, True]. This could again be done with manual recursion, or with a trick like this:

indicesAsMask :: [Int]  -- Must be strictly sorted
              -> [Bool]
indicesAsMask ixs@(0:_) = True : do
   (il, ir) <- zip ixs $ tail ixs
   replicate (ir - il - 1) False ++ [True]
indicesAsMask ixs = False : tail (indicesAsMask $ 0:ixs)

Then you can simply zip your list together with the mask, and filter out those elements whose mask value is True.

回复收藏 0 原文

浅沫记忆 2025-02-19 16:48:54

如果您知道这些索引没有限制，则可以接受

fmap (myList !!) myIndices

myList在myindices中的每个索引都可以索引。得到一个运行时例外：

myList = ["a", "b", "c", "d"]
myIndices = [1,2,3,10]
fmap (myList !!) myIndices
["b","c", "d","*** Exception: Prelude.!!: index too large

如果您想在这方面保持强大

concat $ fmap (\i -> take 1 $ drop i $ myList) myIndices

如果没有，您会代码> myList 或一个空列表，如果myList还不够长； concat平列列表列表。

可以使用Monadic Bind Operator ＆gt;＆gt; =更紧凑地编写上述方法：

myIndices >>= (\i -> take 1 $ drop i $ myList)

该方法的缺点是它运行以每一个为单位单个索引，这意味着您多次遍历myList，因此给出了复杂性 o（m*n） m indices和列表中的 n elsemts，而原则上只能做一次，如另一个答案所示。（在这里进行更多详细信息。）。 >是。

If you know the indices are not out of bound, you can go with

fmap (myList !!) myIndices

This requires that myList be indexable at every index in myIndices. If not, you get a runtime exception:

myList = ["a", "b", "c", "d"]
myIndices = [1,2,3,10]
fmap (myList !!) myIndices
["b","c", "d","*** Exception: Prelude.!!: index too large

If you want to be robust in that respect, you can take a slightly different approach:

concat $ fmap (\i -> take 1 $ drop i $ myList) myIndices

Here each index i is turned into a list containing the one corresponding element from myList or an empty list if myList is not long enough; the resulting list of lists is flattened by concat.

The above can be written more compactly using the monadic bind operator >>=:

myIndices >>= (\i -> take 1 $ drop i $ myList)

The drawback of this approach is that it runs take 1 $ drop i $ myList for every single index, meaning that you traverse myList multiple times, thus giving a complexity O(m*n) for m indices and n elemnts in the list, whereas you could do it only once, in principle, as shown in the other answer. (More details here.) Whether such a complexity is acceptable, clearly depends how big m*n is.

回复收藏 0 原文

~没有更多了~