CODEWITHSUNDEEP
haskell
Ara Vartanian
Ara Vartanian

Reputation: 1563

Functor Design Pattern in Haskell

I apologize for not coming up with a good title for this question. I'm having some trouble expressing what I need. I have a simple problem in Haskell and I am wondering what the best approach is to solve it.

Let's say I have a list of numbers: [-3,2,1,2]. I want to return the value with the highest absolute value. That is, I want to return -3. So I want:

f = maximum . map abs

The problem is, of course, that this returns the calculated value (3) and not the original value (-3).

I could figure out a way of doing this, maybe mapping the original list to a tuple of (originalValue, calculatdValue), finding the tuple whose snd is returned by my function (maximum) and then return fst of that tuple.

But this seems like a lot of "plumbing" for a simple problem like this, and I wonder if there is some abstraction I'm missing that solves this. That is, there is this generally procedure I do all the time, and I want some way of neatly doing it:

  1. I want to take a list of items.
  2. I want to map them to a certain value (let's say the absolute value)
  3. Then I want to select one based on some criteria (let's say I want the maximum or maybe the minimum).
  4. But then I want to return the original value. (If the list was [-3,2,1,2] and I want to return the value with the highest abs, then I would return -3).

Is there a library function for this? Is there a functor or a monad for this?

I think I want a function with the signature:

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

i.e.

f maximum abs [-3,2,1,2]

This feels very "functory" to me or maybe "monadic".

Upvotes: 10

Views: 790

Answers (6)

luqui
luqui

Reputation: 60513

If you are trying to have something ordered and compared by a projection always, rather than just at a specific usage (in which case see augustss's answer), then use a newtype wrapper:

newtype AbsInt = AbsInt Int

instance Eq AbsInt where
    AbsInt x == AbsInt y = abs x == abs y

instance Ord AbsInt where
    compare (AbsInt x) (AbsInt y) = compare x y

Now, for example:

maximum [AbsInt 1, AbsInt 10, AbsInt (-50)] = AbsInt (-50)

Presumably you would be working with AbsInt as your objects of study, so you wouldn't be writing those AbsInts everywhere.

The more operations you need on AbsInt, the more boilerplate you need. However if you just want to "pass through" some instances, GHC has an extension GeneralizedNewtypeDeriving that allows that; eg.:

{-# LANGUAGE GeneralizedNewtypeDeriving #-}

newtype AbsInt = AbsInt Int
    deriving (Num)

Now AbsInt behaves like an Int with regard to arithmetic, but (given the instances above) by absolute values with regard to comparison. Also note that the Num instance gives you the ability to use literals, so:

(maximum [1,2,-3] :: AbsInt) = AbsInt (-3)

Upvotes: 3

rampion
rampion

Reputation: 89113

Another way to do it, if the conversion is a bit expensive:

maximumWith :: (Ord b) => (a -> b) -> [a] -> a
maximumWith f = snd . maximumBy (compare `on` fst) . map (f &&& id)

This type is similar to GHC.Exts's sortWith, which gives us another way to do it:

maximumWith :: (Ord b) => (a -> b) -> [a] -> a
maximumWith f = head . sortWith (Down . f)

We can define a minimumWith similarly:

minimumWith :: (Ord b) => (a -> b) -> [a] -> a
minimumWith f = head . sortWith f

A look at the source for sortWith reveals that it's implemented by sortBy, so it lacks the caching that the first definition for maximumWith had.

This, obviously calls for some benchmarking:

module Main where
import Control.Arrow ((&&&))
import Data.List (sortBy)
import Data.Function (on)
import GHC.Exts (sortWith)
import Criterion.Main

sortWith :: (Ord b) => (a -> b) -> [a] -> [a]
sortWith f = map snd . sortBy (compare `on` fst) . map (f &&& id)

badFib :: Int -> Int
badFib 0 = 1
badFib 1 = 1
badFib n = badFib (n - 1) + badFib (n - 2)

main = defaultMain [ bench "GHC.Exts.sortWith" $ nf (GHC.Exts.sortWith badFib) [0..20]
                   , bench "Main.sortWith" $ nf (Main.sortWith badFib) [0..20]
                   ]

The results on my laptop:

benchmarking GHC.Exts.sortWith
collecting 100 samples, 12 iterations each, in estimated 1.504415 s
bootstrapping with 100000 resamples
mean: 1.264608 ms, lb 1.260519 ms, ub 1.270248 ms, ci 0.950
std dev: 24.42169 us, lb 19.21734 us, ub 31.50275 us, ci 0.950
found 8 outliers among 100 samples (8.0%)
  5 (5.0%) high mild
  3 (3.0%) high severe
variance introduced by outliers: 0.996%
variance is unaffected by outliers

benchmarking Main.sortWith
collecting 100 samples, 50 iterations each, in estimated 1.516733 s
bootstrapping with 100000 resamples
mean: 305.9089 us, lb 304.0602 us, ub 310.9257 us, ci 0.950
std dev: 14.41005 us, lb 6.680240 us, ub 30.26940 us, ci 0.950
found 18 outliers among 100 samples (18.0%)
  9 (9.0%) high mild
  9 (9.0%) high severe
variance introduced by outliers: 0.999%
variance is unaffected by outliers

Upvotes: 6

Dan Burton
Dan Burton

Reputation: 53715

Stop...hoogle time!

So you've got a list of stuff [a]. And you want to end up with just one of those a. You also want to compare elements of this list in some special way (not their natural ordering), in order to determine which comes first. This is the tricky part, but you should be able to see that what I've described is a function of the form a -> a -> Ordering.

Put it all together:

(a -> a -> Ordering) -> [a] -> a

And hoogle it. maximumBy and minimumBy are the first hits :) Hoogle can be a powerful asset when you learn to use it. (See augustss's answer for details on how to use maximumBy in this case)

Upvotes: 7

Ara Vartanian
Ara Vartanian

Reputation: 11

Here is something I cooked up. It's kind of meh, because it requires (Eq b)

selectOn :: (Eq b) => ([b] -> b) -> (a -> b) -> [a] -> a
selectOn reducer f list = head $ filter (\x -> f(x) == k ) list
  where k = reducer $ map f list

And then:

selectOn maximum abs [1,2,-3]

Or:

selectOn sum id [-3, 0, 3]

I guess I can generalize compare on and get the exact same effect.

Upvotes: 1

stonemetal
stonemetal

Reputation: 6208

I believe something along the lines of the following should work.

foldl abs_max (head xs) xs
 where abs_max x y = if (abs x) > (abs y) then x else y

Looking beyond the task at hand you could generalize it by abstracting out the comparison function and passing it in later.

Upvotes: 1

augustss
augustss

Reputation: 23014

Use maximumBy which takes a comparison function. You can then pass some function that compares the way you want.

maximumBy (compare `on` abs)

Upvotes: 20

Related Questions