Clever Geek Handbook

How to deal with previous items when matching a list?

I am stuck creating a function in Haskell that should do the following:

For each integer in the list, check how many integers before it are smaller.

smallerOnes [1,2,3,5] will have the result [(1,0), (2,1), (3,2), (5,3)]

At the moment I have:

smallerOnes :: [Int] -> [(Int,Int)]
smallerOnes [] = []
smallerOnes (x:xs) =

I have no information on how to fix this problem. Recursion is probably the way of thinking here, but at this point I am losing it.

0


source to share


2 answers 


import Data.List (inits)
smallerOnes :: [Int] -> [(Int,Int)]
smallerOnes xs = zipWith (\x ys -> (x, length $ filter (< x) ys)) xs (inits xs)


+3


source


It is useful here not to start with the base case, but with the main case.

Imagine that we have already processed half of the list. Now we are faced with the rest of the list, say x:xs

. We want to know how many "before" integers are less x

; so we need to know these elements, say ys

: length [y | y<-ys, y<x]

will be the answer.

Therefore, you will need to use an internal function that will maintain the prefix ys

, create a result for each x

and return them to the list:

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 []     = []

This can also be coded using some higher order builtins like



scanl :: (a -> b -> a) -> a -> [b] -> [a]

which will need some post-processing (for example map snd

or whatever) or more directly with

mapAccumL :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y])

mapAccumL

located inData.List

.

+4


source






More articles:


All Articles