Sunday, September 28, 2008

A stab at Arrow, Part 3

Well I had an interesting breakthrough today. I got the |||, left, right, and +++ operators, uhmm, operational. The code is as follows


type Arrow<'inp, 'out> (f:'inp ->; 'out) =
let func = f
member x = func x

let arr f = new Arrow<'i,'o>(f)

let (>.>) (f:Arrow<'inp,'mid>) (g:Arrow<'mid,'out>) = arr ( >>

let (&.&) (f:Arrow<'b,'c>) (g:Arrow<'b,'d&>) = arr (fun i -> ( i, i))

let first (f:Arrow<'a, 'b>) = arr (fun (i,x) -> ( 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)

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 -> a
| Right b -> b

let left (f: Arrow&<'a,'b>) =
arr (
fun x -> match x with
| Left a -> Left ( a)
| Right a -> Right a

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)

I have kind of gotten the loop combinator working, But it is a loop combinator combined with a delay function.

Well I guess next, it about time to explain some of this mess.

Monday, September 22, 2008

A bit of a snag

Well it seem that I have hit a bit of a snag in implementing the arrow combinators. I can't for the life of me figure out how to write the loop or the ( ||| ) combinator. The later is problem with my understanding of how to use the Choice type and discriminating unions. But with the former I am genuinely lost. Here is the Haskell signature for loop:

Class Arrow arr => ArrowLoop arr where
loop :: arr (a,c) (b,c) -> arr a b

So in F# that should be either:

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

or :

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

Again in Haskell the loop combinator for functions is defined as:

instance ArrowLoop (->) where
loop f a = b
where (b,c) = f (a,c)

Now how would you implement that in F#?

Friday, September 12, 2008

A Stab at Hughes Arrows in F#

Well it's been awhile since I have posted. For one I 've been a bit bogged down with work. But that's another story that I might go into at a later date. What I wanted to blog about today is arrow. Some of you may be familiar with them. They are abstract constructs that can be very useful in things like animation or event driven programing. How did I go from Euler problems to abstract patterns?

Well it started with my love of video games. Since I like a lot I have hidden aspirations of being a game programmer. (Although to this date I have work only on one game which as far as I know never saw the light of day.) So I was looking into using functional programming techniques with game programming. (BTW there is an interesting journal here by a functional programmer.) So I started looking at animation. I came across an old paper about the Fran framework. It is based on the functional reactive (FR of Fran) programming. But that wasn't the interesting part. It is what this library spawned which is Yampa. Yampa makes extensive use of arrows. So my interest was piqued. I went to look for information on these arrows.

Through the use of the "Programming with Arrows" and "Directing JavaScript with Arrows", I was able to get a little bit of a hold on the concept of arrows. So with a dangerous amount of knowledge of arrows and F# I wrote this:

module Arrow =
type Arrow<'inp, 'out> (f:'inp -> 'out) =
member x = f x

let arr f = new Arrow<;'i,'o>(f)

let op_RightShift (f:Arrow<'inp,'mid>) (g:Arrow<'mid,'out>) =
arr (fun i -> i))

let (&&&) (f:Arrow<'b,'c>;) (g:Arrow<'b,'d>) =
arr (fun i -> ( i, i))

let first (f:Arrow<'a, 'b>) =
arr (fun (i,x) -> ( 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)

I was surprised how quickly I was able to get this together. So what do you think? How can I improve it? What did I do wrong? All comments are welcome.

Tuesday, June 3, 2008

Project Euler Problem 9 in C#

So I have just finished Problem 9. You have got to love the Pythagorean Theorem. I have always been a math geek and I was awestruck when my preCalculus teacher took the time to prove it. Let me tell you. That was the longest bit of logic that I had seen in my 17 years of life. But there it was all 2 whiteboards full. It would have been 3 but he ran out of room.

Well, problem number 9 was an interesting return to the world of Pythagoras. If you haven't looked at the riddle, here it is:

Find the only Pythagorean triplet, {a, b, c}, for which a + b + c = 1000.

OK. The first thing we know is that a2 + b2 = c2 is Pythagorean Theorem.
Now to find Pythagorean Triplets with positive whole numbers(natural numbers) we could try iterating through the infinite set of number until we found the right set or we could use this formula:

a = 2mn
b = m2 - n2
c = m2 + n2
where m > n > 0
So now we have:

1000 = a + b + c
1000 = (2mn) + (m2 - n2) + (m2 + n2)
1000 = 2mn + 2m2 + 0
500 = mn + m2
500 = m(n + m)
(500/m) = n + m
(500/m) - m = n

You now have what you need to write a program to find your triplet. I'll give you my inplementation later.

Monday, June 2, 2008

Project Euler

I know that some of you have heard about Project Euler. If not you should check it out. It'll give you the ol' grey matter a good stretch. The few problems that I have solved have helped to think in more of a functional manner. I'll post some more on the solutions that I have used to solve them later.

Oh, by the way, welcome to my blog.