在对列表进行映射时，如何考虑以前的元素？
在对列表进行映射时，如何考虑以前的元素？
提问于 2014-10-14 09:23:21
我被困在Haskell的一个函数中，必须做以下几件事：
对于列表中的每个整数，检查它前面有多少个整数较小。
smallerOnes [1,2,3,5] will have the result [(1,0), (2,1), (3,2), (5,3)]现在我有：
smallerOnes :: [Int] -> [(Int,Int)]
smallerOnes [] = []
smallerOnes (x:xs) = 我对如何解决这个问题一无所知。递归可能是这里的思维方式，但在那个时候，我失去了它。
回答 2
Stack Overflow用户
回答已采纳
发布于 2014-10-14 09:51:04
import Data.List (inits)
smallerOnes :: [Int] -> [(Int,Int)]
smallerOnes xs = zipWith (\x ys -> (x, length $ filter (< x) ys)) xs (inits xs)Stack Overflow用户
发布于 2014-10-14 09:34:33
在这里，不是从基本情况开始，而是从主要情况开始是有益的。
想象一下我们已经处理了一半的名单。x:xs说，现在我们面临的是列表中的其余部分。我们想知道“在它之前”有多少个整数比x小；所以我们需要知道这些元素，比如ys：length [y | y<-ys, y<x]。
因此，您需要使用一个内部函数来维护前缀ys，为每个x生成结果并在列表中返回它们：
smallerOnes :: [Int] -> [(Int,Int)]
smallerOnes [] = []
smallerOnes xs = go [] xs
where
go ys (x:xs) = <result for this x> : <recursive call with updated args>
go ys [] = []这也可以使用一些内置的高阶函数进行编码。
scanl :: (a -> b -> a) -> a -> [b] -> [a]需要一些后置处理(比如map snd或其他什么)，或者更直接地使用
mapAccumL :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y])页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/26357098
复制相关文章
相似问题
腾讯云开发者
