Back to Questions
5.0k
views12
comments
A stab at Arrows
f#functionalreactive

Hi everyone, this is the first time I have had something that I felt I should post. And even now I'm a bit nervous. Well I'll get into the heart of the subject.

I have been looking at functional reactive animation. An I got to thinking how difficult would it be to implement arrows in F#. Well it seems not to be that difficult because here is a preliminary try.

#lightmodule Arrow = type Arrow<'inp, 'out> (f:'inp -> 'out) = member a.run x = f x let arr f = new Arrow<'i,'o>(f) let op_RightShift (f:Arrow<'inp,'mid>) (g:Arrow<'mid,'out>) = arr (fun x -> g.run(f.run x)) let (&&&) (f:Arrow<'b,'c>) (g:Arrow<'b,'d>) = arr (fun i -> (f.run i, g.run i)) let first (f:Arrow<'a, 'b>) = arr (fun (i,x) -> ( f.run i, x)) let second (f:Arrow<'a, 'b>) = let swap (x,y) = (y,x) (arr swap) >>> (first f) >>> (arr swap) let ( *** ) (f:Arrow<'a,'b>) (g:Arrow<'c,'d>) = (first f) >>> (second g)

Disclaimer: I am a professional amateur. So this code may not be completely correct. However, comment are welcome and appreciated.

.

Hello,

Welcome to the community! No need to be nervous about posting here we try to be friendly and welcoming.

I think I understand your code and it seems correct to me. I understand that the code is just for fun, but I'm strugging to see why you'd want to do this in F#, since F# already has the arrow notation build in. It feels like your adding an extra layer were it is needed, or is there another perpose I'm missing? I guess if it was compiled to a library this could be used to provide currying in languages that didn't support it, ie C#/VB.NET?

Cheers,
Rob

By on 9/13/2008 12:26 AM ()

I did not realize that it had already been implemented in F#. So what is the F# notation for arrow as I have missed it somehow? If it isn't to much trouble what should I search for to see an example of this?

By on 9/13/2008 11:58 AM ()

Hi there,

Robert, "arrow" in this context is referring to the Haskell notion of "arrow", a very nice and powerful generalization of monads.

thanks

don

By on 9/13/2008 8:24 PM ()

Apologies for the confusion, I am unfamilar with haskel. I thought arrow was refering to -> from a function type signature. I did try and google for arrows, but you find lots of information about the Robin Hood kind. If you had any links to information about arrows, please feel free to share them.

Cheers,
Rob

By on 9/13/2008 10:54 PM ()

Rob, one Arrows tutorial that i recommend is Understanding Arrows from the Haskell wikibook. The first part of the tutorial doesn't use much Haskell syntax. The Arrows concept is interesting but i haven't seen it used much. One of Haskell's XML libraries uses arrows, but it is imo too complex and libraries like that one are getting "light" alternatives that are much easier to use.

By on 9/14/2008 1:21 AM ()

A nice, practical paper about Arrows and functional reactive programming is at [link:www.haskell.org]

I'm interested in your progress, thedwalker. Do let us know what you're up to. :)

bye

Kurt

By on 9/14/2008 5:54 AM ()

I'll try. I've hit a bit of a snag with implementing the loop, left, right, and ||| combinators. The latter is probably just that I haven't totally grasped how it should work. Or maybe I'm overthinking which wouldn't be a surprise for me.

One thing that struck me as odd was I couldn't seem to get the some of operator to work as static members. I receive a type constraint mismatch error when I try to define ( >>> ) within the Arrow type. ( &&& ) gives infers a type signature of:
Arrow<'a,'b> -> Arrow<'a,'b> -> Arrow<'a,('b*'b)>

However when I defined them in a manner similar to C# extension methods everything was fine except ( >>> ) gives a type constraint mismatch in the definition of the 'second' function
or it'll act as if I did not overload the operator.

By on 9/14/2008 6:41 PM ()

Hi there

You'll should probably use a different operator name, ">>>" and "&&&" conflict with the default operators used for overloaded bitwise integer manipulations. Normally this doesn't matter but the default definition for ">>>" restricts the signature more than you need.

Knid regards

don

By on 9/19/2008 3:58 PM ()

I can see how that can affect things, but interestingly like I said it only happens when I make it a static extension of the Arrow type. Even if I change the name of the functions as ( >>> ) and ( &&& ) was originally named combine and par respectively because the tooltip type signatures don't seem to work for me on user-defined operator.

On a slight tangent I did find a rather convoluted example that transformed intergers into their roman numeral representations using. Here it is:

let unfold f x =
let rec loop x acc =
match f x with
| None -> List.rev acc
| Some(a, x') -> loop x' (a::acc)
loop x []
let numerals = [("M", 1000); ("CM", 900); ("D", 500); ("CD", 400);
("C", 100); ("XC", 90); ("L", 50); ("XL", 40);
("X", 10); ("IX", 9); ("V", 5); ("IV", 4);
("I", 1)]

let next n =
match n with
| 0 -> None
| _ -> numerals |> List.filter (fun x-> let _,s = x in s <= n) |> List.hd |> (second (arr (fun x-> n - x))).run |> Some

let romanize x = List.reduce_left (fun (a: string) (i:string) ->a ^ i )(unfold next x)

By on 9/19/2008 8:06 PM ()

It's been almost ten days since my last post on implementing the arrows and some of it common combinators. That's partially because of work and because I had hit a bit of a bump in the road. But the bump has been overcome so I have had a chance to implement the left, right, |||, and the +++ combinators. Submitted for your perusal, the code:

type either<'a, 'b> =
| Left of 'a
| Right of 'b

let ( |.| ) (f: Arrow<'a, 'c>) (g:Arrow<'b, 'c>) =
arr (fun x -> match x with
| Left a -> f.run a
| Right b -> g.run b
)

let left (f: Arrow<'a,'b>) =
arr (
fun x -> match x with
| Left a -> Left (f.run a)
| Right a -> Right a
)
let right (f: Arrow<'a, 'b>) =
let mirror = fun x -> match x with
| Left a -> Right a
| Right a -> Left a
(arr mirror) >.> left f >.> (arr mirror)
let ( +.+ ) (f: Arrow<'a,'b>) (g: Arrow<'c,'d>) = (left f) >.> (right g)

As you can see I took Don' suggestion and renamed the combinator that conflict with existing operator. It works fine although now the definitions look like emoticon.

All that is really left now is loop. But that will be a beast to figure out. As I can't make heads or tails of the definitions I've seen for it. For instance, the Haskell definiton is:

loop :: arr (a, c) (b, c) -> arr a b
loop f a = b
where (b, c) = f (a, c)

From this Haskell, I surmised that it would look something like this in F#:

val loop : Arrow<'a*'c, 'b*'c> -> Arrow<'a, 'b>

let loop (f:Arrow<'a*'c, 'b*'c> =
arr (
fun a ->
let mutable st = init
let b,c = f.run (a, st) in st <- c
b)

But this for some reason doesn't sit right with me. It should take the component c and feed it back in the the function f contains. Am I missing something?

By on 9/28/2008 9:28 PM ()

What's the definition of >.>? Looks like it was missing?

For "Loop" you are writing a very funky and general tie-the-knot combinator. Because F# is strict you will need to insert some explicit laziness, and the operator will only make sense for lazy "c" types, i.e. types where you can provably embed/delay computations. You can do this in at least three ways

<UL><li>pass in a "delay" function that embeds "unit -> c" into "c"</LI><li>change the type of "loop" so that it includes lazy<c> on the input side.</LI><li>change the type of "loop" so that it includes "unit -> c" on the input side.</LI></UL> For example, I quite like this approach: let loop delay (f:Arrow<_,_>) = arr (fun b -> let rec p = f.run (b,delay (fun () -> snd p)) fst p) You then instantiate "delay" for each looping type, e.g. to "Seq.delay": let loopWithSequenceFeedback f = loop Seq.delay f Here's the alternative that inserts "lazy" into the type: let loop2 delay (f:Arrow<_,_>) = arr (fun b -> let rec p = f.run (b,lazy (snd p)) fst p) and the usage site would still need to propagate the feedback laziness through the feedback type. Here's another possibility which is effectively the same thing and is similar to what you had but with a "lazy" delay let loop3 (f:Arrow<_,_>) = arr (fun b -> let p = ref None p := Some (f.run (b,lazy (snd (!p).Value))) fst (!p).Value) Anyway, that's my shot at it today don

By on 9/29/2008 1:13 PM ()

Thanks Don! That's where I couldn't quite get my brain to go. I forgot that since the most of the material written about Hughes' Arrows are from a Haskell point of view, that sooner or later Haskell's laziness would be taken for granted in the definition of a combinator.

To clarify the operators that mysteriously appeared in my last post. I renamed them from >>>, &&&, |||, ***, and +++ to >.>, &.&, |.|, *.*, and +.+ respectively. Sorry for the lack of explanation on that.

By on 9/29/2008 2:45 PM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper