Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why does the pointfree version of this function look like this?

I've been playing around with Haskell a fair bit, including practising writing functions in point-free form. Here is an example function:

dotProduct :: (Num a) => [a] -> [a] -> a
dotProduct xs ys = sum (zipWith (*) xs ys)

I would like to write this function in point-free form. Here is an example I found elsewhere:

dotProduct = (sum .) . zipWith (*)

However, I don't understand why the point-free form looks like (sum .) . zipWith (*) instead of sum . zipWith (*). Why is sum in brackets and have 2 composition operators?

like image 698
guhou Avatar asked Jun 26 '10 11:06

guhou


2 Answers

dotProduct xs ys = sum (zipWith (*) xs ys)             -- # definition

dotProduct xs    = \ys -> sum (zipWith (*) xs ys)      -- # f x = g <=> f = \x -> g
                 = \ys -> (sum . (zipWith (*) xs)) ys  -- # f (g x) == (f . g) x
                 = sum . (zipWith (*) xs)              -- # \x -> f x == f
                 = sum . zipWith (*) xs                -- # Precedence rule

dotProduct       = \xs -> sum . zipWith (*) xs         -- # f x = g <=> f = \x -> g
                 = \xs -> (sum .) (zipWith (*) xs)     -- # f * g == (f *) g
                 = \xs -> ((sum .) . zipWith (*)) xs   -- # f (g x) == (f . g) x
                 = (sum .) . zipWith (*)               -- # \x -> f x == f

The (sum .) is a section. It is defined as

(sum .) f = sum . f

Any binary operators can be written like this, e.g. map (7 -) [1,2,3] == [7-1, 7-2, 7-3].

like image 139
kennytm Avatar answered Oct 09 '22 08:10

kennytm


KennyTM's answer is excellent, but still I'd like to offer another perspective:

dotProduct = (.) (.) (.) sum (zipWith (*))
  • (.) f g applies f on the result of g given one argument
  • (.) (.) (.) f g applies f on the result of g given two arguments
  • (.) (.) ((.) (.) (.)) f g applies f on the result of g given three arguments
  • ...
  • Can do (.~) = (.) (.) (.), (.~~) = (.) (.) (.~), (.~~~) = (.) (.) (.~~) and now let foo a b c d = [1..5]; (.~~~) sum foo 0 0 0 0 results in 15.
    • But I wouldn't do it. It will probably make code unreadable. Just be point-full.
  • Conal's TypeCompose provides a synonym for (.) called result. Perhaps this name is more helpful for understanding what's going on.
    • fmap also works instead of (.), if importing the relevant instances (import Control.Applicative would do it) but its type is more general and thus perhaps more confusing.
  • Conal's concept of "fusion" (not to be confused with other usages of "fusion") is kind of related and imho offers a nice way to compose functions. More details in this long Google Tech Talk that Conal gave
like image 27
yairchu Avatar answered Oct 09 '22 08:10

yairchu