Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.1k views
in Technique[技术] by (71.8m points)

haskell - How can I understand "(.) . (.)"?

I believe I understand fmap . fmap for Functors, but on functions it's hurting my head for months now.

I've seen that you can just apply the definition of (.) to (.) . (.), but I've forgot how to do that.
When I try it myself it always turns out wrong:

(.) f g = x -> f (g x)
(.) (.) (.) = x -> (.) ((.) x)
x f -> (.) ((.) x) f
x f y  -> (((.)(f y)) x)
x f y g-> (((.)(f y) g) x)
x f y g-> ((f (g y)) x)
x f y g-> ((f (g y)) x):: t2 -> (t1 -> t2 -> t) -> t3 -> (t3 -> t1) -> t

If "just applying the definition" is the only way of doing it, how did anybody come up with (.) . (.)?
There must be some deeper understanding or intuition I'm missing.

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

Coming up with (.) . (.) is actually pretty straightforward, it's the intuition behind what it does that is quite tricky to understand.

(.) gets you very far when rewriting expression into the "pipe" style computations (think of | in shell). However, it becomes awkward to use once you try to compose a function that takes multiple arguments with a function that only takes one. As an example, let's have a definition of concatMap:

concatMap :: (a -> [b]) -> [a] -> [b]
concatMap f xs = concat (map f xs)

Getting rid of xs is just a standard operation:

concatMap f = concat . map f

However, there's no "nice" way of getting rid of f. This is caused by the fact, that map takes two arguments and we'd like to apply concat on its final result.

You can of course apply some pointfree tricks and get away with just (.):

concatMap f = (.) concat (map f)
concatMap f = (.) concat . map $ f
concatMap = (.) concat . map
concatMap = (concat .) . map

But alas, readability of this code is mostly gone. Instead, we introduce a new combinator, that does exactly what we need: apply the second function to the final result of first one.

-- .: is fairly standard name for this combinator
(.:) :: (c -> d) -> (a -> b -> c) -> a -> b -> d
(f .: g) x y = f (g x y)

concatMap = concat .: map

Fine, that's it for motivation. Let's get to the pointfree business.

(.:) = f g x y -> f (g x y)
     = f g x y -> f ((g x) y)
     = f g x y -> f . g x $ y
     = f g x   -> f . g x

Now, here comes the interesting part. This is yet another of the pointfree tricks that usually helps when you get stuck: we rewrite . into its prefix form and try to continue from there.

     = f g x   -> (.) f (g x)
     = f g x   -> (.) f . g $ x
     = f g     -> (.) f . g
     = f g     -> (.) ((.) f) g
     = f       -> (.) ((.) f)
     = f       -> (.) . (.) $ f
     =             (.) . (.)

As for intuition, there's this very nice article that you should read. I'll paraphrase the part about (.):

Let's think again about what our combinator should do: it should apply f to the result of result of g (I've been using final result in the part before on purpose, it's really what you get when you fully apply - modulo unifying type variables with another function type - the g function, result here is just application g x for some x).

What it means for us to apply f to the result of g? Well, once we apply g to some value, we'll take the result and apply f to it. Sounds familiar: that's what (.) does.

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

Now, it turns out that composition (our of word) of those combinators is just a function composition, that is:

(.:) = result . result -- the result of result

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...