CODEWITHSUNDEEP
haskellrecursion
Petr Stejskal
Petr Stejskal

Reputation: 21

Number of loops in recursion

I would like to count the number of positive integers/elements in the list. This returns the elements with positive values, how can I count the elements? would like to construct something like count(array(...)).

I would like to see a version with i++ and foldl. That would be very helpful.

countPositivesRec :: [Int] -> [Int]
countPositivesRec [] = []
countPositivesRec (x:xs) | x >= 0 = x : tl
                         | otherwise = tl
                           where tl = countPositivesRec xs

Upvotes: 0

Views: 303

Answers (3)

Will Ness
Will Ness

Reputation: 71070

You have

filtering p cons x r = if | p x -> cons x r | otherwise -> r

countPositives = length 
                   . filter (> 0)
               = foldr (\x r -> r + 1) 0                              -- r++
                   . foldr (filtering (> 0) (:)            ) []
               =     foldr (filtering (> 0) (\x r -> r + 1))  0

(since folds fuse by composing their reducer transformers, a-la "fold replaces the cons with a reducer operation, so why create the cons in the first place if it gonna be replaced anyway"), and

filtering (> 0) (\x r -> r + 1) x r 
                     = if | (> 0) x -> (\x r -> r + 1) x r | otherwise -> r
                     = if | x > 0 -> r + 1 | otherwise -> r

and thus, a version with fold and increment that you wanted,

countPositives = foldr (\x r -> if | x > 0 -> r + 1 | otherwise -> r) 0  -- r++

You can take it from here.

Upvotes: 1

Yann Vernier
Yann Vernier

Reputation: 15877

The function you've written is filter (>=0). As Paul pointed out, the only step remaining is to count and length does that. We can transform the function step by step:

countPositivesRec :: [Int] -> [Int]
countPositivesRec [] = []
countPositivesRec (x:xs) | x >= 0 = x : tl
                         | otherwise = tl
                           where tl = countPositivesRec xs

Observe that xs is only used in the transformed form tl. That's what makes this a right fold. 

onlypos1 = foldr maybekeep []
  where maybekeep x tl | x >= 0    = x : tl
                       | otherwise = tl

This operation is known as a filter, keeping only some parts:

onlypos2 = filter dowekeep
  where dowekeep x = x >= 0
onlypos3 = filter (\x -> x >= 0)
onlypos4 = filter (>= 0)

But this is of course only one of many possible approaches. For instance, strictness analysis can lead to the conclusion that length is better implemented as foldl' (\a _ -> succ a) 0 than foldr (\_ a -> succ a) 0. Indeed, that is its basic form in the Prelude:

length = foldl' (\c _ -> c+1) 0

We see that the combining function of length ignores the value of one argument, merely requires it to be there. This can naturally be merged with our condition that only some elements count:

lengthFilter1 = length . filter
lengthFilter2 pred = foldl' predCount 0
  where predCount c x = if pred x then c+1 else c
countNonNegative = lengthFilter2 nonNegative
  where nonNegative x = x >= 0

Incidentally, 0 isn't positive. It's non-negative.

In the end, Haskell's lazy lists mean we can use them to fuse traversals; length . filter (>=0) will only read the input list once, because the only reason it's processing results from filter is that length consumes them. The filtered list never exists as a fully expanded structure, unlike e.g. Python or PHP. This form is likely one of the most readable, but others exist, e.g.:

countNonNegatives xs = sum [1 | x <- xs, x >= 0]

Upvotes: 1

chi
chi

Reputation: 116139

Here's a hint: follow the same recursion scheme as before, but return an int at every step.

countPositivesRec :: [Int] -> Int
                              ---
countPositivesRec [] = 0 -- no positives in the empty list
countPositivesRec (x:xs) | x >= 0    = ??
                         | otherwise = ??
                          where tl = countPositivesRec xs

One you solve this, it can be rewritten using foldr, if you want.

If you really want to use foldl instead, I would suggest you start by defining a function f such that

f (f (f 0 x0) x1) x2

evaluates to the number of positives in x0,x1,x2. Then you can use foldl f 0 inputList

Upvotes: 1

Related Questions