CODEWITHSUNDEEP
haskellrecursiontuples
danielnovais92
danielnovais92

Reputation: 633

Recursion With Tuples in Haskell

I want to define a simple function in Haskell:

    nzp :: [Int] -> (Int,Int,Int)

that accepts a list of integers as input and returns a triple (a,b,c) where a is the amount of numbers in the list less than 0, b is the amount equal to 0 and c is the amount higher than zero. For example, 

    nzp [3,0,-2,0,4,5] = (1,2,3)

I have to define this function recursively and I can only traverse the list once. How can I do this? I can't seem to grasp the concept of recursively creating a tuple.

Most Regards

Upvotes: 1

Views: 3869

Answers (5)

fp_mora
fp_mora

Reputation: 714

I am a little over a couple of months into Haskell. A helper/auxilliary function would make running this solution easier. 

s3 [] (l,g,z) = (l,g,z)
s3 (x:xs) (l,g,z) = if      x<0
                    then        (s3 xs (l+1,g,z))
                    else if x>0
                         then   (s3 xs (l,g+1,z))
                         else   (s3 xs (l,g,z+1))

This is run with s3 [1,0,-2,3,4,-7,0,-8] (0,0,0) producing (3,3,2).

Just about any primitive recursive function can be translated into a fold.

Upvotes: 1

not my job
not my job

Reputation: 672

Here are some pointers:

  1. To use recursion to build up a value, you need to pass the previous version of the value as an argument, so write

    nzp_helper :: [Int] -> (Int,Int,Int) -> (Int, Int, Int)

  2. Decide what the answer is when the list is empty

    nzp_helper [] runningTotals = -- what's the answer if the list is empty?

  3. Decide what the answer is when there's something in the list

    nzp_helper (i:is) (negatives, positives, zeros) = 
      | i < 0 = -- write stuff here
      | i == 0 = -- I hope you're getting the idea

  4. Kick the whole thing off by defining nzp using nzp_helper.

    nzp is = nzp_helper is -- one final argument - what?

Upvotes: 5

Lee
Lee

Reputation: 144136

Instead of thinking of trying to create a single tuple recursively, you should think about updating an existing tuple containing the counts based on given value. This function would look something like:

update :: (Int, Int, Int) -> Int -> (Int, Int, Int)
update (l,e,g) x | x < 0 = (l+1, e, g)
update (l,e,g) x | x == 0 = (l, e+1, g)
update (l,e,g) x | x > 0 = (l, e, g+1)

Then you can traverse the input list using foldl and accumulate the output tuple:

nzp :: [Int] -> (Int, Int, Int)
nzp = foldl update (0,0,0)

EDIT: As @leftroundabout points out in the comments, you should avoid using foldl since it can lead to space leaks - you can find an explanation in Real World Haskell. You can use the strict version of foldl, foldl' in Data.List

import Data.List
nzp = foldl' update (0,0,0)

Upvotes: 3

karakfa
karakfa

Reputation: 67507

New to Haskell too! Perhaps not proper but here is my solution which works. Define an auxiliary function that accumulates the n,z, and p values

let f (x:xs, (n, z, p)) | x < 0 = f (xs, (n+1, z, p))
                        | x == 0 = f (xs, (n, z+1, p))
                        | otherwise = f (xs, (n, z, p+1))
    f ([], (n, z, p)) = ([], (n, z, p))

and define nzp in terms of the auxiliary function

 let nzp x = snd $ f (x,(0,0,0))

to verify

Prelude> nzp [-1,1,1,-1,0]
(2,1,2)

Upvotes: 1

leftaroundabout
leftaroundabout

Reputation: 120711

I can't seem to grasp the concept of recursively creating a tuple.

I shouldn't think so – in fact, it's impossible! (At least not without GHC extension havoc.)

No, you need to create a tuple in one go. The important thing needed for your function: since you may only traverse the list once, you need to pull through the entire tuple at once as well. As this is apparently homework, I shall instead show how it works with a fold (that is in fact preferrable, but translates quite directly to recursion):

nzp = foldr switchIncr (0,0,0)
 where switchIncr x (negatives, zeroes, positives)
         | x<0        = (succ negatives, zeroes, positives)
         | x==0       = (negatives, succ zeroes, positives)
         | otherwise  = (negatives, zeroes, succ positives)

Upvotes: 2

Related Questions