h1

My Evolution as a Haskell Programmer: Factorial with Arrows

February 19, 2007

A couple of years ago Fritz Ruehr wrote a great article about The Evolution of a Haskell Programmer. It was written in 2001, when I was still in high school, some years away from being introduced to the beautiful Haskell programming language.

Currently, I’m following a course on Advanced Functional Programming at the Utrecht University. One of the advanced topics tought in that course is about Arrows. Arrows are an abstraction of computations, just like Monads, but even more general and pretty nice to define stream functions with (useful for defining logical circuits, for example). I’m still trying to get my head fully around it, but so far I understand it enough to add a new part to the evolution (a missing link!): the factorial function defined with arrows.

I will present the code below and sparsely comment on it. Most of the code is actually from the Advanced Functional Programming lecture.

-- We need this library 
import Control.Arrow        

-- Define a type for stream functions, from one list to another 
newtype SF a b = SF { runSF :: [a] -> [b] }      

-- Define the Arrow functions for the SF type.  Once you've 
-- defined these three, you'll get a lot of other functions for 
-- free. 
instance Arrow SF where 
  arr f = SF (map f) 
  SF f >>> SF g = SF (f >>> g) 
  first (SF f) = SF (unzip >>> first f >>> uncurry zip)      

-- arr   lifts a function to the arrow domain 
-- >>>   combines (connects) two arrow functions 
-- first only applies the function to the first part from a 
--       tuple      

-- See the http://www.haskell.org/arrows for more 
-- information and some nice graphics, which will help 
-- understanding.

Okay, so far, so good. By defining the 'first' and '>>>' functions, we get an '&&&' combinator for free, which we will use in our final definition. For example: 'f &&& g' can be understood as accepting and input x, then applying both f and g to it, resulting in the output of a tuple of the results. In short, the type of '&&&' is 'Arrow arr => arr a b -> arr a c -> arr a (b, c)'.

-- The type of loop is (ArrowLoop arr) => arr (a, c) (b, c) -> 
-- arr a b.  A loop makes a function from 'a' to 'b', while 
-- 'looping' a 'c'. 
instance ArrowLoop SF where 
  loop (SF f) = SF $ \\as -> 
    let (bs,cs) = unzip (f (zip as (stream cs))) 
    in bs      

-- Note in the definition that cs is defined recursive(!)  This 
-- is really where the usefulness of Haskell's lazyness kicks 
-- in.  Although, because zip and unzip are both strict, we 
-- have to help it a little, by defining a helper function 
-- stream.      

stream :: [a] -> [a] 
stream ~(x:xs) = x:stream xs      

-- The ~ in the pattern makes the pattern matching irrefutable, 
-- which means that the pattern will not be interpreted but 
-- assumed to be correct.

Well, with that out of the way we can get to the good stuff. We just need two simple helpers to modify the stream.

-- 'Delays' a stream by prepending an element.  This can be 
-- used to initialize a stream _before_ the input is read. 
-- We're going to need this to use that nasty loop above. 
-- Remember, the c was defined recursive, without 
-- initialization. 
delay :: a -> SF a a 
delay x = SF (x:)      

-- Takes an input and muliplies it.  It 'simply' lifts an 
-- uncurried (*) to the arrow domain. 
-- Example (try it yourself): mul (6,7) = 42 
mul :: Arrow arr => arr (Integer, Integer) Integer 
mul = arr (uncurry (*))

Okay, now, the basic idea is to supply a stream function with the list of integers and then all we have to do is multiply the result of the first item with the second and multiply that result with the third, etc. Aha, that's easy, we can just use the loop for that. The only thing we need is in initialization value to start the multiplying with. For this we use the delay. Schematicly, our plan looks like the following picture.

Factorial Arrows

You can clearly see how the loop works while the input and the output of the whole is still a single stream. The dot in the image where the output of 'mul' splits is actually the '&&&' combinator. The code then looks like this.

facSF :: SF Integer Integer 
facSF = loop (mul >>> (arr id &&& delay 1))

Pretty clean, eh? Only thing left is a nice wrapper to run this thing.

-- Using Integers so that for large numbers (and factorials 
-- tend to get really large fast) it still produces nice 
-- output.  Try 'fac 420' for example. 
fac :: Integer -> Integer 
fac x = runSF facSF [1..x] !! fromInteger (x - 1)

This concludes our fun with Arrows. Viva la evolucion!

About these ads

18 comments

  1. It looks really nice, but what is the big advantage of Arrows over other control-structures. I’m pretty sure you can do really cool stuff with it. I’m not sure, but the big advantage is that you have multiple outputs, right? It sure looks pretty handy… but a little bit too much code. Do you have more examples?


  2. You can look at the AFP slides for a Fibonnacci machine implemented with arrows. I must warn you it’s even more mindboggling than the ‘simple stuff’ above.

    The main advantages of Arrows I know of I’ll have to quote from the AFP course, since I have no ‘real life’ experience with using them, besides for toying around.

    Arrows have been adapted to support Functional Reactive Programming, for example in Yampa.

    Besides that, Arrows can improve memory behaviour, in particular the garbage collection. You can imagine that the already processed part of a stream can easily be collected.


  3. I think that instead of

    SF f >>> SF g = SF (f >>> g)

    You need

    SF f >>> SF g = SF (f . g)


  4. Hi Gaal,

    Could you explain why you think that? As you can see on the Haskell page on Arrows, the type of (>>>) is ‘a b c -> a c d -> a b d’ (‘a’ is in this case SF), while the type of (.) is ‘(b -> c) -> (a -> b) -> a -> c’

    I wouldn’t dare to publish code that I didn’t test beforehand ;)


  5. (Actually “SF (f . g)” is wrong; I should have said “SF (g . f)”.)

    The definition of >>> can’t be

    SF f >>> SF g = SF (f >>> g)

    For two reasons. First, it’s turtles all the way down, that is, there’s nothing to stop the recursive definition. Second, “SF f >>> SF g” implies

    f, g :: [a] -> [b]

    If the type of (>>>) is “a b c -> a c d -> a b d”, then “f >>> g” does not typecheck.

    As far as my understanding goes (not exceedingly far), (>>>) is the repacking of the composition of two peeled-off stream functions f and g into a new stream function. But the composition itself takes place on f and g. (>>>) lifts it to the arrow for its users.


  6. Okay, let’s say f :: [b] -> [c] and g :: [c] -> [d]

    That means: SF f :: SF b c and SF g :: SF c d.

    A word of warning here, the first SF is the constructor, the second is the type(!)

    (SF f >>> SF g) :: SF b d, clearly.

    Now comes an important trick/insight: functions can be seen as arrows!

    instance Arrow (->) where
    arr = id
    (>>>) = flip (.)
    first f (a, c) = (f a, c)

    This means f :: (->) [b] [c] and g :: (->) [c] [d] and therefore: (f >>> g) :: (->) [b] [d] (which is of course written as [b] -> [d] conventionally).

    Now, if you want to specify the type of SF (f >>> g) it’s easy to see that this is SF ([b] -> [d]), which is written as SF b d.

    Hopefully this clearifies it a bit.


  7. Ah, yes, thank you.

    SF (f >>> g) redispatches via the arrow class, and unless I’m mistaken in this case the (->) instance of the same class means that the actual reduction is indeed always (g . f)? So writing it in arrow form is more elegant (and probably more proper) but means the same thing.

    I need to reread the arrows paper.


  8. Indeed :)


  9. Either my browser or your blog software ate the backslash in your lambda expression in the loop definition of the ArrowLoop SF instance, the absence of which might frustrate Haskell newbies trying to run the code for themselves.

    It definitely confused ghc when I tried out the code for myself. It is unfortunate that GHC’s error was “parse error on input `bound by lambda. Did your browser or blog munch that backslash?”, which would have much more perspicuously suggested the needed fix.


  10. No. Stupid blogware. That is not what I wrote. It just ate a whole sentence after the backwards single quote. Anyway, I guess I just proved my point that wordpress.com does not work well with code. I am much happier with google’s blogger.


  11. Dan, thanks! It’s indeed WordPress ignorance to code that caused the backslash to be dropped. When escaping the backslash in the input field it works, so I fixed the example code.


  12. I have used arrows quite a bit for doing all kinds of things, and one of the things I like most about using them as opposed to other constructs, such as monads, is the right to left nature of the beast, and the use of (***) and (&&&), which can be strung together in as complex a scenario as needed and then the results of say a thing like
    (f &&& g) &&& (h &&& j) >>> (\((a,b),(c,d) -> a + b + c + d)
    where the four functions f,g,h,j are applied separately to an input and then the result of that computation is then summed together in the lambda. Pretty neat stuff.. and you can use them out of the box without understanding category theory or lambda caluculus… I leave that stuff to S.P. Jones and those folks to get the compiler right.. and just use the stuff..
    cheers,
    gene


  13. Notice that you can define loop (SF f) in another way. The original is

    instance ArrowLoop SF where
    loop (SF f) = SF $ \as ->
    let (bs,cs) = unzip (f (zip as (stream cs)))
    in bs

    And here it is the (more cryptic :) definition I propose

    loop (SF f) = SF $ loop $ second stream >>> uncurry zip >>> f >>> unzip

    where I especially like the fact that “loop” of SF functions it is defined in terms of (built-in) looping functions of type ([a],[c]) -> ([b], [c]). In this way you reuse the main idea of looping, which is encoded in Control.Arrow when defining (->) as an instance of ArrowLoop.


  14. Hello There. I discovered your blog the use of msn.
    That is an extremely well written article. I’ll be sure to bookmark it and come back to read more of your useful info. Thanks for the post. I’ll definitely comeback.


  15. It’s awesome to pay a visit this website and reading the views of all friends about this article, while I am also keen of getting familiarity.


  16. Hi there! Do you know if they make any plugins to assist with SEO?

    I’m trying to get my blog to rank for some targeted keywords but I’m not
    seeing very good gains. If you know of any please
    share. Thank you!


  17. Excellent article. Keep posting such kind of information on
    your page. Im really impressed by your blog.
    Hey there, You have performed a fantastic job. I’ll definitely digg it and in my opinion suggest to my friends. I am sure they will be benefited from this web site.


  18. I wwas suggested this website by my cousin. I’m not
    sure whether this post is written by him as nobody else know such detailed about my difficulty.
    You are incredible! Thanks!



Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: