[Haskell-cafe] Composition and type magic

[Michael Orlitzky]

On 02/24/2015 12:57 AM, Sumit Sahrawat, Maths & Computing, IIT (BHU) wrote:
> Thanks.
> You've given me a good exercise in equational reasoning.
> 
> I'm studying such things because I might start studying combinatory logic
> (Smullyan's mockingbird book) soon.
> It's a good exercise for the mind, and is very enjoyable with pencil &
> paper.
> Can you give me some more patterns like transducers (foldl foldl) and the
> dot-dot-dot ( boobies, in your words :) ) example?
> 

I cheated with the pointfree tool, but you can do it by hand, too. The
only trick you need to know in this case is how to get the extra
argument on the end. You start with,

  conv xs = sum . zipWith (*) xs . reverse

and obviously, you want the 'xs' on the end. So you want to switch the
'zipWith (*) xs' and 'reverse' somehow. Well, you can always flip the
composition operator! Unfortunately it's no longer infix at that point,
so it has to be written like,

  conv xs = sum . (flip (.)) reverse (zipWith (*) xs)

Now the secret is that putting an extra dot around the chain of
functions takes it from a one-argument chain to a two-argument chain
(where the first function in the chain eats the second argument). You
can sort of see this in the type of 'sum' and '(sum .)':

  ghci> :t sum
  sum :: Num a => [a] -> a

  ghci> :t (sum .)
  (sum .) :: Num c => (a -> [c]) -> a -> c

The second one essentially eats an argument by taking "something that
will give me a list" instead of a list itself. You have to do the same
thing with the '(flip (.)) reverse' part of the chain:

  conv = (sum .) . (((flip (.)) reverse) .) zipWith (*)

Now, since you've got '((flip (.)) reverse' in parentheses anyway, you
can change it from a normal function application to a "section," i.e.
these two are the same: (flip (.)) reverse == (. reverse). So you wind
up with,

  conv = (sum .) . (((. reverse) .) zipWith (*)

Drop the useless parentheses,

  conv = (sum .) . (. reverse) . zipWith (*)

and now all that's left to do is pray that you aren't hanged for witchcraft.