CODEWITHSUNDEEP
functionhaskelllambdafunction-composition
parker.sikand
parker.sikand

Reputation: 1381

Gap in my understanding of composition, types not matching

In my code I need to sort a list of (Int, Int)'s by the value of the second element.

It's easy enough to do sorted = sortBy (\(_,a) (_,b) -> compare a b) listOfPairs, but I hate writing lambda's like this and I need to use this same lambda in a few places in my code.

So I tried to create two helpful functions that I will end up using in many places as follows (and I couldn't find them in the prelude):

-- apply a function of one argument to two different arguments and return a pair
fBoth :: (a -> b) -> a -> a -> (b,b)
fBoth f a b = (f a, f b)

-- pass elements of a pair to a function of two arguments
expandPair :: (a -> b -> c) -> (a,b) -> c
expandPair f (a,b) = f a b

Now I thought I would be able to compose something together to pass to sortBy instead of an ugly "extractor" lambda. But I cant quite get the types to line up.

I feel like I want to compose (expandPair compare) with (fBoth snd), because :t expandPair compare = (a,a) -> Ordering and :t fBoth snd = (a,b) -> (a,b) -> (b,b). I would think that the resulting type of this composition would be (a,b) -> (a,b) -> Ordering which I can pass to sortBy, but it doesn't quite work.

If I try to do sortBy ((expandPair compare) . (fBoth snd)) [(1,2),(3,4)] it gives me type errors. But what confuses me is that if I do expandPair compare $ fBoth snd (1,2) (3,4) it actually works and yields LT as expected.

So clearly I'm not understanding something about function composition here... I get the whole "g composed with f = g(f(x))" but I'm having trouble making it work for me here.

Alternatively, if there's an even simpler way to accomplish this particular task of sorting a list of pairs by the second element, I'd be interested in hearing that as well.

Upvotes: 3

Views: 138

Answers (2)

Nicolas
Nicolas

Reputation: 24759

In the particular case of compare what your're looking an pplication of th on function from Data.Function:

>>> :t (`on` snd)
(`on` snd) :: (b -> b -> c) -> (a, b) -> (a, b) -> c

>>> :t (compare `on` snd)
(compare `on` snd) :: Ord b => (a, b) -> (a, b) -> Ordering

Upvotes: 0

bheklilr
bheklilr

Reputation: 54058

First of all, your expandPair function is literally the same definition as uncurry, which is in Prelude.

The problem here is that fboth snd takes 2 arguments, so the normal composition operator is not quite suited for this task. However, you can make a rather strange looking operator that lets you "compose" a function that takes two arguments with a function that takes 1 argument:

(.:) :: (c -> d) -> (a -> b -> c) -> a -> b -> d
(.:) = (.).(.)

The easy mnemonic for remembering this is that the function on the side with one dot takes 1 argument, of the same type as the output of the function that takes two arguments, which is on the side with two dots. You can then write this as

sortBy (uncurry compare .: fboth snd) [(1, 2), (3, 4)]

Now, I will say that it's best not to really think about how the .: operator works, just look at its type rather than its definition. It does come in handy fairly often, I use it pretty regularly and I certainly didn't come up with this operator.

You can also implement it as

> :m +Data.Function
> sortBy (compare `on` snd) ...
-- sortBy (on compare snd) ...

But as @mhwombat has pointed out, Data.Ord has an alias for on compare called comparing:

> :m +Data.Ord
> sortBy (comparing snd) ...

which is my preference.

Something that might make this operator a little more clear:

> :t (id .: (,))
a -> b -> (a, b)
> (id .: (,)) 1 2
(1, 2)
> (fst .: (,)) 1 2
1
> (snd .: (,)) 1 2
2
> (negate .: (+)) 1 2
-3

Upvotes: 7

Related Questions