CODEWITHSUNDEEP
haskellrecursion
CYC
CYC

Reputation: 629

Do recursion and counting numbers at the same time in Haskell

If I had a known list A :: [Int], and wanted to get a new list B = newList A with newList defined as the following:

newList :: [Int] -> [Int]
newList [] = []
newList (a:as) | a==0      = f(a) : newList (as)
               | a==1      = g(a) : newList (as)
               | otherwise = h(a) : newList (as)

where f, g, h :: Int -> Int are unimportant functions.

Other than B, I also wanted to know how many 0, 1 are there in A respectively.

But since when producing B recursively, it has already checked whether a== (0 or 1) for each elements in A, so it's a redundancy to check it again separably.

Is it possible to get B but at the same time get how many 0, 1 are there in A with checking only once?

Upvotes: 2

Views: 113

Answers (1)

effectfully
effectfully

Reputation: 12715

This is not an answer you are looking for, but there is a nice abstract structure behind your function, so I'll leave it here:

import Data.Monoid
import Data.Functor
import Data.Traversable
import Control.Arrow
import Control.Monad.Trans.Writer

wr :: Int -> Writer (Sum Int, Sum Int) Int
wr 0 = tell (Sum 1, Sum 0) $> f 0
wr 1 = tell (Sum 0, Sum 1) $> g 1
wr n = return $ h n

collect :: [Int] -> ([Int], (Int, Int))
collect = second (getSum *** getSum) . runWriter . traverse wr

Summing is a monoid, double summing is a monoid, the Writer monad handles monoids, traverse maps a list with an effectful function and performs all effects.

This:

f = (+ 1)
g = (+ 2)
h = (+ 3)

main = print $ collect [0, 1, 2, 3, 0, 0, 0, 4, 1]

prints ([1,3,5,6,1,1,1,7,3],(4,2)) — four zeros and two ones.

Upvotes: 4

Related Questions