CODEWITHSUNDEEP
haskell
Sir DK
Sir DK

Reputation: 179

Haskell :: Finding Min and Max for a set of Tuple

I've tried to find min and max for tuple. Here the code goes:

fFindMinMax :: (Ord a, Ord b, Ord c, Ord d) => [(a, b, c, d)] -> (Double,Double,Double,Double,Double,Double)
fFindMinMax [(_, x, y, z)] = (minimum x, maximum x, minimum y, maximum y, minimum z, maximum z)

And the errors come for maximum x, maximum y and maximum z.

Couldnt match expected type t1 Double with actual type b.

Can someone enlighten me?

Upvotes: 2

Views: 3185

Answers (2)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476659

First attempt

First of all, your current pattern:

fFindMinMax [(_, x, y, z)] = ...

means that it will only work if you pass a list with one element. So from the moment you pass an empty list, or a list with two or more elements, this will fail.

What you need is a map to obtain all the second/third/fourth elements of the tuples. We can do this with:

fFindMinMax cs = ...
    where cSnd = map (\(_,x,_,_) -> x) cs
          cThr = map (\(_,_,y,_) -> y) cs
          cFou = map (\(_,_,_,z) -> z) cs

So now the question is: what should we write as function predicate. You actually already made an attempt there that works: we can calculate the minimum cSnd and maximum cSnd and so on for every coordinate. So:

fFindMinMax cs = (minimum cSnd, maximum cSnd, minimum cThr, maximum cThr, minimum cFou, maximum cFou)
    where cSnd = map (\(_,x,_,_) -> x) cs
          cThr = map (\(_,_,y,_) -> y) cs
          cFou = map (\(_,_,_,z) -> z) cs

Now what is the type of the function? We do not have to restrict us to Double, nor do we have to make sure that all coordinates have the same type, the type signature of fFindMinMax can be:

fFindMinMax :: (Ord x, Ord y, Ord z) => [(a, x, y, z)] -> (x, x, y, y, z, z)
fFindMinMax cs = (minimum cSnd, maximum cSnd, minimum cThr, maximum cThr, minimum cFou, maximum cFou)
    where cSnd = map (\(_,x,_,_) -> x) cs
          cThr = map (\(_,_,y,_) -> y) cs
          cFou = map (\(_,_,_,z) -> z) cs

Note that this program will error if you give it an empty list, since the minimum or maximum of an empty list is not defined.

Improve memory consumption

A problem with the above solution is that we construct lists with the second, third and fourth element. Since we do not calculate the minimum and maximum at the same time, this means that we will end up storing this lists into memory.

We can improve the code by writing a helper function that calculates the minimum and the maximum concurrently for the same list:

{-# LANGUAGE BangPatterns #-}

minmax :: Ord a => [a] -> (a,a)
minmax [] = error "Empty list"
minmax (h:t) = minmax' h h t
    where minmax' a b [] = (a,b)
          minmax' !a !b (c:cs) = minmax' (min a c) (max b c) cs

How does this function works? Well the first line is rather straightforward: in case we are given an empty list, we can not calculate the minimum or the maximum, so we raise an error Empty list. In the latter case that list has a first item h and the rest of the items t. We consider h to be the thus far obtained minimum and maximum: if a list contains a single element, then that element is both the minimum and the maximum of that list. So we call an extra function minmax' :: Ord a => a -> a -> [a] -> a that calculates the minimum and maximum by giving it the minimum and maximum obtained thus far (h and h) and the remaining of the list.

Each iteration, it will take the next element c and calculate the minimum by calculated min with the thus far minimum a and the next element c, and calculate the maximum with the thus far maximum b and the next element c. We keep iterative doing this until we reach the end of the list. In that case the thus far obtained minimum and maximum are the final minimum and maximum. So we can return them as (a,b).

Then we can use the function like:

fFindMinMax :: (Ord x, Ord y, Ord z) => [(a, x, y, z)] -> (x, x, y, y, z, z)
fFindMinMax cs = (xmi, xma, ymi, yma, zmi, zma)
    where (xmi, xma) = minmax $ map (\(_,x,_,_) -> x) cs
          (ymi, yma) = minmax $ map (\(_,_,y,_) -> y) cs
          (zmi, zma) = minmax $ map (\(_,_,_,z) -> z) cs

Upvotes: 3

freestyle
freestyle

Reputation: 3790

Constant space solution

fFindMinMax :: (Ord x, Ord y, Ord z) => [(a, x, y, z)] -> (x, x, y, y, z, z)
fFindMinMax ((_, x, y, z):rest) = foldl' minmax (x, x, y, y, z, z) rest
fFindMinMax []                  = error "fFindMinMax: empty list"
  where
    (xMin', xMax', yMin', yMax', zMin', zMax') `minmax` (_, x, y, z) =
        let
          !xMin = min xMin' x
          !xMax = max xMax' x
          !yMin = min yMin' y
          !yMax = max yMax' y
          !zMin = min zMin' z
          !zMax = max zMax' z
        in (xMin, xMax, yMin, yMax, zMin, zMax)

Upvotes: 1

Related Questions