You got it, Peter!<br><br>There's a different generalization axis
I've gotten a lot of mileage from, hinted at by the types of first and
second. Generalize function fmap to arrows beyond (->). I called
the generalized method "result", because it says to edit in the result
of a function, just as first and second say to edit in the first and
second components of a pair.<br><br>This pattern emerged for me while working on the Eros (<a href="http://conal.net/papers/Eros/">http://conal.net/papers/Eros/</a>) project and is captured in the DeepArrow library (<a href="http://haskell.org/haskellwiki/DeepArrow">http://haskell.org/haskellwiki/DeepArrow</a>). The Eros paper shows applications for interactive composition of values, code, and UIs.<br>
<br>Even without the generalization to deep arrows, defining result = (.), and using first, second, and result gives a nice concrete reading, in addition to uses of fmap. For instance, (first.result.second) says how to walk down the type graph: take the first half of a pair, then the result part of a function, then the second part of a pair.<br>
<br> - Conal<br><br><div class="gmail_quote">2008/11/20 Peter Verswyvelen <span dir="ltr"><<a href="mailto:bugfact@gmail.com">bugfact@gmail.com</a>></span><br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Thanks for the feedback.<div><br></div><div><div>Let's see if I get this by writing a little newbie tutorial for myself using literal Haskell syntax. </div><div><br></div><div>I will import Control.Arrow since fmap on a pairs transforms the second coordinate value,<br>
</div><div>and when transforming pairs, I sometimes need to transform the first coordinate value...</div><div><br></div><div><span style="font-weight: bold;"><span style="font-family: 'courier new',monospace;">> import Control.Arrow</span></span><span style="font-family: 'courier new',monospace;"><br>
</span></div><div><br></div><div>To understand the (fmap.fmap.fmap) thing, I will create a simple tutorial,</div><div>mainly for myself to get a better understanding. </div><div><br></div><div>Suppose we have a pair:</div>
<div><br></div><div><span style="font-weight: bold;"><span style="font-family: 'courier new',monospace;">> p :: (Bool, [Char])</span></span></div><div><br></div>
<div>E.g.</div><div><br></div><div><span style="font-weight: bold;"><span style="font-family: 'courier new',monospace;">> p = (True,"Reactive")</span></span></div>
<div><br></div><div>The "type graph" (pardon my lack of knowledge of correct terminology) of p is</div><div><br></div><div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;"> (,)</span></span></div>
<div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;"> / \</span></span></div><div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;"> Bool [] </span></span></div>
<div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;"> |</span></span></div><div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;"> Char</span></span></div>
<div><br></div><div>Since fmap is about transforming a structure into another structure,</div><div>let's suppose that - given any "instance" with a type signature like p -</div><div>we want to create a new instance p' at runtime that transforms</div>
<div>the string (at the second coordinate) into its length.</div><div><br></div><div>That's easy; we can use fmap (or Arrow.second) to do that:</div><div><br></div><div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;">< instance Functor ((,) a) where</span></span></div>
<div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;">< fmap f (x,y) = fmap (x, f y)</span></span></div><div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;"><br>
</span></span></div><div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;">> tp :: (Bool,[Char]) -> (Bool,Int)</span></span></div>
<div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;">> tp = fmap length </span></span></div><div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;">></span></span></div>
<div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;">> p' = tp p</span></span></div><div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;"><br>
</span></span></div><div>fmap on pairs basically transforms the rightmost branch of our graph.</div><div><br></div><div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;"> (,) (,) </span></span></div>
<div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;"> / \ / \ </span></span></div><div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;"> Bool [] --> Bool Int </span></span></div>
<div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;"> | </span></span></div><div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;"> Char </span></span></div>
<div><br></div><div>fmap always transforms the rightmost branch in the graph, since the kind of Functor is * -> *. </div><div><br></div><div>For example lets define an fmap on triples:</div><div><br></div><div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;">> instance Functor ((,,) a b) where</span></span></div>
<div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;">> fmap f (x,y,z) = (x,y,f z)</span></span></div><div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;"><br>
</span></span></div><div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;">< fmap :: (c->d) -> (a,b,c) -> (a,b,d)</span></span></div>
<div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;"><br></span></span></div><div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;"> (,,) (,,)</span></span></div>
<div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;"> / | \ --> / | \</span></span></div><div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;"> a b c a b d</span></span></div>
<div><br></div><div>To continue the (fmap.fmap.fmap) story, suppose we now nest p in a Maybe:</div><div><br></div><div><span style="font-weight: bold;"><span style="font-family: 'courier new',monospace;">> m :: Maybe (Bool, [Char])</span></span></div>
<div><span style="font-weight: bold;"><span style="font-family: 'courier new',monospace;">> m = Just (True, "Reactive")</span></span></div><div><span style="font-weight: bold;"><span style="font-family: 'courier new',monospace;"><br>
</span></span></div><div><span style="font-weight: bold;"><span style="font-family: 'courier new',monospace;"> Maybe </span></span></div><div><span style="font-weight: bold;"><span style="font-family: 'courier new',monospace;"> |</span></span></div>
<div><span style="font-weight: bold;"><span style="font-family: 'courier new',monospace;"> (,)</span></span></div><div><span style="font-weight: bold;"><span style="font-family: 'courier new',monospace;"> / \</span></span></div>
<div><span style="font-weight: bold;"><span style="font-family: 'courier new',monospace;"> Bool [] </span></span></div><div><span style="font-weight: bold;"><span style="font-family: 'courier new',monospace;"> |</span></span></div>
<div><span style="font-weight: bold;"><span style="font-family: 'courier new',monospace;"> Char</span></span></div><div><br></div><div>Again we want to transform the string into its length.</div>
<div><br></div><div>To do that we can use the fmap Maybe instance:</div><div><br></div><div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;">< fmap f Nothing = Nothing</span></span></div>
<div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;">< fmap f (Just x) = Just (f x)</span></span></div><div><br></div><div>
The function we need to fmap on m is just tp!</div><div><br></div><div><span style="font-weight: bold;"><span style="font-family: 'courier new',monospace;">> tm :: Maybe (Bool,[Char]) -> Maybe (Bool,Int)</span></span></div>
<div><span style="font-weight: bold;"><span style="font-family: 'courier new',monospace;">> tm = fmap tp</span></span></div><div><span style="font-weight: bold;"><span style="font-family: 'courier new',monospace;">></span></span></div>
<div><span style="font-weight: bold;"><span style="font-family: 'courier new',monospace;">> m' = tm m</span></span></div><div><br></div><div>So again this fmap transforms the rightmost branch underneath the Maybe</div>
<div>(which is the one and only branch underneath the unary Maybe type)</div><div><br></div><div>If we expand tm we get</div><div><br></div><div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;">< tm = fmap (fmap length) = <span style="color: rgb(0, 153, 0);">(fmap . fmap)</span> length</span></span></div>
<div><br></div><div>So here we have the first magical (fmap . fmap): </div><div>- the first fmap transforms the branch underneath the Maybe with (fmap (fmap length)),</div><div>- the second fmap transforms the right branch underneath the pair (,) with (fmap length).</div>
<div><br></div><div>We can also do this for functions. Suppose we now have</div><div><br></div><div><span style="font-weight: bold;"><span style="font-family: 'courier new',monospace;">> f :: Char -> Maybe (Bool, [Char])</span></span></div>
<div><span style="font-weight: bold;"><span style="font-family: 'courier new',monospace;">> f c = Just (c=='a', "Reactive")</span></span></div>
<div><br></div><div>The type graph of f is</div><div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;"><br></span></span></div>
<div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;"> (->)</span></span></div><div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;"> / \</span></span></div>
<div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;">Char Maybe </span></span></div><div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;"> |</span></span></div>
<div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;"> (,)</span></span></div><div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;"> / \</span></span></div>
<div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;"> Bool [] </span></span></div><div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;"> |</span></span></div>
<div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;"> Char</span></span></div><div><br></div><div>But function application also has an fmap instance! </div>
<div><br></div><div>It is just the same as function composition:</div><div><br></div><div><span style="font-weight: bold;"><span style="font-family: 'courier new',monospace;">< instance Functor ((<-) a) where</span></span></div>
<div><span style="font-weight: bold;"><span style="font-family: 'courier new',monospace;">< fmap f g = f . g</span></span></div><div><span style="font-weight: bold;"><span style="font-family: 'courier new',monospace;">< fmap :: (b->c) -> (a->b) -> (a->c)</span></span></div>
<div><span style="font-weight: bold;"><span style="font-family: 'courier new',monospace;"><br></span></span></div><div><span style="font-weight: bold;"><span style="font-family: 'courier new',monospace;"> (->) (->) </span></span></div>
<div><span style="font-weight: bold;"><span style="font-family: 'courier new',monospace;"> / \ -> / \ </span></span></div><div><span style="font-weight: bold;"><span style="font-family: 'courier new',monospace;"> a b a c</span></span></div>
<div><span style="font-weight: bold;"><span style="font-family: 'courier new',monospace;"><br></span></span></div><div>Again the rightmost branch is transformed...</div>
<div> </div><div>So to transform the string into its length but now in the f graph, we do</div><div><br></div><div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;">> tf :: (Char -> Maybe (Bool, [Char])) -> (Char -> Maybe (Bool, Int))</span></span></div>
<div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;">> tf = fmap tm</span></span></div><div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;">></span></span></div>
<div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;">> f' = tf f</span></span></div><div><br></div><div>Expanding this gives</div>
<div><br></div><div><span style="font-weight: bold;"><span style="font-family: 'courier new',monospace;">> tf' = (<span style="color: rgb(0, 153, 0);">fmap . fmap . fmap)</span> length</span></span></div>
<div><span style="font-weight: bold;"><span style="font-family: 'courier new',monospace;">> f'' = tf' f</span></span></div><div><br></div><div>So the expression ((fmap.fmap.fmap) g) performs deep transformation </div>
<div>on the 3 rightmost branches of any type graph (that has fmap instances)</div><div><br></div><div>To transform a leftmost branch, we can use Arrow.first, for example:</div><div><br></div><div><span style="font-weight: bold;"><span style="font-family: 'courier new',monospace;">> tf'' :: (Char -> Maybe (Bool,[Char])) -> (Char -> Maybe (String,[Char]))</span></span></div>
<div><span style="font-weight: bold;"><span style="font-family: 'courier new',monospace;">> tf'' = (fmap . fmap . first) show </span></span></div><div>
<span style="font-weight: bold;"><span style="font-family: 'courier new',monospace;"><br></span></span></div><div><span style="font-weight: bold;"><span style="font-family: 'courier new',monospace;">> f''' = tf'' f</span></span></div>
<div><br></div><div>Demo:<br></div><div><br></div><div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;">> main = mapM_ putStrLn </span></span></div>
<div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;">> [ showT p $ fmap length</span></span></div><div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;">> , showT m $ (fmap.fmap) length</span></span></div>
<div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;">> , showF f $ (fmap.fmap.fmap) length</span></span></div><div>
<span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;">> , showF f $ (fmap.fmap.first) show ]</span></span></div><div><div>
<span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;">></span></span></div><div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;">> showT x t = show x ++ " ==> " ++ (show $ t x)</span></span></div>
<div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;">> showF f t = "\'a' -> "++show (f 'a') ++ " ==> \'a' -> " ++ show ((t f) 'a')</span></span></div>
<div><span style="font-family: 'courier new',monospace;"><span style="font-weight: bold;"><br></span></span></div><div><span style="font-family: 'courier new'; font-size: 12px; font-weight: bold;"><div>
<span style="font-weight: normal;"><span style="font-style: italic;">|(True,"Reactive") ==> (True,8)</span></span></div><div><span style="font-weight: normal;"><span style="font-style: italic;">| Just (True,"Reactive") ==> Just (True,8)</span></span></div>
<div><span style="font-weight: normal;"><span style="font-style: italic;">| 'a' -> Just (True,"Reactive") ==> 'a' -> Just (True,8)</span></span></div>
<div><span style="font-weight: normal;"><span style="font-style: italic;">| 'a' -> Just (True,"Reactive") ==> 'a' -> Just ("True","Reactive")</span></span></div>
<div><br></div></span></div></div><div>I think I learned something cool here: being able to perform deep transformations without writing a lot of boiler plate code. </div><div><br></div><div>Thank you!</div><div><br></div>
</div>
<br>_______________________________________________<br>
Reactive mailing list<br>
<a href="mailto:Reactive@haskell.org">Reactive@haskell.org</a><br>
<a href="http://www.haskell.org/mailman/listinfo/reactive" target="_blank">http://www.haskell.org/mailman/listinfo/reactive</a><br>
<br></blockquote></div><br>