Personal tools

Arrow tutorial

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
m (Changed the ASCII diagram for the part after hOutput)
 
(9 intermediate revisions by 5 users not shown)
Line 1: Line 1:
  +
[[Category:Tutorials]]
  +
[[Category:Arrow]]
 
<haskell>
 
<haskell>
  +
  +
> {-# LANGUAGE Arrows #-}
 
> module ArrowFun where
 
> module ArrowFun where
 
> import Control.Arrow
 
> import Control.Arrow
  +
> import Control.Category
  +
> import Prelude hiding (id,(.))
  +
 
</haskell>
 
</haskell>
   
Line 9: Line 16:
   
 
Arr builds an arrow out of a function. This function is
 
Arr builds an arrow out of a function. This function is
arrow-specific. It's signature is
+
arrow-specific. Its signature is
   
 
<haskell>
 
<haskell>
  +
 
arr :: (Arrow a) => (b -> c) -> a b c
 
arr :: (Arrow a) => (b -> c) -> a b c
  +
 
</haskell>
 
</haskell>
   
 
Arrow composition is achieved with (>>>). This takes two arrows
 
Arrow composition is achieved with (>>>). This takes two arrows
 
and chains them together, one after another. It is also arrow-
 
and chains them together, one after another. It is also arrow-
specific. It's signature is:
+
specific. Its signature is:
   
 
<haskell>
 
<haskell>
  +
 
(>>>) :: (Arrow a) => a b c -> a c d -> a b d
 
(>>>) :: (Arrow a) => a b c -> a c d -> a b d
  +
 
</haskell>
 
</haskell>
   
Line 29: Line 40:
   
 
<haskell>
 
<haskell>
  +
 
first :: (Arrow a) => a b c -> a (b, d) (c, d)
 
first :: (Arrow a) => a b c -> a (b, d) (c, d)
 
second :: (Arrow a) => a b c -> a (d, b) (d, c)
 
second :: (Arrow a) => a b c -> a (d, b) (d, c)
  +
 
</haskell>
 
</haskell>
   
Line 45: Line 58:
   
 
<haskell>
 
<haskell>
  +
 
> newtype SimpleFunc a b = SimpleFunc {
 
> newtype SimpleFunc a b = SimpleFunc {
 
> runF :: (a -> b)
 
> runF :: (a -> b)
Line 55: Line 69:
 
> second (SimpleFunc f) = SimpleFunc (mapSnd f)
 
> second (SimpleFunc f) = SimpleFunc (mapSnd f)
 
> where mapSnd g (a,b) = (a, g b)
 
> where mapSnd g (a,b) = (a, g b)
> (SimpleFunc f) >>> (SimpleFunc g) = SimpleFunc (g . f)
+
>
  +
> instance Category SimpleFunc where
  +
> (SimpleFunc g) . (SimpleFunc f) = SimpleFunc (g . f)
  +
> id = arr id
  +
 
</haskell>
 
</haskell>
   
Line 65: Line 79:
   
 
<haskell>
 
<haskell>
  +
 
> split :: (Arrow a) => a b (b, b)
 
> split :: (Arrow a) => a b (b, b)
 
> split = arr (\x -> (x,x))
 
> split = arr (\x -> (x,x))
  +
 
</haskell>
 
</haskell>
   
Line 73: Line 89:
   
 
<haskell>
 
<haskell>
  +
 
> unsplit :: (Arrow a) => (b -> c -> d) -> a (b, c) d
 
> unsplit :: (Arrow a) => (b -> c -> d) -> a (b, c) d
 
> unsplit = arr . uncurry
 
> unsplit = arr . uncurry
 
> -- arr (\op (x,y) -> x `op` y)
 
> -- arr (\op (x,y) -> x `op` y)
  +
 
</haskell>
 
</haskell>
   
 
(***) combines two arrows into a new arrow by running the two arrows
 
(***) combines two arrows into a new arrow by running the two arrows
on a pair of values (one arrow on the first pair and one arrow on the
+
on a pair of values (one arrow on the first item of the pair and one arrow on the
second pair).
+
second item of the pair).
   
 
<haskell>
 
<haskell>
  +
 
f *** g = first f >>> second g
 
f *** g = first f >>> second g
  +
 
</haskell>
 
</haskell>
   
Line 90: Line 110:
   
 
<haskell>
 
<haskell>
f &&& g = split >>> first f >>> second g
+
-- = split >>> f *** g
+
f &&& g = split >>> first f >>> second g
  +
-- = split >>> f *** g
  +
 
</haskell>
 
</haskell>
   
Line 99: Line 119:
   
 
<haskell>
 
<haskell>
  +
 
> liftA2 :: (Arrow a) => (b -> c -> d) -> a e b -> a e c -> a e d
 
> liftA2 :: (Arrow a) => (b -> c -> d) -> a e b -> a e c -> a e d
 
> liftA2 op f g = split >>> first f >>> second g >>> unsplit op
 
> liftA2 op f g = split >>> first f >>> second g >>> unsplit op
> -- = f &&& g >>> unsplit op
+
> -- = f &&& g >>> unsplit op
  +
 
</haskell>
 
</haskell>
   
Line 112: Line 133:
   
 
<haskell>
 
<haskell>
  +
 
> f, g :: SimpleFunc Int Int
 
> f, g :: SimpleFunc Int Int
 
> f = arr (`div` 2)
 
> f = arr (`div` 2)
 
> g = arr (\x -> x*3 + 1)
 
> g = arr (\x -> x*3 + 1)
  +
 
</haskell>
 
</haskell>
   
Line 120: Line 143:
   
 
<haskell>
 
<haskell>
  +
  +
> h :: SimpleFunc Int Int
 
> h = liftA2 (+) f g
 
> h = liftA2 (+) f g
  +
>
  +
> hOutput :: Int
 
> hOutput = runF h 8
 
> hOutput = runF h 8
  +
 
</haskell>
 
</haskell>
   
Line 133: Line 161:
 
(4, 25) -> 29 applies (+) to tuple elements.
 
(4, 25) -> 29 applies (+) to tuple elements.
   
+------> f --------------+
+
+------> f ---------+
| v
+
| v
8 ---> (split) ---> g -----> (unsplit (+)) ----> 29
+
8 ---> (split) (unsplit (+)) ----> 29
  +
| ^
  +
+------> g ---------+
   
 
so we see that h is a new arrow that when applied to 8, applies 8 to f
 
so we see that h is a new arrow that when applied to 8, applies 8 to f
 
and applies 8 to g and adds the results.
 
and applies 8 to g and adds the results.
  +
  +
A lot of juggling occurred to get the plumbing right since
  +
h wasn't defined as a linear combination of arrows. GHC has
  +
a do-notation that simplifies this in a similar way to how
  +
do-notation simplifies monadic computation. To use this
  +
notation you must specify the -farrows flag. The h function
  +
can be defined as:
  +
  +
<haskell>
  +
  +
> h' :: SimpleFunc Int Int
  +
> h' = proc x -> do
  +
> fx <- f -< x
  +
> gx <- g -< x
  +
> returnA -< (fx + gx)
  +
>
  +
> hOutput' :: Int
  +
> hOutput' = runF h' 8
  +
  +
</haskell>
   
   
Line 147: Line 195:
   
 
<haskell>
 
<haskell>
  +
 
newtype Kleisli m a b = Kleisli {
 
newtype Kleisli m a b = Kleisli {
 
runKleisli :: (a -> m b)
 
runKleisli :: (a -> m b)
 
}
 
}
  +
 
</haskell>
 
</haskell>
   
Line 159: Line 209:
   
 
<haskell>
 
<haskell>
> -- XXX I am getting type problems with split, unsplit and liftA2! why?
 
> split' = arr (\x -> (x,x))
 
> unsplit' = arr . uncurry
 
> --liftA2' :: (Arrow a) => (b -> c -> d) -> a e b -> a e c -> a e d
 
> liftA2' op f g = split' >>> first f >>> second g >>> unsplit' op
 
</haskell>
 
   
<haskell>
 
 
> plusminus, double, h2 :: Kleisli [] Int Int
 
> plusminus, double, h2 :: Kleisli [] Int Int
 
> plusminus = Kleisli (\x -> [x, -x])
 
> plusminus = Kleisli (\x -> [x, -x])
> double = arr (* 2)
+
> double = arr (* 2)
> h2 = liftA2' (+) plusminus double
+
> h2 = liftA2 (+) plusminus double
  +
>
  +
> h2Output :: [Int]
 
> h2Output = runKleisli h2 8
 
> h2Output = runKleisli h2 8
  +
 
</haskell>
 
</haskell>
   
 
== A Teaser ==
 
== A Teaser ==
Finally, here's a little teaser. There's an arrow function called
+
Finally, here is a little teaser. There is an arrow function called
returnA which returns an identity arrow. There's a ArrowPlus class
+
returnA which returns an identity arrow. There is an ArrowPlus class
 
that includes a zeroArrow (which for the list monad is an arrow that
 
that includes a zeroArrow (which for the list monad is an arrow that
 
always returns the empty list) and a <+> operator (which takes the
 
always returns the empty list) and a <+> operator (which takes the
results from two arrows and concatenates them). We can build up
+
results from two arrows and concatenates them). We can build up
 
some pretty interesting string transformations (the multi-valued
 
some pretty interesting string transformations (the multi-valued
 
function String -> [String]) using Kleisli arrows:
 
function String -> [String]) using Kleisli arrows:
   
 
<haskell>
 
<haskell>
  +
  +
> main :: IO ()
 
> main = do
 
> main = do
 
> let
 
> let
 
> prepend x = arr (x ++)
 
> prepend x = arr (x ++)
> append x = arr (++ x)
+
> append x = arr (++ x)
> withId t = returnA <+> t
+
> withId t = returnA <+> t
 
> xform = (withId $ prepend "<") >>>
 
> xform = (withId $ prepend "<") >>>
 
> (withId $ append ">") >>>
 
> (withId $ append ">") >>>
Line 194: Line 240:
 
> xs = ["test", "foobar"] >>= (runKleisli xform)
 
> xs = ["test", "foobar"] >>= (runKleisli xform)
 
> mapM_ putStrLn xs
 
> mapM_ putStrLn xs
  +
 
</haskell>
 
</haskell>
   
Line 211: Line 258:
   
 
== Tutorial Meta ==
 
== Tutorial Meta ==
  +
The wiki file source is literate Haskell. Save the source in a file called ArrowFun.lhs to compile it (or run in GHCi).
  +
  +
The code is adapted to GHC 6.10.1; use [http://www.haskell.org/haskellwiki/?title=Arrow_tutorial&oldid=15443] for older versions of GHC and other Haskell implementations.
  +
 
* Original version - Nov 19, 2006, Tim Newsham.
 
* Original version - Nov 19, 2006, Tim Newsham.
  +
\

Latest revision as of 04:56, 4 January 2010

> {-# LANGUAGE Arrows #-}
> module ArrowFun where
> import Control.Arrow
> import Control.Category
> import Prelude hiding (id,(.))

Contents

[edit] 1 The Arrow

Arrow a b c represents a process that takes as input something of type b and outputs something of type c.

Arr builds an arrow out of a function. This function is arrow-specific. Its signature is

arr :: (Arrow a) => (b -> c) -> a b c

Arrow composition is achieved with (>>>). This takes two arrows and chains them together, one after another. It is also arrow- specific. Its signature is:

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

First and second make a new arrow out of an existing arrow. They perform a transformation (given by their argument) on either the first or the second item of a pair. These definitions are arrow-specific. Their signatures are:

first :: (Arrow a) => a b c -> a (b, d) (c, d)
second :: (Arrow a) => a b c -> a (d, b) (d, c)

First and second may seem pretty strange at first, but they'll make sense in a few minutes.

That's it for the arrow-specific definitions.

[edit] 2 A Simple Arrow

Let's define a really simple arrow as an example. Our simple arrow is just a function mapping an input to an output. We don't really need arrows for something this simple, but we could use something this simple to explain arrows.

> newtype SimpleFunc a b = SimpleFunc {
>     runF :: (a -> b)
> }
>
> instance Arrow SimpleFunc where
>     arr f = SimpleFunc f
>     first (SimpleFunc f) = SimpleFunc (mapFst f)
>                   where mapFst g (a,b) = (g a, b)
>     second (SimpleFunc f) = SimpleFunc (mapSnd f)
>                   where mapSnd g (a,b) = (a, g b)
>
> instance Category SimpleFunc where
>     (SimpleFunc g) . (SimpleFunc f) = SimpleFunc (g . f)
>     id = arr id

[edit] 3 Some Arrow Operations

Now lets define some operations that are generic to all arrows.

Split is an arrow that splits a single value into a pair of duplicate values:

> split :: (Arrow a) => a b (b, b)
> split = arr (\x -> (x,x))

Unsplit is an arrow that takes a pair of values and combines them to return a single value:

> unsplit :: (Arrow a) => (b -> c -> d) -> a (b, c) d
> unsplit = arr . uncurry       
>           -- arr (\op (x,y) -> x `op` y)

(***) combines two arrows into a new arrow by running the two arrows on a pair of values (one arrow on the first item of the pair and one arrow on the second item of the pair).

f *** g = first f >>> second g

(&&&) combines two arrows into a new arrow by running the two arrows on the same value:

f &&& g = split >>> first f >>> second g
     -- = split >>> f *** g

LiftA2 makes a new arrow that combines the output from two arrows using a binary operation. It works by splitting a value and operating on both halfs and then combining the result:

> liftA2 :: (Arrow a) => (b -> c -> d) -> a e b -> a e c -> a e d
> liftA2 op f g = split >>> first f >>> second g >>> unsplit op
>            -- = f &&& g >>> unsplit op


[edit] 4 An Example

Now let's build something using our simple arrow definition and some of the tools we just created. We start with two simple arrows, f and g. F halves its input and g triples its input and adds one:

> f, g :: SimpleFunc Int Int
> f = arr (`div` 2)
> g = arr (\x -> x*3 + 1)

We can combine these together using liftA2:

> h :: SimpleFunc Int Int
> h = liftA2 (+) f g
>
> hOutput :: Int
> hOutput = runF h 8

What is h? How does it work? The process defined by h is (split >>> first f >>> second g >>> unsplit (+)). Lets work through an application of h to some value, 8:

   8 -> (8, 8)             split
   (8, 8) -> (4, 8)        first f (x `div` 2 of the first element)
   (4, 8) -> (4, 25)       second g (3*x + 1 of the second element)
   (4, 25) -> 29           applies (+) to tuple elements.
             +------> f ---------+
             |                   v
   8 ---> (split)          (unsplit (+)) ----> 29
             |                   ^
             +------> g ---------+

so we see that h is a new arrow that when applied to 8, applies 8 to f and applies 8 to g and adds the results.

A lot of juggling occurred to get the plumbing right since h wasn't defined as a linear combination of arrows. GHC has a do-notation that simplifies this in a similar way to how do-notation simplifies monadic computation. To use this notation you must specify the -farrows flag. The h function can be defined as:

> h' :: SimpleFunc Int Int
> h' = proc x -> do
>       fx <- f -< x
>       gx <- g -< x
>       returnA -< (fx + gx)
>
> hOutput' :: Int
> hOutput' = runF h' 8


[edit] 5 Kleisli Arrows

Let's move on to something a little fancier now: Kleisli arrows. A Kleisli arrow (Kleisli m a b) is the arrow (a -> m b) for all monads. It's defined in Control.Arrows similarly to our SimpleFunc:

newtype Kleisli m a b = Kleisli {
  runKleisli :: (a -> m b) 
}

It comes complete with its own definitions for arr, first, second and (>>>). This means that all multi-value functions (a -> [b]) are already defined as Kleisli arrows (because [] is a monad)! (>>>) performs composition, keeping track of all the multiple results. Split, (&&&) and (***) are all defined as before. So for example:

> plusminus, double, h2 :: Kleisli [] Int Int
> plusminus = Kleisli (\x -> [x, -x])
> double    = arr (* 2)
> h2        = liftA2 (+) plusminus double 
>
> h2Output :: [Int]
> h2Output = runKleisli h2 8

[edit] 6 A Teaser

Finally, here is a little teaser. There is an arrow function called returnA which returns an identity arrow. There is an ArrowPlus class that includes a zeroArrow (which for the list monad is an arrow that always returns the empty list) and a <+> operator (which takes the results from two arrows and concatenates them). We can build up some pretty interesting string transformations (the multi-valued function String -> [String]) using Kleisli arrows:

> main :: IO ()
> main = do
>    let
>        prepend x = arr (x ++)
>        append  x = arr (++ x)
>        withId  t = returnA <+> t
>        xform = (withId $ prepend "<") >>>
>                (withId $ append ">") >>>
>                (withId $ ((prepend "!") >>> (append "!")))
>        xs = ["test", "foobar"] >>= (runKleisli xform)
>    mapM_ putStrLn xs

An important observation here is that

   f >>> g

is multi-valued composition (g . f), and

   (withId f) >>> (withId g) =
   (returnA <+> f) >>> (returnA <+> g) =
   ((arr id) <+> f) >>> ((arr id) <+> g)

which, when applied to an input x, returns all values:

   ((id . id) x) ++ ((id . f) x) ++ ((id . g) x) ++ ((g . f) x) =
   x ++ (f x) ++ (g x) ++ ((g . f) x)

which are all permutations of using arrows f and g.

[edit] 7 Tutorial Meta

The wiki file source is literate Haskell. Save the source in a file called ArrowFun.lhs to compile it (or run in GHCi).

The code is adapted to GHC 6.10.1; use [1] for older versions of GHC and other Haskell implementations.

  • Original version - Nov 19, 2006, Tim Newsham.

\